记录编号	90699	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最小路径覆盖问题	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2014-03-08 19:57:32	内存使用	1.39 MiB

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <queue>
#define S (n+n+1)
#define T (n+n+2)
#define N (n+n+2)
using namespace std;

int g[400][400],g1[400][400],h[400],n,m,i,k,ans;
bool vis[400];
queue <int> q;

int dfs(int x,int sum)
{
	int y,t,last=sum;
	if (x==T) return sum;
	for (y=1;y<=N&&sum;y++)
		if (g[x][y]>0&&h[y]==h[x]+1)
		{
			t=dfs(y,min(sum,g[x][y]));
			g[x][y]-=t; g[y][x]+=t; sum-=t;
		}
	return last-sum;
}

bool bfs()
{
	int x,y;
	memset(h,-1,sizeof(h));
	q.push(S); h[S]=0;
	while (!q.empty())
	{
		x=q.front(); q.pop();
		for (y=1;y<=N;y++)
			if (g[x][y]>0&&h[y]==-1)
			{
				h[y]=h[x]+1;
				q.push(y);
			}
	}
	return h[T]>=0;
}

int dinic()
{
	int ret=0;
	while (bfs()) ret+=dfs(S,INT_MAX);
	return ret;
}

bool check(int x)
{
	for (int i=1;i<=n;i++)
		if (g1[i][n+x]&&!vis[i]&&i!=x)
			return false;
	return true;
}

void print(int x)
{
	vis[x]=true; printf("%d ",x);
	for (int y=1;y<=n;y++)
		if (g[x][n+y]<g1[x][n+y])
			print(y);
}

int main()
{
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) g[S][i]=1;
	for (i=1;i<=n;i++) g[n+i][T]=1;
	while (m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x][n+y]=1;
	}
	memcpy(g1,g,sizeof(g));
	ans=n-dinic();
	for (k=1;k<=ans;k++)
	{
		for (i=1;i<=n;i++) if (!vis[i]&&check(i)) break;
		print(i);
		putchar('\n');
	}
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}