最小路径覆盖问题

给一个有向无环图,要求你用最少的路径(所有路径不重复经过一个点)包含图中所有点,最少需要几条路径。
最小边覆盖=总数-最大匹配。先一开始当n条,然后考虑路径合并,每有两条路径合在一起,那么覆盖数就-1。所以,将点拆成x和y,源点向x连1,y向汇点连1,然后把给的边从x连到y,这样跑出的最大流即是路径合并的数量,减一下即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const ll maxm = 100000;
struct Edge{
    ll from, to, cap, flow;
    Edge(){
    }
    Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}    
};
struct Edge1
{
    ll from, to; ll dist;       //起点,终点,距离
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
    ll n, m, s, t;
    vector<Edge>edges;
    vector<ll>G[MAXN];
    ll d[MAXN];
    ll cur[MAXN];
    ll vis[MAXN];
    void init(ll n, ll s, ll t)
    {
        this->n = n;this->s = s;this->t = t;
        edges.clear();
        for(ll i = 0;i <= n;++i) G[i].clear();
    }
    
    void add_edge(ll from, ll to, ll cap)
    {
        edges.push_back( Edge(from, to, cap, 0) );
        edges.push_back( Edge(to, from, 0, 0) );
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1); 
    }
    
    bool bfs(){
        memset(vis, 0, sizeof(vis));
        queue<ll>Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        while(!Q.empty())
        {
            ll x = Q.front();
            Q.pop();
            for(ll i = 0;i < G[x].size();++i)
            {
                Edge& e = edges[G[x][i]];
                if(!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }       
        }
        return vis[t];
    }
    ll dfs(ll x,ll a)
    {
        if(x == t || a == 0)return a;
        ll flow = 0, f;
        for(ll& i = cur[x];i < G[x].size();++i)
        {
            Edge& e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to] && (f = dfs( e.to, min(a, e.cap-e.flow)))>0)
            {
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                a -= f;
                if(a == 0)break; 
            }
        }
        return flow;
    }
    ll maxflow()
    {
        ll flow = 0;
        while(bfs())
        {
            memset(cur, 0, sizeof(cur));
            flow += dfs(s,inf);
        }
        return flow;
    }
}gao;//刘汝佳网络流dinic板子
int fa[305];
int find(int x)
{
    if(fa[x]!=x){
        return fa[x]=find(fa[x]);
    }
    return x;
}
void uni(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if(x1!=y1){
        fa[y1]=x1;
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    gao.init(n*2+2,n*2+1,n*2+2);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        gao.add_edge(x,n+y,1);
    }
    for(int i=1;i<=2*n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        gao.add_edge(n*2+1,i,1);
        gao.add_edge(i+n,n*2+2,1);
    }
    int ans=n-gao.maxflow();
    for(int i=0;i<gao.edges.size();i++){
        Edge k=gao.edges[i];
        if(k.from<=n&&k.from>=1&&k.to<=n*2&&k.to>n&&k.flow==1){
            uni(k.from,k.to-n);
        }
    }
    for(int i=1;i<=n;i++){
        if(find(i)==i){
            for(int j=1;j<=n;j++){
                if(find(j)==i){
                    printf("%d ",j);
                }
            }
            printf("\n");
        }
    }
    printf("%d\n",ans);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注