POJ 2125 Destroying The Graph 题解【最小点权覆盖集】【网络流】【最小割方案】

点击量：208

这个题的主要难点是最小割输出方案。

目录

Description

Alice and Bob play the following game. First, Alice draws some directed graph with $ N$ vertices and $ M$ arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex.

Alice assigns two costs to each vertex: $ Wi^+$ and $ Wi^-$. If Bob removes all arcs incoming into the $ i$-th vertex he pays $ Wi^+$ dollars to Alice, and if he removes outgoing arcs he pays $ Wi^-$ dollars.

Find out what minimal sum Bob needs to remove all arcs from the graph.

Input

Input file describes the graph Alice has drawn. The first line of the input file contains $ N$ and $ M (1\le N\le 100, 1\le M\le 5000)$. The second line contains $ N$ integer numbers specifying $ Wi^+$. The third line defines $ Wi^-$ in a similar way. All costs are positive and do not exceed $ 10^6$ . Each of the following $ M$ lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print $ W$ — the minimal sum Bob must have to remove all arcs from the graph. On the second line print $ K$ — the number of moves Bob needs to do it. After that print $ K$ lines that describe Bob’s moves. Each line must first contain the number of the vertex and then ‘+’ or ‘-‘ character, separated by one space. Character ‘+’ means that Bob removes all arcs incoming into the specified vertex and ‘-‘ that Bob removes all arcs outgoing from the specified vertex.

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5
3
1 +
2 -
2 +

Source

Northeastern Europe 2003, Northern Subregion

题意：

给出一个有向图，可能有重边和自环。现在你需要对点进行操作，每次可以删除某点的所有出边或入边，删除一个点的出边和入边分别有代价$ Wi^-,Wi^+$。请你求出最小代价，并输出方案。

题解：

因为每条边都要被它的来源或去向删掉，因此可以联想到最小点权覆盖集，和poj 3308 Paratroopers的想法比较类似。

一个点可以分别操作其来源和去向，我们把每个点$ i$分成$ i$和$ i’$。令点$ i$只连出边，点$ i’$只连入边，然后把所有的$ i$与源点相连，边权为相应的$ Wi^-$（注意这里入边是$ +$，出边是$ -$），所有$ i’$与汇点相连，边权为相应的$ Wi^+$。

此时跑最大流就是第一问的答案了。

考虑输出方案。

最小点权覆盖的实质是最小割，只有割边才有意义，当一条边流量为$ 0$时代表进行了这个操作。我们只要求出所有的割边，就能找到促成这个题最优解的方案。

我们从源点开始dfs，标记找到的点$ vis=1$，当一条边两侧的$ vis$值不一样时，这条边就是割边。注意一对点只能被计算一次，因为这个题有重边（样例）。而在最小点权覆盖集的建图中，割边只可能出现在与源点或汇点相连的边，因此这里只需要一个额外的$ used$就可以了。

最后注意要先输出边数再输出方案，比较稳的做法是检索两次，这个题就结束了。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[20000];
int head[250],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0);
    head[to]=ecnt;
}
int d[250],q[250];
bool bfs()
{
    int l=0,r=0;
    memset(d,0,sizeof(d));
    q[++r]=233;
    d[233]=1;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i^1].v&&!d[e[i].n])
            {
                d[e[i].n]=d[x]+1;
                q[++r]=e[i].n;
            }
    }
    return d[0]>0;
}
int dinic(int x,int in)
{
    if(x==233)
        return in;
    int flow=in;
    for(int i=head[x];flow&&~i;i=e[i].nxt)
        if(e[i].v&&d[e[i].n]==d[x]-1)
        {
            int tmp=dinic(e[i].n,Min(e[i].v,flow));
            if(!tmp)
                d[e[i].n]=0;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
            flow-=tmp;
        }
    return in-flow;
}
bool vis[250],used[250];
void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].v&&!vis[e[i].n])
            dfs(e[i].n);
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        add(n+i,233,u);
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        add(0,i,u);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,n+v,0x3fffffff);
    }
    int ans=0;
    while(bfs())
    {
        int tmp;
        do
        {
            tmp=dinic(0,0x3fffffff);
            ans+=tmp;
        }while(tmp);
    }
    printf("%d\n",ans);
    dfs(0);
    ans=0;
    for(int i=head[0];~i;i=e[i].nxt)
        if(!vis[e[i].n]&&!used[e[i].n])
            ++ans,used[e[i].n]=1;
    for(int i=head[233];~i;i=e[i].nxt)
        if(vis[e[i].n]&&!used[e[i].n])
            ++ans,used[e[i].n]=1;
    printf("%d\n",ans);
    memset(used,0,sizeof(used));
    for(int i=head[0];~i;i=e[i].nxt)
        if(!vis[e[i].n]&&!used[e[i].n])
            printf("%d -\n",e[i].n),used[e[i].n]=1;
    for(int i=head[233];~i;i=e[i].nxt)
        if(vis[e[i].n]&&!used[e[i].n])
            printf("%d +\n",e[i].n-n),used[e[i].n]=1;
    return 0;
}