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.
Input
Output
Sample Input
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)207 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
156
Hint
Source
#include#include #include #include #include using namespace std;#define maxn 100+5#define inf 0x7fffffffint 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 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 < > a >> from >> b >> to >> c >> cost; edge[from][to] = cost; //cout < <<" "< <<" "< < > a >> to >> b >> cost; edge[s][to] = cost; //cout < <<" "<<<" "< < >a>>from>>b>>cost; edge[from][t] = cost; //cout < <<" "< <<" "< <