poj2125最小点权覆盖

     最小点权覆盖 转化为 最小割 然后网络流。

    

　　之前有道和这个差不多的题，伞兵。不过还是做不出来，又对着书拍的。现在好像懂了怎么建图了。 s-u-v-t若不被割开则存在 u-v 没被取到。

还是拆点，拆成出点和入点。注意图不要建反了，是出点集指向入点集 。  

     输出路径。这题因为最小割 不是在左边的边，就是在右边的边，所以 从源点对残余网络dfs 。  左边走不到的全是所求的出点的集合，右边能走到的全是入点的集合。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <string>
#include <iostream>
#include <map>
#include <cstdlib>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include<math.h>
using namespace std;
int s;int e1;
const int maxn=211;
int n;
const int INF=0xfffffff;
int Min(int a,int b)
{
    return a>b?b:a;
}
int level[maxn];
struct edge
{
    int val;int to;int next;int op;
}e[111111];

int len;int head[maxn];

void add(int from,int to,int val)
{
    e[len].to=to;e[len].val=val;
    e[len].next=head[from];
    e[len].op=len+1;
    head[from]=len++;
    e[len].to=from; e[len].val=0;
    e[len].next=head[to];
    e[len].op=len-1;
    head[to]=len++;
}

bool bfs()
{
    memset(level,0,sizeof(level));
    level[s]=1;
    int q[maxn*3]; int l=0;int r=0;
    q[r++]=s;
    while(l<r){
        int cur=q[l++];
        for(int i=head[cur];i!=-1;i=e[i].next){
            int cc=e[i].to;
            if(!e[i].val) continue;
            if(!level[cc]){
                level[cc]=level[cur]+1;
                q[r++]=cc;
            }
        }
    }
    return level[e1];
}

int dfs(int x,int val)
{
    if(x==e1) return val;
    int sum=0;
    for(int i=head[x];i!=-1&&val;i=e[i].next){
        int cc=e[i].to;
        if(!e[i].val) continue;
        if(level[cc]==level[x]+1){
            int t=dfs(cc,Min(val,e[i].val));
            e[i].val-=t;e[e[i].op].val+=t;
            sum+=t;val-=t;
        }
    }
    if(sum==0) level[x]=-1;
    return sum;
}

int dinic()
{
    int ans=0;int t;
    while(bfs()){
        while(t=dfs(s,INF)) ans+=t;
    }
    return ans;
}
int ha[maxn*2];
void Hash(int x)
{
    ha[x]=1;
    for(int i=head[x];i!=-1;i=e[i].next){
        int cc=e[i].to;
        if(!e[i].val) continue;
        if(!ha[cc]){
            Hash(cc);
        }
    }
}

void solve()
{
    int ans=dinic();
    vector<int> q;
    printf("%d
",ans);
    Hash(0);
    for(int i=1;i<=n;i++){
        if(!ha[i]) q.push_back(i);
        if(ha[i+n]) q.push_back(i+n);
    }
    int t=q.size();
    printf("%d
",t);
    for(int i=0;i<t;i++)
        if(q[i]<=n) printf("%d -
",q[i]);
    else  printf("%d +
",q[i]-n);
}
int main()
{
    int m;
    while(scanf("%d%d",&n,&m)!=EOF){
        len=0;
        s=0;e1=2*n+1;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++){
            int tt;scanf("%d",&tt);
            add(i+n,e1,tt);
        }
        for(int i=1;i<=n;i++){
            int tt;scanf("%d",&tt);
            add(s,i,tt);
        }
        for(int i=0;i<m;i++){
            int a;int b;
            scanf("%d%d",&a,&b);
            add(a,b+n,INF);
        }
        solve();
    }
    return 0;

}