记录编号	269519	评测结果	AAWWWWAWWWW
题目名称	[网络流24题] 最小路径覆盖问题	最终得分	27
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-06-13 17:48:08	内存使用	0.68 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int read(){
	int x=0, f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int maxn = 6000;

struct Edge{
    int next, to;
}e[24001];
int head[maxn<<1], tot;
void Add(int x,int y)
{
	e[++tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}
int match[maxn<<1], vis[maxn<<1], T;
int last[maxn<<1];

int N, M;
bool target(int x){
    for(int i=head[x]; i; i=e[i].next){
        int to = e[i].to;
        if(!vis[to]){
            vis[to] = 1;
            if(!match[to] || target(match[to])){
                match[to] = x;
                last[x] = to;
                return true;
            }
        }
    }
    return false;
}
int main(){
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	N = read(), M = read();
    for(int i=1; i<=M; ++i){
        int a = read(), b = read();
        Add(a, b);
    }
    int ans = 0;
    for(int i=1; i<=N; ++i){
        memset(vis, 0, sizeof(vis));
        if(!target(i)) ans++;
    }
    for(int i=1; i<=N; ++i)
        if(!match[i]){
            int x = i;
            do{
                printf("%d ", x);
                x = last[x];
            }while(x);
            puts("");
        }
    printf("%d", ans);
    fclose(stdin); fclose(stdout);
	return 0;
}