codevs 1904 最小路径覆盖问题

题目描述 Description
给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个
顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶
点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少
的路径覆盖。
设计一个有效算法求一个有向无环图G 的最小路径覆盖。
对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。

输入描述 Input Description
第1 行有2个正整数n和m。n是给定有向无环图
G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。

输出描述 Output Description
将最小路径覆盖输出。从第1 行开始，每行输出
一条路径。文件的最后一行是最少路径数。

样例输入 Sample Input
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11

样例输出 Sample Output
1 4 7 10 11
2 5 8

3 6 9

3

思路：最小路径覆盖：利用最少的路径把整幅图的顶点全部覆盖。各路径之间交集为空； 其中，定点数=最大匹配+最小路径覆盖。

可以将此图转化为二分图求最大匹配，其中可以用网络最大流、匈牙利算法求。

网络最大流做法，将所有点（理解为源点）复制，然后重编号（理解为汇点），然后连接题目所给边，然后设一个超级源点和一个超级汇点，每条边的最大流设为1，求这幅图的网络流得出最大匹配数。

（此法不能得出路径）；

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int maxn=1010;

int N, M;
struct Edge
{
    int u, v, cap;
    Edge() {}
    Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
} es[maxn*maxn];
int R, S, T;
vector<int> tab[maxn]; // 边集
int dis[maxn];
int current[maxn];
void addedge(int u, int v, int cap)
{
    tab[u].push_back(R);
    es[R++] = Edge(u, v, cap); // 正向边
    tab[v].push_back(R);
    es[R++] = Edge(v, u, 0); // 反向边容量为0
    // 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2
}
int BFS()
{
    queue<int> q;
    q.push(S);
    memset(dis, 0x3f, sizeof(dis));

    dis[S] = 0;
    while (!q.empty())
    {
        int h = q.front();
        q.pop();
        for (int i = 0; i < tab[h].size(); i++)
        {
            Edge &e = es[tab[h][i]];
            if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
            {
                dis[e.v] = dis[h] + 1;
                q.push(e.v);
            }
        }
    }
    return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}
int dinic(int x, int maxflow)
{
    if (x == T)
        return maxflow;
    // i = current[x] 当前弧优化
    for (int i = current[x]; i < tab[x].size(); i++)
    {
        current[x] = i;
        Edge &e = es[tab[x][i]];
        if (dis[e.v] == dis[x] + 1 && e.cap > 0)
        {
            int flow = dinic(e.v, min(maxflow, e.cap));
            if (flow)
            {
                e.cap -= flow; // 正向边流量降低
                es[tab[x][i] ^ 1].cap += flow; // 反向边流量增加
                return flow;
            }
        }
    }
    return 0; // 找不到增广路 退出
}
int DINIC()
{
    int ans = 0;

    while (BFS()) // 建立分层图
    {
        int flow;
        memset(current, 0, sizeof(current)); // BFS后应当清空当前弧数组
        while (flow = dinic(S, 0x3f3f3f3f)) // 一次BFS可以进行多次增广
            ans += flow;
    }
    return ans;
}
int main()
{
    while (scanf("%d%d", &N, &M) != EOF)
    {
        R = 0;
        S = 0;
        T = 2*N + 1;
        for (int i = 0; i <= T; i++)
            tab[i].clear();

        for (int i = 0; i < M; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y+N,1);
        }
        for(int i=1; i<=N; i++)
        {

            addedge(S,i,1);
            addedge(i+N,T,1);
        }
//        printf("%d\n", DINIC());
        printf("%d\n",N-DINIC());
    }
    return 0;
}

下面是lyq给的匈牙利算法写法，可以输出路径；

#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
//#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define pd(x) printf("%d\n",x)
#define cls(a,x) memset(a,x,sizeof(a))
const double eps=1e-5;
const double PI=acos(-1.0);
const int INF=1e9+10;
const int MOD=1e9+7;
const int N=1e3+10;
vector<int>g[N];
int n,m;
int used[N],linked[N];
int pre[N];
void init()
{
    for(int i=0; i<=n; i++) g[i].clear();
}
bool dfs(int u)
{
    int len=g[u].size();
    for(int i=0; i<len; i++)
    {
        int v=g[u][i];
        if(!used[v])
        {
            used[v]=1;
            if(linked[v]==-1||dfs(linked[v]))
            {
                linked[v]=u;
                pre[u]=v; 
                return true;
            }
        }
    }
    return false;
}
void hungary()
{
    memset(linked,-1,sizeof(linked));
    memset(pre,-1,sizeof(pre));
    int ans=0;
    for(int i=0; i<n; i++)
    {
        memset(used,0,sizeof(used));
        if(dfs(i)) ans++;
    }
    for(int i=1;i<=n;i++)
    if(linked[i]==-1)
    {
        int u=i;
        while(u+1)
        {
            printf("%d ",u);
            u=pre[u];
        }
        puts("");
    }
    printf("%d\n",n-ans);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int u,v;
        init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
        }
        hungary();
    }
    return 0;
}