只是为了贴上自己的朱刘算法模板
#include<bits/stdc++.h> using namespace std; const int N=102; int b[N],mark[N],color[N],pre[N],ne; double low[N],in[N]; struct edges{int u,v;double w;}e[N*N]; inline void addedge(int u,int v,double wi){e[++ne].u=u,e[ne].v=v,e[ne].w=wi;} #define inf 0x7fffffff inline double zhuliu(int rt,int n,int m){ double res=0; while(1){ int cnt,u,v; for(int i=0;i<=n;i++)in[i]=inf; for(int i=1;i<=m;i++)if(e[i].u!=e[i].v && in[e[i].v]>e[i].w)in[e[i].v]=e[i].w,pre[e[i].v]=e[i].u; for(int i=0;i<=n;i++)color[i]=mark[i]=0; in[rt]=cnt=0,mark[rt]=1; for(int i=1;i<=n;i++){ res+=in[v=i]; while(mark[v]!=i && !color[v] && v!=rt)mark[v]=i,v=pre[v]; if(v!=rt && !color[v]){ cnt++; for(u=pre[v];u!=v;u=pre[u])color[u]=cnt; color[v]=cnt; } } if(!cnt)break; for(int i=1;i<=n;i++)if(!color[i])color[i]=++cnt; int me=0; for(int i=1;i<=m;i++){ v=e[i].v; e[i].u=color[e[i].u],e[i].v=color[e[i].v]; if(e[i].u!=e[i].v)e[++me]=e[i],e[me].w-=in[v]; } n=cnt,rt=color[rt],m=me; } return res; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){scanf("%lf%d",&low[i],&b[i]);if(b[i])addedge(n+1,i,low[i]);else addedge(n+1,i,0);} int k,x,y;double z,ans;scanf("%d",&k); for(;k;k--){ scanf("%d%d%lf",&x,&y,&z); if(b[x] && b[y])addedge(x,y,z),low[y]=min(low[y],z); } ans=zhuliu(n+1,n+1,ne); for(int i=1;i<=n;i++)if(b[i])ans+=(b[i]-1)*low[i]; printf("%.2lf",ans); return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9417875.html
相关资源：JAVA上百实例源码以及开源项目