记录编号	490462	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最小路径覆盖问题	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2018-03-09 10:56:02	内存使用	1.41 MiB

#include<bits/stdc++.h>
#define ll long long
#define s (n<<1|1)
#define t (n<<1)+3
using namespace std;
const int N = 4e2+7, inf = 1e9;
int n, m, ans;
int g[N][N], f[N][N], p[N][N], dep[N], vis[N];
bool bfs()
{
    queue<int> q;
    q.push(s);
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v = 1; v <= t; v++)
        {
            if(g[u][v]>0&&!dep[v])
            {
                dep[v] = dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t] > 0;
}
int dfs(int x, int flow)
{
    if(x==t)
    {
        return flow;
    }
    int rest = flow, k;
    for(int i = 1; i <= t&&rest; i++)
    {
        if(g[x][i]>0&&dep[i]==dep[x]+1)
        {
            k = dfs(i, min(rest, g[x][i]));
            if(!k)
            {
                dep[i] = 0;
            }
            g[x][i] -= k;
            g[i][x] += k;
            rest -= k;
        }
    }
    return flow-rest;
}
int dinic()
{
    int cnt = 0;
    while(bfs())
    {
        cnt += dfs(s, inf);
    }
    return cnt;
}
void print(int x)
{
    vis[x]++;
    printf("%d ", x);
    for(int i = 1; i <= n; i++)
    {
        if(g[x][i+n]<f[x][i+n])
        {
            print(i);
            break;
        }
    }
    return;
}
int main()
{
    freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        g[s][i] = g[i+n][t] = 1;
    }
    while(m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v+n] = 1;
    }
    memcpy(f, g, sizeof(g));
    int ans = n-dinic();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(!vis[i]&&f[i][j+n])
            {
                print(i);
                puts("");
            }
        }
    }
    printf("%d\n", ans);
	return 0;
}