记录编号	330834	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最小路径覆盖问题	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-10-26 21:12:01	内存使用	0.67 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#define INF 0x3f3f3f3f
#define N 330
using namespace std;

int n,m,i,j,Found,flow,al,t,cnt,x,y;
int l[N][N];
int gap[N],gaps[N],go[N],bh[N];

inline int read(){
	int p=0;	char c=getchar();
	while (c<'0'||c>'9')	c=getchar();
	while (c>='0'&&c<='9')	p=p*10+c-48,c=getchar();
	return p;
}
inline int min(int a,int b){return (a<b)?a:b;}

inline void Sap(int x){
	int i=0,F=al,mingap=cnt-1;
	if (x==cnt) {flow+=al; Found=1; return;}
	for (i=1;i<=cnt;i++)
		if (l[x][i]){
			if (gap[i]+1==gap[x]){
				al=min(al,l[x][i]);	Sap(i);
				if (gap[1]>=cnt)	return;
				if (Found)	break;
				al=F;
			}
			mingap=min(mingap,gap[i]);
		}
	if (!Found){
		gaps[gap[x]]--;	if (!gaps[gap[x]]) gap[1]=cnt;
		gaps[gap[x]=mingap+1]++;
	}	else l[x][i]-=al,l[i][x]+=al;
}

int main(){
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	n=read();	m=read();	cnt=n*2+2;
	for (i=1;i<=n;i++)	l[1][1+i]=1;
	for (i=1;i<=n;i++)	l[1+n+i][cnt]=1;
	for (i=1;i<=m;i++){
		x=read();	y=read();	l[x+1][1+n+y]=1;
	}
	gaps[0]=cnt;
	while (gap[1]<cnt){
		Found=0; al=INF; Sap(1);
	}
	cnt=0;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		if (l[1+n+j][1+i]) go[i]=j;
	for (i=1;i<=n;i++)
	if (!bh[i]){
		t=i;	cnt++;
		while (t) {bh[t]=1; printf("%d ",t); t=go[t];}
		putchar(10);
	}
	printf("%d\n",cnt);
	return 0;
}