跟上一题差不多，就是输入的处理比较麻烦。
View Code #include#include #include using namespace std;#define MIN(a,b) ((a)<(b)?(a):(b))#define N 105int n,ns,nt,m;int g[N][N];int pre[N];void EK(int s,int t){ int u,v,maxflow=0; while(1) { queue q; memset(pre,-1,sizeof(pre)); q.push(s); while(!q.empty()) { u=q.front(),q.pop(); for(v=0;v<=n+1;v++) if(g[u][v] && pre[v]==-1) { pre[v]=u; q.push(v); } if(pre[t]!=-1) break; } if(pre[t]==-1) break; int aug=0x7fffffff; for(v=t,u=pre[t];v!=s;v=u,u=pre[u]) { aug=MIN(aug,g[u][v]); } for(v=t,u=pre[t];v!=s;v=u,u=pre[u]) { g[u][v]-=aug; g[v][u]+=aug; } maxflow+=aug; } printf("%d\n",maxflow);}int main(){ int i; int s,t; int u,v,w; char c; while(~scanf("%d%d%d%d",&n,&ns,&nt,&m)) { s=n; t=n+1; memset(g,0,sizeof(g)); while(m--) { c=0; while(c!='(') scanf("%c",&c); scanf("%d,%d)%d",&u,&v,&w); g[u][v]+=w; } for(i=0;i