SSL 2603_最小路径覆盖问题_网络流

发布于 2019-05-16  8 次阅读


题目大意

给出一个图,求出最小路径覆盖


思路

最小路径覆盖=总点数-最大匹配
用全部点建一个二分图然后跑一遍最大流,记录下每一个点的路径,然后输出即可


#include 
#include 
#include 
#define maxn 20000
#define fill(x,y) memset(x,y,sizeof(x))
#define min(x,y) x t;
    t.push(x);
    fill(state,63);
    state[x]=0;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&state[tt]+10)
        {
            int d=find(e[i].y,min(mn,e[i].w));
            if (d>0)
            {
                e[i].w-=d;
                e[e[i].rev].w+=d;
                vis[x]=e[i].y;
                return d;
            }
        }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y+n,1);
    }
    for (int i=1;i<=n;i++)
    {
        add(0,i,1);
        add(n+i,n+n+1,1);
    }
    int ans=0;

    while (bfs(0))
    {
        int d=find(0,INF);
        ans+=d;
    }

    for (int i=1;i<=n;i++)
    {
        if (vis[i]!=0)
        {
            int t=i;
            do
            {
                if (t>n) t-=n;
                printf("%d ",t);
                int x=vis[t];
                vis[t]=0;
                t=x;
            }
            while (t!=0);
            printf("\n");
        }
    }
    printf("%d\n",n-ans);
}
]]>