最小路径覆盖问题

detect · 2019-07-19 11:08:08 · 个人记录

题目传送门

考虑答案数为总点数-最大可合并点数，故考虑建图求解最大可并点，因为每个点经过一次，所以点与点连1的边，然后入点和出点连每一个点1的边，当然入点出点连的边是一个点断成的的两个点，然后给出边的作用是连接断成的两个点。

这样一来，每个点只能指向一条边，一个点也只能被指向一条边，才能保证图是按照路径分隔开来。我们希望被合并的点最多，于是喜闻乐见的最大流派上用场。

关于保持答案，我们每一次增广时，更新对应匹配点（每个点只会有一个），最后链表输出即可

此题告诉我们网络流还可以处理一些可合并问题。

#include<bits/stdc++.h>
using namespace std;
int head[100000],bi=1,n,m,S,T,lev[100000],vis[100000],nex[100000],pre[100000],last[100000],go[100000],w[100000];
void add(int x,int y,int v)
{
    nex[++bi]=head[x];
    head[x]=bi;
    go[bi]=y;
    w[bi]=v;
}
bool bfs()
{
    memset(lev,-1,sizeof(lev));
    lev[S]=0;
    queue <int> q;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();
        //cout<<u<<" ";
        q.pop();
        for(int i=head[u];i;i=nex[i])
        {
            int v=go[i];
            if(w[i]&&lev[v]==-1)
            {
                lev[v]=lev[u]+1;
                q.push(v);
            }
        }
    }
    return lev[T]!=-1;
}
int dfs(int u,int flow)
{
    if(u==T) return flow;
    int res=0,sum=0;
    for(int i=head[u];i;i=nex[i])
    {
        int v=go[i];    
        if(lev[v]==lev[u]+1&&w[i])
        {
            sum=dfs(v,min(flow-res,w[i]));
            if(sum)
            {
                pre[u]=v;//从小到大链表 
                if(u!=S)//与根相连的肯定不在一起 
                {
                    //cout<<"*"<<v-n<<endl;
                    vis[v-n]=1;
                }
                w[i]-=sum;
                w[i^1]+=sum;
                res+=sum;
            }
        }
    }
    return res;
}
signed main()
{
    cin>>n>>m;
    S=0;
    T=2*n+1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y+n,1);
        add(y+n,x,0);
    }
    for(int i=1;i<=n;i++)
    {
        add(S,i,1);
        add(i,S,0);
        add(i+n,T,1);
        add(T,i+n,0);//建边 
    }
    long long ans=0;
    while(bfs())
    {
        ans+=dfs(S,1e9);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)//可以为链的头 
        {
            int now=i;
            cout<<now<<" ";
            while(pre[now]!=T&&pre[now])//还没到头还可以链表 
            {
                cout<<(pre[now]-n)<<" ";//注意断点与原点编号区别 
                now=pre[now]-n;
            }
            cout<<endl;
        }
    }
    cout<<n-ans;
    return 0;   
}