to]=min(a[u],e.cap-e.flow); } } } if(a[t]==0)return f; int x=t; while(x!=s){ edges[p[x]].flow+=a[t]; edges[p[x]^1].flow-=a[t]; x=edges[p[x]].from; } f+=a[t]; } return f; } int main()//多源多汇点，在前面加个源点，后面加个汇点，转成单源单汇点 { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int start,end; int np,nc,m; int u,v,z; while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF) { edges.clear(); for(int i=0;i<=n+1;i++)G[i].clear(); while(m--) { while(getchar()!='('); scanf("%d,%d)%d",&u,&v,&z); u++;v++; addedge(u,v,z); } while(np--) { while(getchar()!='('); scanf("%d)%d",&u,&z); u++; addedge(0,u,z); } while(nc--) { while(getchar()!='('); scanf("%d)%d",&u,&z); u++; addedge(u,n+1,z); } start=0; end=n+1; int ans=Ek(start,end); cout<
dinic算法版：
#include
#include
#include
#include
#include
using namespace std; const int INF=0x3f3f3f3f; const int MAXN=150;//点数的最大值 const int MAXM=20500;//边数的最大值 int n,a[MAXN],p[MAXN]; int cur[MAXN],d[MAXN],vis[MAXN]; struct Edge { int from,to,cap,flow; }; std::vector
edges; std::vector
G[MAXN]; void addedge(int u,int v,int w){ edges.push_back((Edge){u,v,w,0}); edges.push_back((Edge){v,u,0,0}); int m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } int bfs(int s,int t) { memset(vis,0,sizeof vis); queue
q; q.push(s); vis[s]=1; d[s]=0; while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i
e.flow){ q.push(e.to); vis[e.to]=1; d[e.to]=d[u]+1; } } } return vis[t]; } int dfs(int x,int a,int t){ if(x==t||a==0)return a; int flow=0,f=0; for(int &i=cur[x];i
0){ e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } int dinic(int s,int t){ int flow=0; while(bfs(s,t)){ memset(cur,0,sizeof cur); flow+=dfs(s,INF,t); } return flow; } int main()//多源多汇点，在前面加个源点，后面加个汇点，转成单源单汇点 { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int start,end; int np,nc,m; int u,v,z; while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF) { edges.clear(); for(int i=0;i<=n+1;i++)G[i].clear(); while(m--) { while(getchar()!='('); scanf("%d,%d)%d",&u,&v,&z); u++;v++; addedge(u,v,z); } while(np--) { while(getchar()!='('); scanf("%d)%d",&u,&z); u++; addedge(0,u,z); } while(nc--) { while(getchar()!='('); scanf("%d)%d",&u,&z); u++; addedge(u,n+1,z); } start=0; end=n+1; int ans=dinic(start,end); cout<
|