最大权闭合子图 同上一篇blog
Code:
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<iostream> 5 #include<algorithm> 6 #define ms(a,b) memset(a,b,sizeof a) 7 #define rep(i,a,n) for(int i = a;i <= n;i++) 8 #define per(i,n,a) for(int i = n;i >= a;i--) 9 #define inf 2147483647 10 using namespace std; 11 typedef long long ll; 12 typedef double D; 13 #define eps 1e-8 14 ll read() { 15 ll as = 0,fu = 1; 16 char c = getchar(); 17 while(c < '0' || c > '9') { 18 if(c == '-') fu = -1; 19 c = getchar(); 20 } 21 while(c >= '0' && c <= '9') { 22 as = as * 10 + c - '0'; 23 c = getchar(); 24 } 25 return as * fu; 26 } 27 const int N = 225; 28 const int M = 50005; 29 //head 30 int s = N-2,t = N-1; 31 int head[N],nxt[M],mo[M],cnt = 1; 32 ll cst[M]; 33 void _add(int x,int y,ll w) { 34 mo[++cnt] = y; 35 cst[cnt] = w; 36 nxt[cnt] = head[x]; 37 head[x] = cnt; 38 } 39 void add(int x,int y,ll w) { 40 if(x^y) _add(x,y,w),_add(y,x,0); 41 } 42 43 int dep[N],cur[N]; 44 bool bfs() { 45 queue<int> q; 46 memcpy(cur,head,sizeof cur); 47 ms(dep,0),q.push(s),dep[s] = 1; 48 while(!q.empty()) { 49 int x = q.front(); 50 q.pop(); 51 for(int i = head[x];i;i = nxt[i]) { 52 int sn = mo[i]; 53 if(!dep[sn] && cst[i]) { 54 dep[sn] = dep[x] + 1; 55 q.push(sn); 56 } 57 } 58 } 59 return (bool)dep[t]; 60 } 61 62 ll dfs(int x,ll flow) { 63 if(x == t || flow == 0ll) return flow; 64 ll res = 0; 65 for(int &i = cur[x];i;i = nxt[i]) { 66 int sn = mo[i]; 67 if(dep[sn] == dep[x] + 1 && cst[i]) { 68 ll d = dfs(sn,min(cst[i],flow - res)); 69 if(d) { 70 cst[i] -= d,cst[i^1] += d; 71 res += d; 72 if(res == flow) break; 73 } 74 } 75 } 76 if(res ^ flow) dep[x] = 0; 77 return res; 78 } 79 80 ll DINIC() { 81 ll ans = 0; 82 while(bfs()) ans += dfs(s,inf); 83 return ans; 84 } 85 int n,m; 86 int main() { 87 n = read(),m = read(); 88 ll x,sum = 0; 89 rep(i,1,n) { 90 x = read(); 91 add(s,i,x),sum += x; 92 x = read(); 93 while(x) add(i,x+105,inf),x = read(); 94 } 95 rep(i,1,m) add(i+105,t,read()); 96 printf("%lld ",sum - DINIC()); 97 return 0; 98 }