题意：挖金矿。一个矿有n层，每层有m块金子。要挖每块金子都有一个代价cost，每块金子都有一个价值cost，另外每块金子还有w个关系，表示如果要挖它，必须先挖掉第i层的第j块金子，求最大获利。
最大闭合子图。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 3010 5 #define maxm 400000 6 using namespace std; 7 typedef long long LL; 8 const LL INF = 1LL<<60; 9 int v[maxm],next[maxm]; 10 LL w[maxm]; 11 int first[maxn],q[maxn],work[maxn],d[maxn]; 12 int e,S,T; 13 14 void init(){ 15 e = 0; 16 memset(first,-1,sizeof(first)); 17 } 18 19 void add_edge(int a,int b,LL c){ 20 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 21 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 22 } 23 24 int bfs(){ 25 int rear = 0; 26 memset(d,-1,sizeof(d)); 27 d[S] = 0;q[rear++] = S; 28 for(int i = 0;i < rear;i++){ 29 for(int j = first[q[i]];j != -1;j = next[j]) 30 if(w[j] && d[v[j]] == -1){ 31 d[v[j]] = d[q[i]] + 1; 32 q[rear++] = v[j]; 33 if(v[j] == T) return 1; 34 } 35 } 36 return 0; 37 } 38 39 LL dfs(int cur,LL a){ 40 if(cur == T) return a; 41 for(int &i = work[cur];i != -1;i = next[i]){ 42 if(w[i] && d[v[i]] == d[cur] + 1) 43 if(LL t = dfs(v[i],min(a,w[i]))){ 44 w[i] -= t,w[i^1] += t; 45 return t; 46 } 47 } 48 return 0; 49 } 50 51 LL dinic(){ 52 LL ans = 0; 53 while(bfs()){ 54 memcpy(work,first,sizeof(first)); 55 while(LL t = dfs(S,INF)) ans += t; 56 } 57 return ans; 58 } 59 60 int main() 61 { 62 int n,m,t; 63 scanf("%d",&t); 64 for(int kase = 1;kase <= t;kase++){ 65 init(); 66 S = 0,T = 3000; 67 LL sum = 0; 68 scanf("%d",&n); 69 for(int i = 1;i <= n;i++){ 70 scanf("%d",&m); 71 for(int j = 1;j <= m;j++){ 72 int pos = i*26+j; 73 LL cost,value; 74 int ww; 75 scanf("%I64d%I64d%d",&cost,&value,&ww); 76 value -= cost; 77 if(value > 0) add_edge(S,pos,value),sum += value; 78 if(value < 0) add_edge(pos,T,-value); 79 for(int k = 0;k < ww;k++){ 80 int a,b; 81 scanf("%d%d",&a,&b); 82 add_edge(pos,a*26+b,INF); 83 } 84 } 85 } 86 printf("Case #%d: %I64d ",kase,sum-dinic()); 87 } 88 return 0; 89 }