题意：给出n,np,nc,m，n为节点数，np为发电站数，nc为用电厂数，m为边的个数。
接下来给出m个数据(u,v)z，表示w(u,v)允许传输的最大电力为z；np个数据(u)z，表示发电站的序号，以及最大的发电量；
nc个数据(u)z，表示用电厂的序号，以及最大的用电量。
最后让你求可以供整个网络使用的最大电力。
思路：纯模板题。
这里主要是设一个源点s和一个汇点t，s与所有发电厂相连，边的最大容量为对应发电厂的最大发电量；
t与所有用电厂相连，边的最大容量为对应用电厂的最大用电量。
因为节点编号0~n-1，所以这里s设为n，t设为n+1。
接着求最大流即可。
#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int INF=0x3f3f3f3f; const int maxn=110; int pri[maxn]; //用来记录增广路 int n,np,nc,m; //n为节点数，np为发电站数，nc为用电厂数，m为边的个数。 int s,t,sum; //源点，汇点，最大流 struct Edge{ int c,f; //c为容量，f为流 }edge[maxn][maxn]; bool BFS() { queue<int> q; memset(pri,0,sizeof(pri)); pri[s]=1; q.push(s); while(!q.empty()) { int temp=q.front(); q.pop(); for(int i=0; i<=n+1; i++) { if(!pri[i] && edge[temp][i].c-edge[temp][i].f){ pri[i]=pri[temp]+1; if(i==t) return true; //即如果可以流到汇点，直接return true q.push(i); } } } return false; } //p表示当前节点，flow表示该节点通过的流量 int dinic(int p,int flow){ if(p==t){ return flow; } int f=flow; for(int i=0;i<=n+1;i++){ if(pri[i]==pri[p]+1 && edge[p][i].c-edge[p][i].f){ int a=edge[p][i].c-edge[p][i].f; //a为该边可以增加的流量 int ff=dinic(i,min(a,flow)); //ff为路径中所有a的最小值，即为该条路中可以增加的流量 edge[p][i].f+=ff; //正向边 edge[i][p].f-=ff; //逆向边，逆向边的c为0，f为负值，这样c-f即为正向边的目前流量，即可以“退流”的量 flow-=ff; } } return f-flow; } int main() { int u,v,z; while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){ sum=0; s=n;t=n+1; for(int i=0;i<maxn;i++){ for(int j=0;j<maxn;j++) edge[i][j].c=edge[i][j].f=0; } for(int i=1;i<=m;i++){ while(getchar()!='('); //要加上这句。 scanf("%d,%d)%d",&u,&v,&z); //printf("%d %d %d ",u,v,z); edge[u][v].c=z; } for(int i=0;i<np;i++){ while(getchar()!='('); scanf("%d)%d",&u,&z); //printf("%d %d ",u,z); edge[s][u].c=z; } for(int i=0;i<nc;i++){ while(getchar()!='('); scanf("%d)%d",&u,&z); //printf("%d %d ",u,z); edge[u][t].c=z; } //如能找到增广路，则sum加上增加的流量 while(BFS()){ sum+=dinic(s,INF); } printf("%d ",sum); } return 0; }