「网络流 24 题」最小路径覆盖
题解:将原图中所有的点拆成Xi和Yi,然后建立一个源点和一个汇点,从源点向每个Xi连接一条容量为1的边,从Yi向汇点连接一条容量为1的边,如果原图中有一条从u连向v的边,那么在建立的图中从Xu向Yv连接一条容量为1的边,对该二分图跑一遍最大流就好了。

方案输出:从每一个之前没被走过的点,开始沿着从Xu到Yv再到Xv沿着满流的边将所有的点输出则为一条路径

证明:每一个点可以看作一条长度为0的一条路径,那么对应的二分图两点匹配也就是原图中两条路径和为一条路径,所以二分图的最大匹配,就是原图中路径的最大匹配,每两个点匹配原图中的路径数就会减少1,所以答案就是n-max_flow()

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,m,s,t,e = 2,ans,top;
int head[MAXN],cur[MAXN],d[MAXN];
bool vis[MAXN];

struct node{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w){
    edge[e] = (node){v,w,0,head[u]};head[u] = e++;
    edge[e] = (node){u,0,0,head[v]};head[v] = e++;
}

inline void init()
{
    scanf("%d%d",&n,&m);
    s = 0;t = 2*n+1;
    for(int i = 1;i <= n;i++) addedge(s,i,1);
    for(int i = 1;i <= n;i++) addedge(n+i,t,1);
    
    int u,v;
    for(int i = 1;i <= m;i++){
        scanf("%d%d",&u,&v);
        addedge(u,n+v,1);
    }
}

queue<int>Q;

inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            node &E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a)
{
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        node &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(E.c-E.f,a))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    } 
    return flow;
}

inline int mf()
{
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

void cut(int x){
    vis[x] = true;printf("%d ",x);
    for(int i = head[x];i;i = edge[i].next){
        node E = edge[i];
        if(1 <= E.v-n && E.v-n <= n && !vis[E.v-n] && E.c == E.f && E.v != 2*n+1){
            cut(E.v-n);
        }
    }
}

int main()
{
    
    init();
    ans = n - mf();
    
    for(int i = 1;i <= n;i++){
        if(!vis[i])    {
        cut(i);
        printf("\n");
        }
    }

    printf("%d\n",ans);
    
    return 0;
} 
Last modification:October 5th, 2018 at 02:39 pm
If you think my article is useful to you, please feel free to appreciate