HDU 3879 Base Station

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 100010;
 5 struct arc{
 6     int to,flow,next;
 7     arc(int x = 0,int y = 0,int z = -1){
 8         to = x;
 9         flow = y;
10         next = z;
11     }
12 }e[1000010];
13 int head[maxn],d[maxn],gap[maxn],tot,S,T;
14 void add(int u,int v,int flow){
15     e[tot] = arc(v,flow,head[u]);
16     head[u] = tot++;
17     e[tot] = arc(u,0,head[v]);
18     head[v] = tot++;
19 }
20 queue<int>q;
21 void bfs(){
22     for(int i = 0; i <= T; ++i){
23         d[i] = -1;
24         gap[i] = 0;
25     }
26     d[T] = 0;
27     q.push(T);
28     while(!q.empty()){
29         int u = q.front();
30         q.pop();
31         ++gap[d[u]];
32         for(int i = head[u]; ~i; i = e[i].next){
33             if(d[e[i].to] == -1){
34                 d[e[i].to] = d[u] + 1;
35                 q.push(e[i].to);
36             }
37         }
38     }
39 }
40 int dfs(int u,int low){
41     if(u == T) return low;
42     int tmp = 0,minH = T - 1;
43     for(int i = head[u]; ~i; i = e[i].next){
44         if(e[i].flow && d[e[i].to] + 1 == d[u]){
45             int a = dfs(e[i].to,min(low,e[i].flow));
46             e[i].flow -= a;
47             e[i^1].flow += a;
48             low -= a;
49             tmp += a;
50             if(!low) break;
51             if(d[S] >= T) return tmp;
52         }
53         if(e[i].flow) minH = min(minH,d[e[i].to]);
54     }
55     if(!tmp){
56         if(--gap[d[u]] == 0) d[S] = T;
57         ++gap[d[u] = minH + 1];
58     }
59     return tmp;
60 }
61 int sap(int ret = 0){
62     bfs();
63     while(d[S] < T) ret += dfs(S,INF);
64     return ret;
65 }
66 int main(){
67     int n,m,u,v,w;
68     while(~scanf("%d%d",&n,&m)){
69         memset(head,-1,sizeof head);
70         int sum = tot = 0;
71         S = n + m + 1;
72         T = S + 1;
73         for(int i = 1; i <= n; ++i){
74             scanf("%d",&w);
75             add(S,i,w);
76         }
77         for(int i = 1; i <= m; ++i){
78             scanf("%d%d%d",&u,&v,&w);
79             sum += w;
80             add(u,i + n,INF);
81             add(v,i + n,INF);
82             add(i + n,T,w);
83         }
84         printf("%d\n",sum-sap());
85     }
86     return 0;
87 }