（待更新）
Prelude
传送到LOJ
虽然是网络流24题中的T2，但是挺难的，至少我之前不知道什么是最大闭合权子图。
Solution
首先要明白什么是最大闭合权子图，然后求最小割就可以了。。。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int MAXN = 110; const int MAXM = 6000; const int INF = 0x3f3f3f3f; namespace Dinic { struct Edge { int u,v,c,f; Edge() {} Edge(int u,int v,int c,int f): u(u), v(v), c(c), f(f) {} }; int n,m,s,t; Edge edge[MAXM]; int head[MAXN],nxt[MAXM]; int dis[MAXN],cur[MAXN]; void init(int _n) { n = _n, m = 0; for(int i = 0; i < n; ++i) head[i] = -1; } void adde(int u,int v,int c) { nxt[m] = head[u]; edge[m] = Edge(u,v,c,0); head[u] = m++; nxt[m] = head[v]; edge[m] = Edge(v,u,0,0); head[v] = m++; } queue<int> q; bool bfs() { for(int i = 0; i < n; ++i) dis[i] = INF; dis[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(dis[e.v] == INF && e.c > e.f) { dis[e.v] = dis[u] + 1; q.push(e.v); } } } return dis[t] != INF; } int dfs(int u, int res) { int flow = 0, f; if(u == t || !res) return res; for(int &i = cur[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dis[e.v] == dis[u] + 1) { f = dfs(e.v,min(res,e.c - e.f)); e.f += f; edge[i^1].f -= f; flow += f; res -= f; if(!res) break; } } return flow; } int maxflow(int _s, int _t) { s = _s, t = _t; int flow = 0; while(bfs()) { for(int i = 0; i < n; ++i) cur[i] = head[i]; flow += dfs(s,INF); } return flow; } } int get[60],yi[60][60],cost[60]; bool shi[60],yiqi[60]; int main() { int m,n; scanf("%d%d",&m,&n); int s = 0, t = m + n + 1; Dinic::init(t + 1); for(int i = 1; i <= m; ++i) { yi[i][0] = 0; scanf("%d",get + i); Dinic::adde(s,i,get[i]); while(1) { char getc = getchar(); if(getc == '\n' || getc == '\r') break; scanf("%d",&yi[i][++yi[i][0]]); Dinic::adde(i,m+yi[i][yi[i][0]],INF); } } for(int i = 1; i <= n; ++i) { scanf("%d",cost+i); Dinic::adde(m+i,t,cost[i]); } int _ans = Dinic::maxflow(s,t); int ans = 0; for(int i = 1; i <= m; ++i) ans += get[i]; ans -= _ans; memset(shi,0,sizeof shi); for(int i = 0; i < Dinic::m; ++i) { if(Dinic::edge[i].u != s) continue; if(Dinic::dis[Dinic::edge[i].v] != INF) shi[Dinic::edge[i].v] = 1; } memset(yiqi,0,sizeof yiqi); for(int i = 1; i <= m; ++i) { if(!shi[i]) continue; printf("%d ",i); for(int j = 1; j <= yi[i][0]; ++j) yiqi[yi[i][j]] = 1; } puts(""); for(int i = 1; i <= n; ++i) if(yiqi[i]) printf("%d ",i); puts(""); printf("%d\n",ans); return 0; } |