最小路径覆盖问题

· · 题解

最小路径覆盖问题

题目:自己康

!文章已更新

写在前面:个人感觉本篇题解比大多数题解更为简单 更易理解(dalao勿喷

解法:我们对于这一道题

首先 应该理解题意 我们要在一个DAG中找到最少的边可以链接所有的点 (样例数据)如下图:

所以 我们可以得到最小路径覆盖(最小边覆盖)=原图的结点数-新图的最大匹配数
进而 我们可以先求出新图的最大匹配数
然后 在通过匹配关系 找到这样的路径
对于建图 我们可以把一个点变为两个 左边为实点(实际的点) 右边为虚电(实点中对应点的映射)
我们根据每次读入 把x->y其中x作为实点,y作为虚点连接起来 这样我们可以得到下面这样一个图

最后 输出答案时 我们遍历所有的实点 如果它没有走过 就从它开始走即可
如果我们发现 当前点的下一个点(虚点)对应的实点没有走过
那么我们就从从这个实点开始继续走 直到所有的点都被遍历完

代码酱 OVO↓

#include <bits/stdc++.h>
using namespace std;

#define N 3000001
#define v to[i]
#define inf 0x7f7f7f7f

int n,m,s,t;
int dep[N],vis[N];
int head[N],to[N],from[N],nex[N],w[N],ecnt;

void ae(int x,int y,int z){
    from[ecnt]=x;
    to[ecnt]=y;
    w[ecnt]=z;
    nex[ecnt]=head[x];
    head[x]=ecnt++;
}

bool bfs(){
    memset(dep,-1,sizeof(dep));
    queue<int> q;
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=nex[i]){
            if(dep[v]==-1 and w[i]>0){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}

int dfs(int u,int low){
    if(u==t)
        return low;
    int ret=low;
    for(int i=head[u];i!=-1;i=nex[i]){
        if(dep[v]==dep[u]+1 and w[i]>0){
            int flow=dfs(v,min(ret,w[i]));
            if(flow>0){
                w[i]-=flow;
                w[i^1]+=flow;
            }
            ret-=flow;
            if(!ret)
                break;
        }
    }
    return low-ret;
}

int dinic(){
    int res=0;
    while(bfs()){
        res+=dfs(s,inf);
    }
    return res;
}

void work(int u){//当前点
    if(vis[u]){//如果当前点以访问过 就返回
        return;
    }
    printf("%d ",u);//输出当前的节点
    vis[u]=1;
    for(int i=head[u];i!=-1;i=nex[i]){
        if(!w[i] and v!=s){
            if(!vis[v-n])//v得到的是虚点 我们应找的是v对应的实点 所以减去n
                work(v-n);//从下一点向下继续找
        }
    }
} 

void pre(){
    scanf("%d%d",&n,&m);
    int t1,t2;
    s=0,t=n*2+1;
    for(int i=1;i<=n;i++){
        ae(s,i,1);
        ae(i,s,0);
        ae(i+n,t,1);
        ae(t,i+n,0);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&t1,&t2);
        ae(t1,n+t2,1);
        ae(n+t2,t1,0);
    }
}

int main(){
    memset(head,-1,sizeof(head)); 
    pre();
    int ans=dinic();
    for(int i=1;i<=n;i++){//从1开始遍历每个点
        if(!vis[i]){//如果这个点没找过了 就从这个点开始找 
            work(i);
            printf("\n");//注意要换行
        }
    }
    printf("%d\n",n-ans);//最小覆盖边=总结点数-最大匹配数
    return 0;
}