P2764【最小路径覆盖】

Plus_Ultra · 2019-09-07 20:51:35 · 题解

题解：

网络流24题，蒟蒻用匈牙利算法一遍就水过了

解法：

稍微思考一下，就可以得出这道题要求什么：有向无环图的最小路径点覆盖.
有向无环图的最小路径点覆盖：
- 给定一张DAG(有向无环图)，要求用最少的简单路径（互不相交），覆盖DAG上的所有顶点（每个顶点恰好被覆盖一次），这个问题被称为有向无环图的最小路径点覆盖.
引出定理：DAG的最小路径点覆盖包含的路径条数 = n - 拆点二分图的最大匹配数.（别问我为啥蒟蒻也不知道QwQ).
拆点二分图：
- 把每个点拆成编号为 i 和 i + n 的两个点.建立一张新的二分图， 1 ~ n 是左部子集， n + 1 ~ 2n 是右部子集.对原图的每条有向边 (u,v) ，在二分图的左部子集 u 与右部子集 v + n 之间连边.这样得到的二分图成为原图的拆点二分图.
于是我们可以用匈牙利算法来求解这个问题.
不懂匈牙利算法的盆友看这里！！！

下面上代码（我知道各位大佬也不需要代码）：

#include<iostream>
#include<cstring>

#define N 310
#define M 12010

using namespace std;

int T,n,m,x,y,mat[N],vis[N],ans;
int edge[M],nxt[M],head[M],tot;//数组要开够啊qwq 

void add(int x,int y)//邻接表 
{
    edge[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

int match(int x)//找匹配 
{
    for(int i=head[x];i;i=nxt[i])//遍历相连边 
    {
        int y=edge[i];
        if(!vis[y])//没有访问过 
        {
            vis[y]=1;
            if(!mat[y]||match(mat[y]))//还没有匹配或者能找到替换路 
            {
                mat[y]=x,mat[x]=y;//记得这儿要记录双向匹配，输出时要用啊 
                return 1;//找到 
            }
        }
    }
    return 0;
}

void write(int x)
{
    x+=n;//变成右部子集对应点 
    while(x)
    {
        cout<<x-n<<" ";//输出时当然要-n 
        vis[x-n]=1;//已经访问 
        x=mat[x-n];//下一个路径上的点 
    }
    cout<<endl;
}//这儿不会 

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        add(x,y+n);//这里是拆点操作 
    }

    for(int i=1;i<=n;i++)
    ans+=match(i),memset(vis,0,sizeof(vis));//记得初始化哟 

    for(int i=1;i<=n;i++)//输出路径 
        if(!vis[i])  write(i);
    cout<<n-ans<<endl;//定理 

    return 0;
}

P2764【最小路径覆盖】

题解：

Plus Ultra!!!