HDU 3879 && BZOJ 1497：Base Station && 最大获利 （最大权闭合图）

http://acm.hdu.edu.cn/showproblem.php?pid=3879

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

题意：给出n个点m条边，其中每个点有一个权值代表修建这个点需要耗费的钱，然后m条边里面，代表如果两个修建好的点相连的话，那么可以得到一点利润。求最大的获利。

思路：和BZOJ 1497是同一道题目。学习最大权闭合图的题目，看了一下不清楚应该怎么建图，然后只好搜一个论文来看看。http://wenku.baidu.com/view/6507a6fe2cc58bd63186bdaf.html

建图：将S与n个点相连，权值为点权，将m条边当成点与T相连，权值为边权，边的两个顶点分别再和化成点的边相连，权值为INF。

闭合图可以解决一些依赖关系，例如这道题目需要有两个顶点才可以得到一条边，边是依赖于两个顶点的形成的。

于是网络是这样的：S->站的点->边的点->T。

我们对这个网络得到的一个割 = 选择的站的花费 + 未选择的边的利润（也可以看作损失的利润），显然这个割集越小越好，即最小割。我们要求的是答案 = 选择的边的利润 – 选择的站的利润。

那么我们一开始可以先累加得到一个选择所有边的利润tot，那么恰好tot – 最小割 = 选择所有边的利润 – 未选择边的利润 – 选择的站的花费 = 选择的边的利润 – 选择的站的利润 = 答案。

所以跑一遍最大流后就用tot – 最大流就可以得到答案了。

记得边的数组要开大一点。

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <queue>
 using namespace std;
 #define INF 0x3f3f3f3f
 #define N 60010
 #define M 350010 // 30w不过
 struct Edge {
     int u, v, nxt, cap;
     Edge () {}
     Edge (int u, int v, int nxt, int cap) : u(u), v(v), nxt(nxt), cap(cap) {}
 } edge[M];
 int head[N], tot, S, T, cur[N], dis[N], gap[N], pre[N]; void Add(int u, int v, int cap) {
     edge[tot] = Edge(u, v, head[u], cap); head[u] = tot++;
     edge[tot] = Edge(v, u, head[v], ); head[v] = tot++;
 } void BFS() {
     queue<int> que;
     que.push(T);
     memset(dis, INF, sizeof(dis));
     memset(gap, , sizeof(gap));
     gap[]++; dis[T] = ;
     while(!que.empty()) {
         int u = que.front(); que.pop();
         for(int i = head[u]; ~i; i = edge[i].nxt) {
             if(dis[edge[i].v] != INF) continue;
             dis[edge[i].v] = dis[u] + ;
             gap[dis[edge[i].v]]++;
             que.push(edge[i].v);
         }
     }
 } int ISAP(int n) {
     BFS();
     memcpy(cur, head, sizeof(cur));
     int u = pre[S] = S, flow, ans = , index, i;
     while(dis[S] < n) {
         if(u == T) {
             flow = INF;
             for(i = S; i != T; i = edge[cur[i]].v)
                 if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;
             for(i = S; i != T; i = edge[cur[i]].v)
                 edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;
             u = index; ans += flow;
         }
         for(i = cur[u]; ~i; i = edge[i].nxt) if(edge[i].cap && dis[edge[i].v] +  == dis[u]) break;
         if(~i) { cur[u] = i; pre[edge[i].v] = u; u = edge[i].v; }
         else {
             if(--gap[dis[u]] == ) break;
             int md = n + ;
             for(i = head[u]; ~i; i = edge[i].nxt)
                 if(edge[i].cap && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;
             gap[dis[u] = md + ]++;
             u = pre[u];
         }
     }
     return ans;
 } int main() {
     int n, m;
     while(~scanf("%d%d", &n, &m)) {
         memset(head, -, sizeof(head));
         tot = ; S = ; T = n + m + ;
         for(int i = ; i <= n; i++) {
             int w; scanf("%d", &w);
             Add(S, i, w); // 源点和站点相连
         }
         int tot = ;
         for(int i = ; i <= m; i++) {
             int a, b, c;
             scanf("%d%d%d",&a, &b, &c);
             tot += c; // 选择边的利润和
             Add(i + n, T, c); // 边的点和汇点相连
             Add(a, i + n, INF);
             Add(b, i + n, INF);
         }
         printf("%d\n", tot - ISAP(T + ));
     }
     return ;
 }