最大权闭合子图 同上一篇blog
Code:
1 #include2 #include 3 #include 4 #include 5 #include 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 214748364710 using namespace std;11 typedef long long ll;12 typedef double D;13 #define eps 1e-814 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 //head30 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 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\n",sum - DINIC());97 return 0;98 }