POJ 2125 最小点权覆盖（最小割）

题意：

给出N个点和M条边

再给出ai和bi。

ai表示删除i的所有入边的权值

bi表示删除i的所有出边的权值

然后给出那些边。

求怎样用最小的代价，删除所有的边。

分析：

详细的可以看amber的最小割论文

http://u.115.com/file/f7142414ae

过期的话就百度一下吧。。。

具体名字是《最小割模型在信息学竞赛中的应用》

就是最小点权覆盖（用最少的点权覆盖所有的边）

我们把每个点拆成两个点。

对于每个bi，建边(S,i,bi)

对于每个ai，建边(i+n,T,ai)

然后每条图中的边，建边(i,j+n,INF)

然后求最大流，最后求最小割即可。

插曲：

一开始ai和bi弄反了。WA到SB了

code：

#include #include #define N 100000
#define E 2000000
#define INF 0x7FFFFFFF
using namespace std;
struct edge{int x,y,c,op,next;}g[E];
int n,e=0,ls[N],fa[N],cur[N],d[N],num[N],v[N],ans[N];

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

void init(){
     memset(ls,0,sizeof(ls));
     memset(fa,0,sizeof(fa));
     memset(cur,0,sizeof(cur));
     memset(d,0,sizeof(d));
     memset(num,0,sizeof(num));
     memset(v,0,sizeof(v));
     int m,x,y;
     cin >> n >> m;
     for (int i=1;i<=n;i++){
         cin >> x;
         add(i+n,n+n+1,x);
     }
     for (int i=1;i<=n;i++){
         cin >> x;
         add(0,i,x);
     }
     for (int i=1;i<=m;i++){
         cin >> x >> y;
         add(x,y+n,INF);
     }
}

void relabel(int k){
     cur[k]=ls[k];
     int min=n+n+1;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (g[i].c>0 && d[g[i].y]     d[k]=min+1;
}

int change(){
    int nf=INF;
    for (int i=n+n+1;i!=0;i=g[fa[i]].x)
      nf=min(nf,g[fa[i]].c);
    for (int i=n+n+1;i!=0;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
    return nf;
}

int sap(){
    int flow=0;
    for (int i=0;i<=n+n+1;i++) cur[i]=ls[i];
    num[0]=n+n+2;
    int i=0;
    while (d[0]          for (;cur[i]!=0;cur[i]=g[cur[i]].next)
              if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
          if (cur[i]==0){
            if (–num[d[i]]==0) break;
            relabel(i);
            num[d[i]]++;
            if (i!=0) i=g[fa[i]].x;
          }
          else{
            fa[g[cur[i]].y]=cur[i];
            i=g[cur[i]].y;
            if (i==n+n+1){
              flow+=change();
              i=0;
            }
          }
    }
    return flow;
}

void dfs(int k){
     d[k]=1;
     v[k]=0;
     for (int i=ls[k];i!=0;i=g[i].next)
       if (d[g[i].y]==0 && g[i].c>0) dfs(g[i].y);
}

void print(){
     int t=0;
     for (int i=0;i<=N;i++) v[i]=1;
     memset(d,0,sizeof(d));
     dfs(0);
     for (int i=1;i<=e;i=i+2)
       if (v[g[i].x]==0 && v[g[i].y]==1 && g[i].c==0)
         ans[t++]=i;
     cout << t << endl;
     for (int i=0;i       if (g[ans[i]].x==0) cout << g[ans[i]].y << " -" << endl;
                      else cout << g[ans[i]].x-n<<" +" << endl;
}

int main(){
    init();
    int flow=sap();
    cout << flow << endl;
    print();
}