hdu 3996 (最大權閉合圖)

題意：有n個區域布局，每個區域有一些金礦，挖開金礦需要一定的費用，可以得到一定的利潤，要想挖開一個金礦，必須挖開所有在這個金礦上邊的金礦，求最大利益，給的數據價值太大，用64位。

分析：如果一個金礦可以獲利，就從源點引一條邊，容量為獲得的利益，否則向匯點引一條邊，容量為損耗，一個金礦向所有的必須在它之前開發的金礦連邊，容量為無窮大。求出最大流就是最小損耗，，，

#include<stdio.h>
#include<string.h>
const int N=2600;
const __int64 inf=0x3fffffffffffffff;
int dis[N],gap[N],head[N],num,start,end,ans;
struct edge
{
    int st,ed,next;
    __int64 flow;
}e[N*100];
void addedge(int x,int y,__int64 w)
{
    e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;
    e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
__int64 dfs(int u,__int64 minflow)
{
    if(u==end)return minflow;
    int i,v,min_dis=ans-1;
    __int64 f,flow=0;
    for(i=head[u];i!=-1;i=e[i].next)
    {
        if(e[i].flow<=0)continue;
        v=e[i].ed;
        if(dis[v]+1==dis[u])
        {
            f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow);
            e[i].flow-=f;
            e[i^1].flow+=f;
            flow+=f;
            if(flow==minflow)break;
            if(dis[start]>=ans)return flow;
        }
        min_dis=min_dis>dis[v]?dis[v]:min_dis;
    }
    if(flow==0)
    {
        if(--gap[dis[u]]==0)
            dis[start]=ans;
        dis[u]=min_dis+1;
        gap[dis[u]]++;
    }
    return flow;
}
__int64 isap()
{
    __int64 maxflow=0;
    memset(dis,0,sizeof(head));
    memset(gap,0,sizeof(gap));
    gap[0]=ans;
    while(dis[start]<ans)
        maxflow+=dfs(start,inf);
    return maxflow;
}
int main()
{
    int i,j,n,m,t,x,y,w,op=1;
    __int64 sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        num=0;start=0;end=n*25+1;sum=0;ans=end+1;
        for(i=0;i<n;i++)
        {
            scanf("%d",&m);
            for(j=1;j<=m;j++)
            {
                scanf("%d%d%d",&x,&y,&w);
                if(y-x>=0)
                {
                    addedge(start,i*25+j,y-x);
                    sum+=y-x;
                }
                else addedge(i*25+j,end,x-y);
                while(w--)
                {
                    scanf("%d%d",&x,&y);
                    addedge(i*25+j,(x-1)*25+y,inf);
                }
            }
        }
        printf("Case #%d: %I64d\n",op++,sum-isap());
    }
    return 0;
}