首页 > 代码库 > POJ 1459
POJ 1459
A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p
max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c
max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at
most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l
max(u,v) of power delivered by u to v. Let Con=Σ
uc(u) be the power consumed in the net. The problem is to compute the maximum value of Con.
An example is in figure 1. The label x/y of power station u shows that p(u)=x and p
max(u)=y. The label x/y of consumer u shows that c(u)=x and c
max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l
max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20 7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4
Sample Output
15 6
Hint
Source
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define maxn 100+5 #define inf 0x7fffffff int n,np,nc,m; int s,t,edge[maxn][maxn],pre[maxn]; int EK() { int minflow,maxflow = 0; while(1) { memset(pre, 0, sizeof(pre)); minflow = inf; queue<int> q; q.push(s); while(!q.empty()) //BFS寻找增广路 { int u = q.front(); q.pop(); for(int i = 0;i < n+2;i ++) { if(edge[u][i] > 0 && pre[i] == 0 ) { pre[i] = u; q.push(i); } } } //cout << "here" << endl; if(pre[t] == 0) break; for(int i = t; i != s;i = pre[i]) minflow = min(minflow, edge[pre[i]][i]); for(int i = t; i != s;i = pre[i]) { edge[pre[i]][i] -= minflow; edge[i][pre[i]] += minflow; } maxflow += minflow; //cout << maxflow <<endl; } return maxflow; } int main() { char a,b,c; int from,to,cost; while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) { s = n ; t = n + 1; for(int i = 1; i <= m;i ++) { cin >> a >> from >> b >> to >> c >> cost; edge[from][to] = cost; //cout <<from <<" "<<to<<" "<<cost<<endl; } for(int i = 0; i < np;i ++) { cin >> a >> to >> b >> cost; edge[s][to] = cost; //cout <<s<<" "<<to <<" "<<cost <<endl; } for(int i = 0; i < nc;i ++) { cin >>a>>from>>b>>cost; edge[from][t] = cost; //cout <<from <<" "<<t<<" "<<cost<<endl; } int ans = EK(); printf("%d\n", ans); } return 0; }
POJ 1459