POJ1459Power Network（電網）——最大流水題

長篇閱讀。。。

題目描述：
一個電網包含一些結點（電站、消費者、調度站），這些結點通過電線連接。每個結點u 可能
被供給s(u)的電能，s(u)≥0；同時也可能產生p(u)的電能，0≤p(u)≤pmax(u)；站點u 還有可能
消費c(u)電能，0≤c(u)≤min( s(u), cmax(u) )；可能傳輸d(u)的電能，d(u) = s(u) + p(u) - c(u)。
以上這些量存在以下限制關系：對每個電站，c(u) = 0；對每個消費者，p(u) = 0；對每個調度站，
p(u) = c(u) = 0。
在電網中兩個結點u 和v 之間最多有一條電線連接。從結點u 到結點v 傳輸L(u,v)的電能，0≤L(u,v)≤Lmax(u,v)。定義Con 為c(u)的總和，表示電網中消費電能的總和。本題的目的是求
Con 的最大值。
電網的一個例子如圖6.24 所示。在圖(a)中，電站結點u 的標記”x/y”代表p(u) = x、pmax(u) =
y。消費者結點u 的標記”x/y”代表c(u) = x、cmax(u) = y。每條電線所對應的邊(u,v)，其標記”x/y”
代表L(u,v) = x、Lmax(u,v) = y。在圖(b)中，消費的最大電能Con = 6，圖(a)列出了在此狀態下各
個站點的s(u)、p(u)、c(u)和d(u)。注意，如圖(b)所示的電網中，電能的流動還存在其他狀態，但
消費的電能總和不超過6。

輸入描述：
輸入文件中包含多個測試數據。每個測試數據描述了一個電網。每個測試數據的第1 行為4
個整數：n np nc m，其中，0≤n≤100，代表結點數目；0≤np≤n，代表電站數目；0≤nc≤n，
代表消費者數目；0≤m≤n2，代表傳輸電線的數目。接下來有m 個三元組，(u,v)z，其中u 和v
為結點序號（結點序號從0 開始計起），0≤z≤1000，代表Lmax(u,v)的值。接下來有np 個二元
組，(u)z，其中u 為電站結點的序號，0≤z≤10000，代表pmax(u)的值；每個測試數據的最後是
nc 個二元組，(u)z，其中u 為消費者結點的序號，0≤z≤10000，代表cmax(u)的值。所有數據
都是整數。除三元組(u,v)z 和二元組(u)z 中不含空格外，輸入文件中其他位置允許出現空格。測試
數據一直到文件尾。

輸出描述：<喎?/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxiciAvPgq21MrkyOvOxLz+1tDDv7j2suLK1Mr9vt3L+cPoyva1xLXnzfijrMrks/bVvNK70NCjrM6q0ru49tX7yv2jrLHtyr6158341tDE3M/7t9G15zxiciAvPgrE3LXE1+6089a1oaM8L3A+CjxwPtStzbzW0LXEtefVvqOsz/u30dXfsrvE3Nf3zqrUtLXjus2747Xjo6zM7bzT0ru49tS0teO6zbvjteOjrNS0teO1vbXn1b61xMjdwb/OqnBtYXijrM/7t9HV37W9u+O147XEyN3Bv86qY21heKOs1PLUrczivs3XqruvzqrH873i1+6088H3wcs8YnIgLz4KzOLEv7XEyuTI69PD1f3U8rHttO/KvXNzY2FuZihzLCZyZHF1bzsoJWQsJWQpJWQmcmRxdW87LCZhbXA7dSwmYW1wO3YsJmFtcDt6KTs8YnIgLz4KSVNBUCZoZWxsaXA7PGJyIC8+Ck1lbW9yeTogMTA2MEsgVGltZTogMTEwTVM8L3A+CjxwcmUgY2xhc3M9"brush:java;"> #include #include #include #include const int maxn=110; const int maxm=1010; const int INF=0x3f3f3f3f; using namespace std; int n,s,t; struct Edge{ int from,to,cap,flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; vector edges; vector G[maxn]; int gap[maxn],d[maxn],cur[maxn],p[maxn]; inline void addedge(int u,int v,int c){ edges.push_back(Edge(u,v,c,0)); edges.push_back(Edge(v,u,0,0)); int m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } int ISAP(){ s=n,t=n+1; n+=2; memset(cur,0,sizeof(cur)); memset(d,0,sizeof(d)); memset(gap,0,sizeof(gap)); int x=s,flow=0,a=INF; while(d[s]e.flow&&d[e.to]+1==d[x]){ p[e.to]=G[x][i]; cur[x]=i; x=e.to; ok=1; a=min(a,e.cap-e.flow); break; } } if(!ok){ int m=n; for(int i=0;ie.flow) m=min(m,d[e.to]); } if(--gap[d[x]]==0) break; gap[d[x]=m+1]++; cur[x]=0; if(x!=s) x=edges[p[x]].from; } } return flow; } void Init(){ edges.clear(); for(int i=0;i