记录编号	61298	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最小路径覆盖问题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2013-06-07 13:21:55	内存使用	0.29 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=300,INF=0x7fffffff;
int N,S,T;//新图是0~N
int n,m;//原图顶点个数,边数
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
queue<int> Q;
int e[SIZEN]={0},h[SIZEN]={0};
void push(int x,int k){
	EDGE& now=edges[k];
	if(now.cap<=now.flow) return;
	int cf=min(now.cap-now.flow,e[x]);
	now.flow+=cf,edges[k^1].flow-=cf;
	e[x]-=cf,e[now.to]+=cf;
	if(now.to!=S&&now.to!=T&&e[now.to]) Q.push(now.to);
}
void singlenode(int x){
	int i,nowmin;
	while(e[x]>0){
		nowmin=INF;
		for(i=0;i<c[x].size();i++){
			EDGE& now=edges[c[x][i]];
			if(now.cap>now.flow){
				if(h[now.to]==h[x]-1){
					push(x,c[x][i]);
					if(!e[x]) return;
				}
				else nowmin=min(nowmin,h[now.to]);
			}
		}
		h[x]=nowmin+1;
	}
}
void maxflow(void){
	int i,x;
	for(i=0;i<=N;i++) h[i]=e[i]=0;
	h[S]=N,e[S]=INF;
	for(i=0;i<c[S].size();i++) push(S,c[S][i]);
	while(!Q.empty()){
		x=Q.front();Q.pop();
		singlenode(x);
	}
}
void addedge(int from,int to,int cap){
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
void init(void){
	scanf("%d%d",&n,&m);
	N=n*2+1,S=0,T=N;
	int i,a,b;
	for(i=1;i<=n;i++){
		addedge(S,i,1);
		addedge(n+i,T,1);
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		addedge(a,n+b,1);
	}
}
bool visit[SIZEN]={0};
void findpath(int x){//这货不是匈牙利!!!这货不是匈牙利!!!
	if(visit[x]) return;
	visit[x]=true;
	printf("%d ",x);
	int i;
	for(i=0;i<c[x].size();i++){
		EDGE& now=edges[c[x][i]];
		if(now.flow==1){
			findpath(now.to-n);
		}
	}
}
void write(void){
	int i;
	int nump=0;
	for(i=0;i<=N;i++) visit[i]=false;
	for(i=0;i<c[S].size();i++){
		EDGE& now=edges[c[S][i]];
		if(visit[now.to]) continue;
		if(now.flow==1){
			findpath(now.to);
			printf("\n");
			nump++;
			
		}
		else{
			printf("%d\n",now.to);
			nump++;
		}
	}
	printf("%d\n",nump);
}
int main(){
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	init();
	maxflow();
	write();
	return 0;
}