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); //headconst LL INF = 1LL<<40; const int N = 2e3 + 100; 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, 0, g[u].size()-1}); } void bfs(int s) {mem(level, -1);queue<int>q;level[s] = 0;q.push(s);while (!q.empty()) {int u = q.front();q.pop();for (int i = 0; i < g[u].size(); i++) {edge e = g[u][i];if(e.w > 0 && level[e.to] < 0) {level[e.to] = level[u] + 1;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 > 0 && level[u] < level[e.to]) {LL d = dfs(e.to, t, min(f, e.w));if(d > 0) {e.w -= d;g[e.to][e.rev].w +=d;return d;}}}return 0; } LL max_flow(int s, int t) {LL flow = 0;while(true) {bfs(s);if(level[t] < 0) return flow;LL f;mem(iter, 0);while ((f = dfs(s, t, INF)) > 0) {flow += f;}} } int main() {int n, m, w, u, v;scanf("%d %d", &n, &m);int s = 0, t = n+m+1;for (int i = 1; i <= n; i++) {scanf("%d", &w);add_edge(i, t, w);}LL sum = 0;for (int i = 1; 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 0; }
