[网络流24题] 最小路径覆盖问题

题意

求图G的最小路径覆盖并输出路径

题解

一个忘记了很久的定理,回去翻了翻白书
|最大匹配| + |最小边覆盖| = |V|
|最大独立集| + |最小顶点覆盖| = |V|
|最大匹配| = |最小顶点覆盖|

求解最小边覆盖，只需要构造二分图找到最大匹配也就是最大流再用顶点总数减去即可。
对于路径输出。
可以记录vis数组保存某个点是否输出过。
遍历从1到n所有的点，若该点未被标记，从当前点开始寻找与该点相连并流量为0的边，并把该边的终点设置为当前点，直到当前终点已被标记，这条路径输出完成，不要忘了同时把这条路径的点标记。

code

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

const int maxn = 6000 + 10;
const int inf = 0x3f3f3f3f;
struct Edge{
    int to,cap,nxt;
}edges[maxn << 2];
int head[maxn],deep[maxn],cur[maxn],num = 0;
int vis[maxn];

void addedge(int from,int to,int cost)
{
    edges[num].nxt = head[from];
    edges[num].to = to;
    edges[num].cap = cost;
    head[from] = num;
    num++;
}

bool bfs(int s,int t)
{
    memset(deep,-1,sizeof(deep));
    for(int i = 0;i <= maxn;++i) cur[i] = head[i];
    deep[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int i = head[v];i != -1;i = edges[i].nxt){
            Edge &e = edges[i];
            if(e.cap > 0 && deep[e.to] == -1){
                deep[e.to] = deep[v]+1;
                que.push(e.to);
            }
        }
    }
    if(deep[t] == -1) return false;
    return true;
}

int dfs(int v,int t,int f){
    if(!f || v == t) return f;
    int flow = 0,d;
    for(int &i = cur[v];i != -1;i = edges[i].nxt){
        Edge &e = edges[i];
        if(e.cap > 0 && deep[e.to] == deep[v]+1){
            d = dfs(e.to,t,min(e.cap,f));
            if(d <= 0) continue;
            flow += d;
            f -= d;
            edges[i].cap -= d;
            edges[i^1].cap += d;
            if(!f) break;
        }
    }
    if(!flow) deep[v] = -2;
    return flow;
}

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

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    memset(head,-1,sizeof(head));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        addedge(s,i,1);
        addedge(i,s,0);
        addedge(i+n,t,1);
        addedge(t,i+n,1);
    }
    for(int i = 0;i < m;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b+n,1);
        addedge(b+n,a,0);
    }
    dinic(s,t);
    memset(vis,0,sizeof(vis));
    int now = 0;
    int cnt = 0;
    for(int i = 1;i <= n;++i){
        if(vis[i]) continue;
        now = i;
        while(1){
            printf("%d ",now);
            int flag = 0;
            vis[now] = 1;
            for(int i = head[now];i != -1;i = edges[i].nxt){
                int to = edges[i].to;
                int cap = edges[i].cap;
                if(cap == 0 && to > n && to <= 2 * n){
                    now = to - n;
                    flag = 1;
                    break;
                }
            }
            if(!flag) break;
        }
        puts("");
        cnt++;
    }
    printf("%d\n",cnt);



    return 0;
}