题目大意：就是有发电站、用户、中转站，还有电力传输路线，每个节点有可能被传输了多少电，也可能消耗了多少电，也可能生产了多少电，也可能传输了多少电。发电站除了生产电之外都可能会。 用户除了生产电之外都可能会，而中转站只会传输电和被传输电。求电力消耗的最大值。 思路：建立一个超级源点和所有发电站连接起来，建立一个超级汇点和所有用户连接起来，那么这个图的最大流即是最大消耗量。 想象一下，在复杂的地下水管道下面，在源点流入了一股定量的水，那么能够到达汇点的即是能够达到每位用户的总和，而我们现在就是要求这个总和 的最大值。 我是用SAP+GAP优化的模板撸过的~~第一次敲这个模板竟然忘了反向边。囧。。而且更忘了反向边 容量值是0。囧。。 AC program： #include #include #include #include #include #include using namespace std; #define inf 1000000000 #define maxn 150 #define maxm 20500 //note!! 如果RE就是这里出的原因 int num;//note1 int n,np,nc,m; struct node { int c,next,to; }e[maxm]; //note2 int box[maxn];//链式前向星 void init1() { num=0; memset(box,-1,sizeof(box));//按道理应该是初始化为-1的 //int aa,bb,w,u,v; int u,v,w; char yy[20]; for(int i=1;i<=m;i++) { scanf("%s",yy); sscanf(yy,"(%d,%d)%d",&u,&v,&w); u+=2;//统一加2 v+=2; e[num].to=v; e[num].c=w; e[num].next=box[u]; box[u]=num; num++; ///------- e[num].to=u; e[num].c=0;//note!! e[num].next=box[v]; box[v]=num; num++; ///------- } for(int i=1;i<=np;i++) { scanf("%s",yy); sscanf(yy,"(%d)%d",&v,&w); u=1; //原点设为1，所以原来的点要往后推2 v+=2; e[num].to=v; e[num].c=w; e[num].next=box[u]; box[u]=num; num++; ///------- e[num].to=u; e[num].c=0;//note!! e[num].next=box[v]; box[v]=num; num++; ///------- } for(int i=1;i<=nc;i++) { scanf("%s",yy); sscanf(yy,"(%d)%d",&u,&w); u+=2; v=n+2; e[num].to=v; e[num].c=w; e[num].next=box[u]; box[u]=num; num++; ///------- e[num].to=u; e[num].c=0;//note!! e[num].next=box[v]; box[v]=num; num++; ///------- } } int sap(int start,int end,int nnn) { int numh[maxn],h[maxn],cur[maxn],pre[maxn]; int cur_flow,flow_ans=0,u,tmp,neck,i; memset(h,0,sizeof(h)); memset(numh,0,sizeof(numh));/// memset(pre,-1,sizeof(pre));/// for(int i=1;i<=nnn;i++) cur[i]=box[i]; numh[0]=nnn; u=start; while(h[start]e[cur[i]].c) { neck=i; cur_flow=e[cur[i]].c; } } for(i=start;i!=end;i=e[cur[i]].to) { tmp=cur[i]; e[tmp].c-=cur_flow; e[tmp^1].c+=cur_flow; } flow_ans+=cur_flow; u=neck; } for(i=cur[u];i!=-1;i=e[i].next) if(e[i].c&&h[u]==h[e[i].to]+1) break; if(i!=-1) { cur[u]=i; pre[e[i].to]=u; u=e[i].to; } else { if(0==--numh[h[u]])break; cur[u]=box[u]; for(tmp=nnn,i=box[u];i!=-1;i=e[i].next) if(e[i].c) tmp=min(tmp,h[e[i].to]); h[u]=tmp+1; ++numh[h[u]]; if(u!=start)u=pre[u]; } } return flow_ans; } int main() { while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF) { init1(); int love; love=sap(1,n+2,n+2);//n+2个点 printf("%d ",love); } //system("pause"); return 0;}