线性规划与网络流之2 最大权闭合图

题目：http://www.byvoid.com/blog/lpf24-solution/

分析

按照题意，可以构建一个二分图，然后我们可以发现这是一个依赖关系的最大权取值问题。所以直接套用《最小割模型在信息学竞赛中的应用》里的最大权闭合图模型解决。

code:

#include #define E 1000001
#define N 1001
#define Maxnum 1000000000
int m,n,x[E],y[E],next[E],c[E],op[E],ls[N],d[N],fa[N],num[N],cur[N],vs,vt,e=0,s=0,flow=0;

void add(int X,int Y,int C){
     e++;
     x[e]=X; y[e]=Y; c[e]=C; next[e]=ls[X]; ls[X]=e; op[e]=e+1;
     e++;
     x[e]=Y; y[e]=X; c[e]=0; next[e]=ls[Y]; ls[Y]=e; op[e]=e-1;
}

void init(){
     scanf("%d%d",&m,&n);
     vs=0; vt=m+n+1;
     char ch;
     for (int i=1;i<=m;i++){
         int t;
         scanf("%d",&t);
         s+=t;
         add(vs,i,t);
         while (scanf("%c",&ch)!=EOF && ch!=’n’){
               scanf("%d",&t);
               add(i,m+t,Maxnum);
         }
     }
     for (int i=1;i<=n;i++){
         int t;
         scanf("%d",&t);
         add(m+i,vt,t);
     }
}

void relabel(int k){
     int min=vt,i=ls[k];
     cur[k]=ls[k];
     while (i>0){
       if (c[i]>0 && d[y[i]]       i=next[i];
     }
     d[k]=min+1;
}

void change(){
     int i=vt,nf=Maxnum;
     while (i!=vs){
           if (c[fa[i]]           i=x[fa[i]];
     }
     flow+=nf;
     i=vt;
     while (i!=vs){
           c[fa[i]]-=nf;
           c[op[fa[i]]]+=nf;
           i=x[fa[i]];
     }
}

void sap(){
     for (int i=vs;i<=vt;i++){
         num[i]=0;
         d[i]=0;
         cur[i]=ls[i];
     }
     num[0]=vt+1;
     int i=vs;
     while (d[vs]           while (cur[i]>0)
             if (d[x[cur[i]]]==d[y[cur[i]]]+1 && c[cur[i]]>0)
               break;
             else
               cur[i]=next[cur[i]];
           if (cur[i]==0){
              num[d[i]]–;
              if (num[d[i]]==0) break;
              relabel(i);
              num[d[i]]++;
              if (i!=vs) i=x[fa[i]];
           }
           else{
              fa[y[cur[i]]]=cur[i];
              i=y[cur[i]];
              if (i==vt){
                 change();
                 i=vs;
              }
           }
     }
}

int main(){
    freopen("shut10.in","r",stdin);
    freopen("shut10.ans","w",stdout);
    init();
    sap();
    printf("%dn",s-flow);
}