题意：有n个据点，np个发电机，nc个用户，m条电线，给出发电机，用户，电线的电流限制，求最大网络电流。
这是带节点的网络流，其实和原来没什么区别，只要在前后都增加一个据点，在这里我加了0和n+1两个节点，而发电机节点的电流限制可以
转化为0->节点的电流限制，用户节点电流的限制可以转化为节点->n+1的电流限制，之后套用最大网络流模板即可，这里我写了，Edmonds_karp算法。
稍后传上Dinic算法。。。。。。。。。。。。。。。。。。。。
AC代码如下：
Edmonds_karp算法
#include
#include
#include
#include
#define min(a,b) (a
q; int a,b; for(i=0;i<=n+1;i++) p[i]=-1; f[0]=inf; q.push(s); while(!q.empty()) { b=q.front (); q.pop(); if(b==e) break; for(i=0;i<=n+1;i++) { if(p[i]==-1&&map[b][i]>0) { f[i]=min(map[b][i],f[b]); p[i]=b; q.push(i); } } } if(p[e]==-1) return -1; else return f[e]; } int maxflow(int s,int e) { int i,j; int a,ans=0; a=Edmonds_karp(s,e); while(a!=-1) { int k=e,min=inf; while(k!=s) { map[p[k]][k]-=a; map[k][p[k]]+=a; k=p[k]; } ans+=a; a=Edmonds_karp(s,e); } return ans; } int main() { int i,j; int a,b,c,d,f; char z,x,y; while(cin>>n>>np>>nc>>m) { memset(map,0,sizeof map); for(i=1;i<=m;i++) { cin>>z>>a>>x>>b>>y>>c; map[a+1][b+1]+=c; } for(i=1;i<=np;i++) { cin>>z>>d>>x>>f; map[0][d+1]+=f; } for(i=1;i<=nc;i++) { cin>>z>>d>>x>>f; map[d+1][n+1]+=f; } cout<
Dinic算法
#include
#include
#include
#include
#define inf 100000000 #define min(a,b) (a
q; int a,b; memset(cs,-1,sizeof cs); cs[0]=0; q.push(0); while(!q.empty()) { b=q.front (); q.pop(); for(i=0;i<=n+1;i++) { if(cs[i]==-1&&map[b][i]>0) { cs[i]=cs[b]+1; q.push(i); } } } if(cs[n+1]==-1) return 0; else return 1; } int dfs(int s,int mf) { int i,j; int a,b; if(s==n+1) return mf; for(i=0;i<=n+1;i++) { if(cs[i]==cs[s]+1&&map[s][i]>0&&(a=dfs(i,min(mf,map[s][i])))) { map[s][i]-=a; map[i][s]+=a; return a; } } return 0; } int main() { int i,j; int a,b,c,d,f; while(cin>>n>>np>>nc>>m) { memset(map,0,sizeof map); for(i=1;i<=m;i++) { scanf(" (%d,%d)%d",&a,&b,&c); map[a+1][b+1]+=c; } for(i=1;i<=np;i++) { scanf(" (%d)%d",&d,&f); map[0][d+1]+=f; } for(i=1;i<=nc;i++) { scanf(" (%d)%d",&d,&f); map[d+1][n+1]+=f; } int ans=0,sum; while(bfs()) { while(sum=dfs(0,inf)) ans+=sum; } cout<