題目大意：總公有nodes個節(jié)點，有np個發(fā)電站，nc個用戶，m條傳輸線路，每個發(fā)電站有個最大的發(fā)電量，每個用戶有個最大的接受量，問從發(fā)電站到用戶最多可以發(fā)電多少。 思路：多源點多匯點最大流，添加一個超級源點，一個超級匯點
#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;}新聞熱點
疑難解答
