题意：有n个城市。现在需要在这些城市上修一些通信的基站，在每个城市上修一个基站都需要花费一定的费用。另外给出m个组合(a,b,c)，表示如果第a个城市和第b个城市都修起了基站，那么公司可以获利c。但公司并不需要在每个城市都修基站，他们只希望自己能够获得最大的利益。问最大利益。
裸的最大闭合子图吧。只要知道这个模型就是水题。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 55010 7 #define maxm 400000 8 using namespace std; 9 int v[maxm],next[maxm],w[maxm]; 10 int first[maxn],d[maxn],q[maxn],work[maxn]; 11 int e,S,T; 12 13 void init(){ 14 e = 0; 15 memset(first,-1,sizeof(first)); 16 } 17 18 19 void add_edge(int a,int b,int c){ 20 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 21 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 22 } 23 24 int bfs(){ 25 int rear = 0; 26 memset(d,-1,sizeof(d)); 27 d[S] = 0;q[rear++] = S; 28 for(int i = 0;i < rear;i++){ 29 for(int j = first[q[i]];j != -1;j = next[j]) 30 if(w[j] && d[v[j]] == -1){ 31 d[v[j]] = d[q[i]] + 1; 32 q[rear++] = v[j]; 33 if(v[j] == T) return 1; 34 } 35 } 36 return 0; 37 } 38 39 int dfs(int cur,int a){ 40 if(cur == T) return a; 41 for(int &i = work[cur];i != -1;i = next[i]){ 42 if(w[i] && d[v[i]] == d[cur] + 1) 43 if(int t = dfs(v[i],min(a,w[i]))){ 44 w[i] -= t;w[i^1] += t; 45 return t; 46 } 47 } 48 return 0; 49 } 50 51 int dinic(){ 52 int ans = 0; 53 while(bfs()){ 54 memcpy(work,first,sizeof(first)); 55 while(int t = dfs(S,INF)) ans += t; 56 } 57 return ans; 58 } 59 60 61 int main(){ 62 int n,m; 63 while(scanf("%d%d",&n,&m) == 2){ 64 init(); 65 S = 0,T = n+m+1; 66 int sum = 0; 67 for(int i = 1;i <= n;i++){ 68 int tmp; 69 scanf("%d",&tmp); 70 add_edge(i,T,tmp); 71 } 72 for(int i = 1;i <= m;i++){ 73 int a,b,c; 74 scanf("%d%d%d",&a,&b,&c); 75 sum += c; 76 add_edge(S,i+n,c); 77 add_edge(i+n,a,INF); 78 add_edge(i+n,b,INF); 79 } 80 printf("%d ",sum - dinic()); 81 } 82 }