学步园

看题的时候，看不出这是最小顶点覆盖，悲剧。

注意点：1，顶点从0开始，所以，my[]的标记不能以0为标准。

                2，枚举法确实很不错。

#include<iostream>
#include<string>
using namespace std;
int n,m;
int f[220];
class node
{
public:
	int to;
	int next;
};
int head[220],vis[220],my[220],del[220];
node e[20002];
int cnt;
void add(int a,int b)
{
	e[++cnt].to =b;
	e[cnt].next= head[a];
	head[a]=cnt;
}
bool dfs(int k)
{
	for(int u=head[k];u!=-1;u=e[u].next)
	{
		int v=e[u].to;
		if(!vis[v]&&!del[v])
		{
			vis[v]=1;
			if(my[v]==-1||dfs(my[v]))
			{
				my[v]=k;
				return true;
			}
		}
	}
	return false;
}
int  get()
{
	int now =0,i;
	memset(my,-1,sizeof(my));
	for(i=0;i<n;i++)
	{
		if(f[i]==0) continue;
		if(del[i]) continue;
		memset(vis,0,sizeof(vis));
		if(dfs(i))
			now++;
	}
	return now;
}
void solve()
{
	memset(del,0,sizeof(del));
	int sum =get(),now=sum,i;
	int ans[220],len=0;
	for(i=0;i<n;i++)
	{
		del[i]=1;
		bool flag=true;
		int k=get();
		if(k+1==now) 
		{
			now--;
			ans[len++]=i;
			flag=false;
		}
		if(flag)  del[i]=0;
	}
	cout<<sum<<" ";
	for(i=0;i<len;i++)
		cout<<ans[i]<<" ";
	cout<<endl;
}
void in()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		{
			cin>>f[i];
			head[i]=-1;
		}
		for(int i=0;i<m;i++)
		{
			int a,b;
			cin>>a>>b;
			if(a==b) continue;
			if(f[a]==f[b]) continue;
			add(a,b);
			add(b,a);
		}
}
int main()
{
	int test;
	cin>>test;
	while(test--)
	{
		cnt=0;
		in();
		solve();
	}
	return 0;
}