二分图应用模版

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <queue>

using namespace std;

const int MAXN=400,MAXM=50005;

int head[MAXN],nume,n,m,maxflow,s,t,cur[MAXN],dep[MAXN];

queue<int>q;

struct edge{

	int to,nxt,cap,flow;

}e[MAXM];

void adde(int from,int to,int cap){

	e[++nume].to=to;

	e[nume].cap=cap;

	e[nume].nxt=head[from];

	head[from]=nume;

}

bool bfs(){

	memset(dep,0,sizeof(dep));

	q.push(s);dep[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(!dep[v]&&e[i].flow<e[i].cap){

				dep[v]=dep[u]+1;

				q.push(v);

			}

		}

	}

	return dep[t];

}

int dfs(int u,int flow){

	if(u==t) return flow;

	int tot=0;

	for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){

		int v=e[i].to;

		if(dep[v]==dep[u]+1&&e[i].flow<e[i].cap){

			if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){

				e[i].flow+=t;

				e[((i-1)^1)+1].flow-=t;

				tot+=t;

			}

		}

	}

	return tot;

}

void dinic(){

	while(bfs()){

		for(int i=s;i<=t;i++) cur[i]=head[i];

		maxflow+=dfs(s,0x3f3f3f3f);

	}

}

bool f[MAXN];

void print(int u){

	printf("%d ",u);

	f[u]=1;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v&&!f[v-n]&&e[i].flow){

			print(v-n);

			return;

		}

	}

}

int main(){

	cin>>n>>m;

	s=0;t=n*2+1;

	for(int i=1;i<=m;i++){

		int u,v;

		scanf("%d%d",&u,&v);

		adde(u,v+n,1);adde(v+n,u,0);

	}

	for(int i=1;i<=n;i++){

		adde(s,i,1);adde(i,s,0);

		adde(i+n,t,1);adde(t,i+n,0);

	}

	dinic();

	for(int i=1;i<=n;i++){

		if(!f[i]) print(i),printf("\n");

	}

	printf("%d\n",n-maxflow);

}