Codeforces 1082 G - Petya and Graph

G - Petya and Graph

思路:

最大权闭合子图

对于每条边,如果它选了,那么它连的的两个点也要选

边权为正,点权为负,那么就是求最大权闭合子图

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const LL INF = 1LL<<;

const int N = 2e3 + ;

int level[N], iter[N];

struct edge {

    int to;

    LL w;

    int rev;

};

vector<edge>g[N];

void add_edge(int u, int v, LL w) {

    g[u].pb(edge{v, w, g[v].size()});

    g[v].pb(edge{u, , g[u].size()-});

}

void bfs(int s) {

    mem(level, -);

    queue<int>q;

    level[s] = ;

    q.push(s);

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        for (int i = ; i < g[u].size(); i++) {

            edge e = g[u][i];

            if(e.w >  && level[e.to] < ) {

                level[e.to] = level[u] + ;

                q.push(e.to);

            }

        }

    }

}

LL dfs(int u, int t, LL f) {

    if(u == t ) return f;

    for (int &i = iter[u]; i < g[u].size(); i++) {

        edge &e = g[u][i];

        if(e.w >  && level[u] < level[e.to]) {

            LL d = dfs(e.to, t, min(f, e.w));

            if(d > ) {

                e.w -= d;

                g[e.to][e.rev].w +=d;

                return d;

            }

        }

    }

    return ;

}

LL max_flow(int s, int t) {

    LL flow = ;

    while(true) {

        bfs(s);

        if(level[t] < ) return flow;

        LL f;

        mem(iter, );

        while ((f = dfs(s, t, INF)) > ) {

            flow += f;

        }

    }

}

int main() {

    int n, m, w, u, v;

    scanf("%d %d", &n, &m);

    int s = , t = n+m+;

    for (int i = ; i <= n; i++) {

        scanf("%d", &w);

        add_edge(i, t, w);

    }

    LL sum = ;

    for (int i = ; i <= m; i++) {

        scanf("%d %d %d", &u, &v, &w);

        sum += w;

        add_edge(i+n, u, INF);

        add_edge(i+n, v, INF);

        add_edge(s, i+n, w);

    }

    printf("%lld\n", sum - max_flow(s, t));

    return ;

}