题解 P2764 【最小路径覆盖问题】

· · 题解

思路

其实这道题可以用二分图水过，不用网络流。
其中，

bool find(int u){}

就是基础匈牙利算法，甚至直接用模版二分图的就可以。 为了减少篇幅，就不展开写二分图的最大匹配的定理。

但是：怎么找路径呢？

考虑存储点与点在路径上的关系：

最后找一遍路径，用paths存储所有路径，用path存储单个路径。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=155;
vector<int> G[maxn];
int match[maxn],ans=0,n,m;
bool matched[maxn];
bool find(int u){//匈牙利
    for(int v:G[u]){
        if(!matched[v]){
            matched[v]=1;
            if(!match[v]||find(match[v])){
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        memset(matched,0,sizeof(matched));
        if(find(i))ans++;
    }
    int nnode[n+1],pnode[n+1];
    memset(nnode,0,sizeof(nnode));//next，前一个
    memset(pnode,0,sizeof(pnode));//prev，后一个
    for(int v=1;v<=n;v++){
        int u=match[v];
        if(u!=0){
            nnode[u]=v;
            pnode[v]=u;
        }
    }
    bool vis[n+1];//路径是否被访问过
    memset(vis,0,sizeof(vis));//标记顶点是否已被包含在路径中
    vector<vector<int>>paths;//存储最终的所有路径
    for(int u=1;u<=n;u++){
        if(pnode[u]==0){
            vector<int> path;
            int v=u;
            while(v!=0){
                vis[v]=1;
                path.push_back(v);
                v=nnode[v];
            }
            paths.push_back(path);
        }
    }
    for(auto &path:paths){
        for(int i=0;i<path.size();i++){
            cout<<path[i]<<' ';
        }
        cout<<endl;
    }
    cout<<n-ans//即为paths.size();
    return 0;
}