「Bzoj 1497」「NOI2006」最大获利 (最大权闭合子图, 最小割)

BZOJ 1497
题意：有$n$个结点，$m$条无向边可供建设。
建立一个结点$u$有一定的花费$p_u$。建立一条无向边有一定的非负收益$w_e$。
建立一条无向边$(u, v)$的必要条件是要先建立点$u$，点$v$。
求最大获利。

将点、边作为事件，边$(u, v)$依赖点$u,v$，即转化为一个最大权闭合子图问题。
将边拆成点，按最大权闭合子图问题做即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 60000 + 5, MAXM = 200000 + 5, INF = 2147483647;
struct data {
    int v, cap;//Öյ㣬²ÐÁ¿
}ed[MAXM * 2];
int n, m, s, t, maxd;
vector<int> G[MAXN];
int en, cur[MAXN], d[MAXN];//±ßÊý£¬µ±Ç°»¡(ÓÃÓÚÓÅ»¯)£¬¾àÀëSµÄ¾àÀë
void ins(int u, int v, int c) {//¼ÓË«Ïò±ß 
    ed[en] = (data){v, c}, G[u].push_back(en++);
    ed[en] = (data){u, 0}, G[v].push_back(en++);//·´Ïò»¡ÈÝÁ¿Îª0£¡²»ÊÇ-c£¬Á÷Á¿²ÅÊÇÊغãµÄ 
}
bool bfs() {//Çó·Ö²ãͼ 
    queue<int> q; 
    for (int i = 0; i <= maxd; i++) d[i] = INF;
    d[s] = 0, q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap;
            if (d[v] == INF && cap) {//û±»·Ö²ã²¢ÇÒ¿ÉÒԸĽø 
                d[v] = d[u] + 1;//·Ö²ã 
                q.push(v); 
            }
        }
    }
    return d[t] != INF;//Èç¹û´æÔÚÔö¹ã·Ôòt»á±»·ÃÎÊ 
}
int dfs(int u, int a) {//¶à·Ôö¹ã 
    if (u == t) return a;//Ôö¹ãµ½ÖÕµã
    if (a == 0) return 0;//ûÓпɸĽøÁ¿
    int retflow = 0;
    for (int &i = cur[u]; i < G[u].size(); i++) {
        int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap;
        if (d[u] + 1 == d[v]) {//°´²ã´ÎÔö¹ã
            int f = dfs(v, min(a, cap)); //¼ÌÐøÔö¹ã 
            if (f > 0) {//Äܹ»¸Ä½ø
                retflow += f, a -= f, ed[G[u][i]].cap -= f, ed[G[u][i] ^ 1].cap += f;//¸Ä½ø
                if (a == 0) break;//ÓÅ»¯£ºÃ»ÓпɸĽøÁ¿Ê±´ËµãÓ¦¸Ã²»ÔÙ·ÃÎÊ 
            }
        }
    }
    return retflow;
}
int dinic() {//Çó×î´óÁ÷ 
    int flow = 0;
    while (bfs()) {
        for (int i = 0; i <= maxd; i++) cur[i] = 0; //DFSÍêÒÔºóÒªÇå¿Õµ±Ç°»¡
        flow += dfs(s, INF);
    }
    return flow;
}
void clean() {
    en = 0;
    for (int i = 0; i <= n; i++) G[i].clear();
}
void solve() {

    clean();

    scanf("%d%d", &n, &m);
    s = n + m + 1, t = n + m + 2, maxd = n + m + 2;
    for (int p, i = 1; i <= n; ++i) scanf("%d", &p), ins(i, t, p);

    int ans = 0;

    for (int x, y, c, i = 1; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        ins(s, n + i, c);
        ins(n + i, x, INF);
        ins(n + i, y, INF);
        ans += c;
    }

    printf("%d\n", ans - dinic());
}
int main() {
    solve();
    return 0;
}