网络流24题 最小路径覆盖问题

题目传送门

好久之前做的+1，现在才写博客……
填一下网络流24题的坑

---

对于输入的一条((x, y))的边，我们实际将它连成((x, y+n))的边，则此图一定为一张二分图
然后最小路径覆盖$= n - $二分图最大匹配

然后就可以愉快的跑匈牙利了
说好的网络流呢

上古码风警告

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct zzz{
	int t,nex;
}e[6010<<2]; int head[310],tot;
void add(int x,int y){
	e[++tot].t=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
int lin[310],vis[310];
int find(int x){
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].t;
		if(!vis[to]){
			vis[to]=1;
			if(!lin[to]||find(lin[to])){
				lin[x]=to; lin[to]=x;
				return 1;
			}	
		}
	}
	return 0;
}
int read(){
	int k=0; char c=getchar();
	for(;c<'0'||c>'9';) c=getchar();
	for(;c>='0'&&c<='9';c=getchar())
	  k=k*10+c-48;
	return k;
}
int ans; bool jl[310];
int main(){
	int n=read(),m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		add(x,y+n);
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(find(i)) ans++;
	}
	for(int i=1;i<=n;i++){
		if(jl[i]) continue;
		printf("%d ",i);
		int x=lin[i];
		while(x){
			printf("%d ",x-=n);
			jl[x]=1; x=lin[x];
		}
		printf("
");
	}
	printf("%d",n-ans);
	return 0;
}