HDU3996 Gold Mine 最大闭合权

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3996
　　很无语加蛋碎的题目！题意描述不清，然后还有超int（这里wa，果断被坑）= =！方法很简单，很容易看出是最大闭合权。
  1 //STATUS:G++_AC_109MS_2068KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL __int64
 15 #define pii pair<int,int>
 16 #define Max(a,b) ((a)>(b)?(a):(b))
 17 #define Min(a,b) ((a)<(b)?(a):(b))
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int MAX=2510,INF=0x3f3f3f3f;
 22 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
 23 
 24 struct Edge{
 25     int u,v;
 26     LL cap;
 27 };
 28 
 29 vector<Edge> e;
 30 vector<int> g[MAX];
 31 int d[MAX],cur[MAX],p[MAX],num[MAX],val[MAX],ma[110][25],li[MAX][55][2],cou[MAX];
 32 int n,m,k,T,s,t,mt;
 33 
 34 void adde(int a,int b,LL val){
 35     e.push_back((Edge){a,b,val});
 36     g[a].push_back(mt++);
 37     e.push_back((Edge){b,a,0});
 38     g[b].push_back(mt++);
 39 }
 40 
 41 LL augment()
 42 {
 43     int x=t;
 44     LL a=LLNF;
 45     while(x!=s){
 46         a=Min(a,e[p[x]].cap);
 47         x=e[p[x]].u;
 48     }
 49     x=t;
 50     while(x!=s){
 51         e[p[x]].cap-=a;
 52         e[p[x]^1].cap+=a;
 53         x=e[p[x]].u;
 54     }
 55     return a;
 56 }
 57 
 58 LL isap()
 59 {
 60     int i,x,ok,min;
 61     LL flow=0;
 62     mem(d,0);mem(num,0);
 63     num[0]=t+1;
 64     mem(cur,0);
 65     x=s;
 66     while(d[s]<=t){
 67         if(x==t){
 68             flow+=augment();
 69             x=s;
 70         }
 71         ok=0;
 72         for(i=cur[x];i<g[x].size();i++){
 73             Edge& et=e[g[x][i]];
 74             if(et.cap && d[x]==d[et.v]+1){
 75                 ok=1;
 76                 p[et.v]=g[x][i];
 77                 cur[x]=i;
 78                 x=et.v;
 79                 break;
 80             }
 81         }
 82         if(!ok){
 83             min=t;
 84             for(i=0;i<g[x].size();i++){
 85                 Edge& et=e[g[x][i]];
 86                 if(et.cap && d[et.v]<min)min=d[et.v];
 87             }
 88             if(--num[d[x]]==0)break;
 89             num[d[x]=min+1]++;
 90             cur[x]=0;
 91             if(x!=s)x=e[p[x]].u;
 92         }
 93     }
 94     return flow;
 95 }
 96 
 97 void bfs()
 98 {
 99     int x,i,j;
100     mem(d,0);
101     queue<int> q;
102     q.push(s);
103     d[s]=1;
104     while(!q.empty()){
105         x=q.front();q.pop();
106         for(i=0;i<g[x].size();i++){
107             Edge& et=e[g[x][i]];
108             if(et.cap && !d[et.v]){
109                 d[et.v]=1;
110                 q.push(et.v);
111             }
112         }
113     }
114 }
115 
116 int main()
117 {
118   //  freopen("in.txt","r",stdin);
119     int i,j,q,x,y,ca=0;
120     LL ans;
121     scanf("%d",&T);
122     while(T--)
123     {
124         k=mt=ans=0;
125         e.clear();
126         scanf("%d",&n);
127         for(i=1;i<=n;i++){
128             scanf("%d",&m);
129             for(j=1;j<=m;j++){
130                 ++k;
131                 scanf("%d%d%d",&x,&y,&cou[k]);
132                 val[k]=y-x;
133                 ma[i][j]=k;
134                 for(q=1;q<=cou[k];q++)
135                     scanf("%d%d",&li[k][q][0],&li[k][q][1]);
136             }
137         }
138         s=0,t=k+1;
139         for(i=0;i<=t;i++)g[i].clear();
140         for(i=1;i<=k;i++){
141             if(val[i]>0)adde(s,i,val[i]);
142             else if(val[i]<0)adde(i,t,-val[i]);
143             for(j=1;j<=cou[i];j++)
144                 adde(i,ma[li[i][j][0]][li[i][j][1]],LLNF);
145         }
146 
147         isap();
148         bfs();
149         for(i=1;i<=k;i++)
150             if(d[i]>0)ans+=val[i];
151         printf("Case #%d: %I64d\n",++ca,ans);
152     }
153     return 0;
154 }