【题解】Luogu P2319 [HNOI2006]超级英雄

原题传送门

这道题就是一个很简单的二分图匹配

二分图匹配详解

一开始想的是2-sat和网络流，根本没想匈牙利和HK

这道题只要注意一点：当一个点匹配不成功之后就直接退出

剩下的就写个二分图最大匹配就行了

完整代码（不想写HK）

#include <bits/stdc++.h>

#define N 1005

using namespace std;

inline int read()

{

	register int x=0,f=1;register char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*f;

}

inline void write(register int x)

{

	if(!x)putchar('0');if(x<0)x=-x,putchar('-');

	static int sta[25];int tot=0;

	while(x)sta[tot++]=x%10,x/=10;

	while(tot)putchar(sta[--tot]+48);

}

struct node{

	int to,next;

}e[N<<1];

int head[N],tot;

inline void add(register int u,register int v)

{

	e[++tot]=(node){v,head[u]};

	head[u]=tot;

}

int n,m;

int ask[N],matched[N],bematched[N];

inline bool dfs(register int u)

{

	for(register int i=head[u];i;i=e[i].next)

	{

		int v=e[i].to;

		if(ask[v])

			continue;

		ask[v]=1;

		if(!matched[v]||dfs(matched[v]))

		{

			matched[v]=u;

			bematched[u]=v;

			return true;

		}

	}

	return false;

}

int main()

{

	n=read(),m=read();

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

	{

		int x=read()+1,y=read()+1;

		add(i,x),add(i,y);

	}

	int ans=0;

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

	{

		memset(ask,0,sizeof(ask));

		if(dfs(i))

			++ans;

		else

			break;

	}

	write(ans),puts("");

	for(register int i=1;i<=ans;++i)

		write(bematched[i]-1),puts("");

	return 0;

}