2944. Mussy Paper
Time Limit: 2.0 Seconds Memory Limit: 65536K Special Judge
Total Runs: 381 Accepted Runs: 98
A good mathematical joke is better, and better mathematics,
than a dozen mediocre papers.
--J E Littlewood
RoBa has given every paper an interesting value (which can be negative). A greater value indicates a more interesting paper. He wants to select a paper set S, such that, for every paper in this set, all the papers in its reference list are also contained in the set S. And what‘s more, he wants to make the sum of all the interesting value in the set maximum.
The input is terminated with N = 0.
If the maximum possible sum is no more than zero, you should only output one line says "Refused" instead, which means RoBa will refuse to do this research.
4 -10 1 2 10 2 3 4 -3 0 -3 0 4 -10 1 2 -10 2 3 4 -3 0 -3 0 0
4 3 2 3 4 Refused
Problem Setter: RoBa
Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.
Source: TJU Team Selection Contest 2008 (4)
解题：最大权闭合子图
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 110; 4 const int INF = ~0U>>2; 5 struct arc { 6 int to,flow,next; 7 arc(int x = 0,int y = 0,int z = -1) { 8 to = x; 9 flow = y; 10 next = z; 11 } 12 } e[maxn*maxn]; 13 int head[maxn],gap[maxn],d[maxn],tot,S,T; 14 void add(int u,int v,int flow) { 15 e[tot] = arc(v,flow,head[u]); 16 head[u] = tot++; 17 e[tot] = arc(u,0,head[v]); 18 head[v] = tot++; 19 } 20 int dfs(int u,int low) { 21 if(u == T) return low; 22 int tmp = 0,minH = T - 1; 23 for(int i = head[u]; ~i; i = e[i].next) { 24 if(e[i].flow) { 25 if(d[u] == d[e[i].to] + 1) { 26 int a = dfs(e[i].to,min(e[i].flow,low)); 27 e[i].flow -= a; 28 e[i^1].flow += a; 29 tmp += a; 30 low -= a; 31 } 32 if(e[i].flow) minH = min(minH,d[e[i].to]); 33 if(!low) break; 34 } 35 } 36 if(!tmp) { 37 if(--gap[d[u]] == 0) d[S] = T; 38 ++gap[d[u] = minH + 1]; 39 } 40 return tmp; 41 } 42 int sap() { 43 memset(gap,0,sizeof gap); 44 memset(d,0,sizeof d); 45 gap[S] = T; 46 int ret = 0; 47 while(d[S] < T) ret += dfs(S,INF); 48 return ret; 49 } 50 int n,m; 51 bool vis[maxn]; 52 vector<int>ans; 53 void dfs(int u){ 54 vis[u] = true; 55 if(u != S && u != T) ans.push_back(u); 56 for(int i = head[u]; ~i; i = e[i].next) 57 if(!vis[e[i].to] && e[i].flow) dfs(e[i].to); 58 } 59 60 int main() { 61 while(scanf("%d",&n),n) { 62 memset(head,-1,sizeof head); 63 S = n + 1; 64 T = S + 1; 65 int sum = tot = 0,w; 66 for(int u = 1,v; u <= n; ++u) { 67 scanf("%d%d",&w,&m); 68 if(w > 0) { 69 add(S,u,w); 70 sum += w; 71 } else add(u,T,-w); 72 while(m--) { 73 scanf("%d",&v); 74 add(u,v,INF); 75 } 76 } 77 sum -= sap(); 78 if(!sum) puts("Refused"); 79 else{ 80 ans.clear(); 81 memset(vis,false,sizeof vis); 82 dfs(S); 83 printf("%d %d\n",sum,ans.size()); 84 sort(ans.rbegin(),ans.rend()); 85 for(int i = ans.size()-1; i >= 0; --i) 86 printf("%d%c",ans[i],i?‘ ‘:‘\n‘); 87 } 88 } 89 return 0; 90 }
原文：http://www.cnblogs.com/crackpotisback/p/4928918.html
