题目大意：总公有nodes个节点，有np个发电站，nc个用户，m条传输线路，每个发电站有个最大的发电量，每个用户有个最大的接受量，问从发电站到用户最多可以发电多少。 思路：多源点多汇点最大流，添加一个超级源点，一个超级汇点
#include <cstdio>#include <cstring>#include <queue>using std::queue;#define min(a,b) (a<b?a:b)#define INF 99999999;const int MAXN = 105;int r[MAXN][MAXN];int PRe[MAXN];bool vis[MAXN];int nodes,np,nc,m;bool BFS(int s, int t){ memset(vis,false,sizeof(vis)); memset(pre,-1,sizeof(pre)); queue<int> que; pre[s] = s; vis[s] = true; que.push(s); int p; while(!que.empty()) { p = que.front(); que.pop(); for(int i = 1; i <= nodes; ++i) { if(r[p][i] > 0 && !vis[i]) { pre[i] = p; vis[i] = true; if(i == t) return true; que.push(i); } } } return false;}int EK(int s, int t){ int maxflow = 0; int d = INF; while(BFS(s,t)) { d = INF; for(int i = t; i != s; i = pre[i]) d = min(d,r[pre[i]][i]); for(int i = t; i != s; i = pre[i]) { r[pre[i]][i] -= d; r[i][pre[i]] += d; } maxflow += d; } return maxflow;}int main(){ char ch; int u,v,w,s,t; while(scanf("%d %d %d %d",&nodes,&np,&nc,&m) != EOF) { memset(r,0,sizeof(r)); for(int i = 0; i < m; ++i) { scanf(" %c %d %c %d %c %d",&ch,&u,&ch,&v,&ch,&w); r[u+1][v+1] += w; } s = nodes + 1;// 超级源点 t = nodes + 2;//超级汇点 nodes += 2; for(int i = 0; i < np; ++i) { scanf(" %c %d %c %d",&ch,&v,&ch,&w); r[s][v+1] = w; } for(int i = 0; i < nc; ++i) { scanf(" %c %d %c %d",&ch,&u,&ch,&w); r[u+1][t] = w; } printf("%d/n",EK(s,t)); } return 0;}新闻热点
疑难解答
