?
题目给你一大段解释，其实就是废话。还给了一张解释图，其实就是误导。
题目大意：对于一个电力网来说，既有发电站，也有用电方，还有输电线路。其中发电站是有限度的，用电方也是有限度的，输电线更是有限度的，所以明显一个网络流问题。先给出线路和限度，再给出用电方，最后后出发电站。
因为是多源点（多个发电站），多汇点（多个用电方），所以需要超级源处理。
多为超级源，就是假设有一个源，连向所有的源点（发电站），其线路容量就是发电站的限度，那么就可以把发电站当做普通点处理。再假设一个超级汇点，那么就可以把所有汇点（用电方）连向这个超级汇点，其线路容量是用电方限度，那么，就变成一个单纯的单源点，单汇点的最大流问题。用dinic便可以解决。
?
#include#include #include #include #include #include #define MAX 999999 using namespace std; int map_[200][200]; int dis[200]; int bfs(int s,int t) { int now; memset(dis,-1,sizeof (dis)); dis[s] = 0; queue que; que.push(s); while(!que.empty()) { now = que.front(); que.pop(); for (int i = 0;i <= t;i++) if (dis[i] == -1 && map_[now][i] > 0) { dis[i] = dis[now] + 1; que.push(i); } } if (dis[t] != -1) return 1; return 0; } int dinic(int s,int t,int x) { if (s == t) return x; int tmp = x; for (int i = 0;i <= t;i++) { if (dis[i] == dis[s] + 1 && map_[s][i] > 0) { int imin = dinic(i,t,min(map_[s][i],x)); map_[s][i] -= imin; map_[i][s] += imin; x -= imin; } } return tmp - x; } int main() { int n,np,nc,m; while (~scanf (%d%d%d%d,&n,&np,&nc,&m)) { int i,k; int u,v,c; memset(map_,0,sizeof(map_)); for (i = 0;i < m;i++) { scanf( (%d,%d)%d,&u,&v,&c); map_[u + 1][v + 1] += c; //0是超级源点，其他点后移 } for(i = 0;i < np;i++) { scanf( (%d)%d,&v,&c); map_[0][v + 1] += c; } for(i = 0;i < nc;i++) { scanf( (%d)%d,&u,&c); map_[u + 1][n + 1] += c; } int ans = 0; while (bfs(0,n + 1)) ans += dinic(0,n + 1,MAX); printf (%d ,ans); } return 0; }
?
不忘初心，方得始终?