【[HNOI2006]超级英雄】

看到楼下有大佬说了网络流做法，来给大佬配个代码

我们只有我可能都觉得如果不动态加边的话(dinic)可能跑不了这种需要中途退出的二分图匹配

正当我准备去敲匈牙利的时候突然想到这个题可以二分啊

于是二分好了

如果答案是(ans)的话，(ans-1)肯定也满足条件，所以存在单调性，我们就可以二分了

至于(check)怎么写，我们只对(1)到当前要(check)答案跑一边(dinic)就好了，如果最大的匹配数等于当前答案的话那么这个答案就是合法的

时间复杂度应该为(O(Vsqrt{n+m} ext{ }logm))

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define re register
#define maxn 5005
#define INF 9999999
using namespace std;
struct node
{
	int v,nxt,w,f;
}e[100005];
int n,num,m,S,T;
int d[maxn],vis[maxn],head[maxn];
int a[maxn],b[maxn];
int ans=0;
int tot[maxn];
inline int read()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	  x=(x<<3)+(x<<1)+c-48,c=getchar();
	return x;
}
inline void add_edge(int x,int y,int z)
{
	e[num].v=y;
	e[num].nxt=head[x];
	e[num].w=z;
	head[x]=num++;
}
inline int bfs()
{
	queue<int> q;
	memset(vis,0,sizeof(vis));
	vis[S]=1;
	d[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		for(re int i=head[k];i!=-1;i=e[i].nxt)
		if(!vis[e[i].v])
		{
			if(e[i].w<=e[i].f) continue;
			vis[e[i].v]=1;
			d[e[i].v]=d[k]+1;
			q.push(e[i].v);
		}
	}
	return vis[T];
}
int dfs(int x,int now)
{
	if(x==T||!now) return now;
	int flow=0,ff;
	for(re int i=head[x];i!=-1;i=e[i].nxt)
	if(d[e[i].v]==d[x]+1)
	{
		ff=dfs(e[i].v,min(now,e[i].w-e[i].f));
		if(ff<=0) continue;
		now-=ff;
		flow+=ff;
		e[i].f+=ff;
		e[i^1].f-=ff;
		if(!now) break;
	}
	return flow;
}
inline void did(int x)
{
	for(re int i=1;i<=x;i++)
	{
		for(re int j=head[i];j!=-1;j=e[j].nxt)
		if(e[j].f==1&&e[j].v>m) 
		{
			tot[i]=e[j].v;
			break;
		}
	}
}
inline int check(int x)
{
	num=0;
	memset(head,-1,sizeof(head));
	memset(e,0,sizeof(e));
	for(re int i=m+1;i<=m+n;i++) add_edge(i,n+m+1,1),add_edge(n+m+1,i,0);
	for(re int i=1;i<=x;i++)
		add_edge(0,i,1),add_edge(i,0,0);
	for(re int i=1;i<=x;i++)
	{
		add_edge(i,a[i],1);
		add_edge(a[i],i,0);
		if(a[i]==b[i]) continue;
		add_edge(i,b[i],1);
		add_edge(b[i],i,0);
	}
	int k=0;
	while(bfs()) k+=dfs(0,INF);
	return k==x;
}
int main()
{
	n=read();
	m=read();
	int x,y;
	S=0,
	T=n+m+1;
	memset(head,-1,sizeof(head));
	for(re int i=1;i<=m;i++)
		a[i]=read()+1+m,b[i]=read()+1+m;
	int l=0,r=m;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid)) 
			ans=mid,did(mid),l=mid+1;
		else r=mid-1;
	}
	cout<<ans<<endl;
	for(re int i=1;i<=ans;i++)
	printf("%d
",tot[i]-1-m);
	return 0;
}