d760. 10330 - Power Transmission
http://zerojudge.tw/ShowProblem?problemid=d760
內容 ：
DESA正在進行一項電力傳輸的計畫。在 Barisal 這個地方新建了一座發電廠，它的主要目的是提供電力給 Dhaka這座城市。由於 Dhaka 的人口數相當多，DESA 希望盡可能透過網路傳輸最大的電力給它。但是電力在傳輸時會因電阻而損失，所以他們想要使用變電裝置來達到不損失電力的目標。
每個變電裝置有不同的容量。這指的是假如一個變電裝置得到100單位的電，而它的容量只有80個單位，那麼就會損失20單位的電。並且 連接變電裝置之間的電線也是有一定的容量的，例如容量20單位的電線無法傳輸超過20單位的電。DESA 想要知道在沒有電力損失的情況下，最多可以傳輸的電力是多少。這就是你的任務。
輸入說明 ：
輸入含有多組測試資料。
每組測試資料的第一列，有 1 個正整數 N（1 <= N <= 100）代表變電裝置的數目（編號 1 到 N）。下一列有 N 個正整數代表這N個變電裝置的容量。接下來的一列有一個正整數 M，代表各變電裝置間連接電線的數目。再接下來的 M 列每列有3個正整數（i j C）。i, j 為變電裝置的編號，C 為連接 i, j 的電線的容量。電力能夠從 i 變電裝置傳輸到 j 變電裝置。再接下來的一列有2個整數B，D。B代表直接連接發電廠的變電裝置的數目，D代表直接連接到Dhaka的變電裝置的數目。這些連接的電線是特別的，他們的容量是無限大（上圖以藍粗線表示）。下一列有B+D個變電裝置的編號，前B個代表直接連接Barisal發電廠的變電裝置編號，剩下的D個為直接連接到Dhaka的變電裝置的編號。連接Barisal的變電裝置不會連接到Dhaka。
輸出說明 ：
範例輸入 ：
410 20 30 4061 2 51 3 101 4 132 3 52 4 73 4 203 11 2 3 4250 10011 2 1001 11 2
範例輸出 ：
3750
提示 ：
出處 ：
作法 : max flow
這是我第一次寫這個，所以亂寫
由於點有容量，所以把點拆掉，
每次找一條，有容量可以到達終點的路徑，並回朔將路徑上的權值，都扣掉這個容量
找一條我用了SPFA，來完成
直到沒有容量可以再次抵達終點
/**********************************************************************************/
/* Problem: d760 "10330 - Power Transmission" from 10330 - Power Transmission */
/* Language: C */
/* Result: AC (6ms, 438KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-15 21:56:07 */
/**********************************************************************************/
#include<stdio.h>
#define MaxV 10000000
#define MinV 0
int Map[205][205];
int max_flow(int st, int ed, int n) {
int maxflow = 0, tn , tw;
int pre[205], V[205], a, b;
int Q[50000], Qt;
while(1) {
int Used[205] = {};
for(a = 0; a <= n; a++)
V[a] = MinV;
V[st] = MaxV;
Qt = 0, Q[0] = st, pre[st] = st;
for(a = 0; a <= Qt; a++) {
tn = Q[a], Used[tn] = 0;
for(b = 0; b < n; b++) {
tw = (V[tn] < Map[tn][b]) ? V[tn] : Map[tn][b];
if(tw > V[b]) {
V[b] = tw, pre[b] = tn;
if(Used[b] == 0)
Q[++Qt] = b, Used[b] = 1;
}
}
}
if(V[ed] == 0) break;
maxflow += V[ed];
for(a = ed; a != st; a = pre[a]) {
Map[pre[a]][a] -= V[ed], Map[a][pre[a]] += V[ed];
}
}
return maxflow;
}
main() {
int n, m, a, b, v, st, ed, x, y;
int C = 0;
while(scanf("%d", &n) == 1) {
st = 0, ed = 2*n + 1;
for(a = 0; a <= ed; a++)
for(b = 0; b <= ed; b++)
Map[a][b] = 0;
for(a = 1; a <= n; a++) {
scanf("%d", &v);
Map[a][a+n] = v;
}
scanf("%d", &m);
for(a = 0; a < m; a++) {
scanf("%d %d %d", &x, &y, &v);
if(x == y) continue;
Map[x+n][y] += v;
}
scanf("%d %d", &x, &y);
for(a = 0; a < x; a++) {
scanf("%d", &v);
Map[st][v] = MaxV;
}
for(a = 0; a < y; a++) {
scanf("%d", &v);
Map[v+n][ed] = MaxV;
}
printf("%d\n", max_flow(st, ed, ed+1));
}
return 0;
}