poj1325机器工作——二分图最小点覆盖

题目：http://poj.org/problem?id=1325

二分图求最大匹配，即为最小点覆盖；

一开始我写得较麻烦，求出最大匹配又去搜增广路，打标记求最小点覆盖；

然而两种方法都没写“ans=0”，WA了好几次，心力交瘁时才发现，改后即A，心力交瘁。

代码1如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,k,pre1[305],pre2[305],head[305],ct,ans;

bool vis[305];

struct N{

	int to,next;

}edge[3005];

void add(int x,int y)

{

	ct++;

	edge[ct].to=y;

	edge[ct].next=head[x];

	head[x]=ct;

}

bool dfs(int b)

{

	for(int i=head[b];i;i=edge[i].next)

	{

		int a=edge[i].to;

		if(vis[a])continue;

		vis[a]=1;

		if(!pre1[a]||dfs(pre1[a]))

		{

			pre1[a]=b;

			pre2[b]=a;

			return 1;

		}

	}

	return 0;

}

bool dfs2(int b)

{

	vis[b]=1;

	for(int i=head[b];i;i=edge[i].next)

	{

		int a=edge[i].to;

		if(vis[a])continue;

		vis[a]=1;

		if(!pre1[a]||dfs2(pre1[a]))

		{

			pre1[a]=b;

			pre2[b]=a;

			return 1;

		}

	}

	return 0;

}

int main()

{

	while(1)

	{

		ct=0;ans=0;//!

		memset(pre1,0,sizeof pre1);

		memset(pre2,0,sizeof pre2);

		memset(head,0,sizeof head);

		scanf("%d",&n);

		if(!n)return 0;

		scanf("%d%d",&m,&k);

		int d,a,b;

		for(int i=1;i<=k;i++)

		{

			scanf("%d%d%d",&d,&a,&b);

			if(a*b==0)continue;

			add(a+100,b);

			add(b,a+100);

		}

		for(int i=1;i<m;i++)//最大匹配

			if(!pre2[i])

			{

				memset(vis,0,sizeof vis);

				vis[i]=1;//

				dfs(i);

			}

		memset(vis,0,sizeof vis);

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

			if(!pre2[i])

				dfs2(i);

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

			if(!vis[i])ans++;

		for(int i=101;i<n+100;i++)

			if(vis[i])ans++;

		printf("%d\n",ans);

	}

}

代码2如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,k,pre[305],head[305],ct,ans;

bool vis[305];

struct N{

	int to,next;

}edge[3005];

void add(int x,int y)

{

	ct++;

	edge[ct].to=y;

	edge[ct].next=head[x];

	head[x]=ct;

}

bool dfs(int b)

{

	vis[b]=1;

	for(int i=head[b];i;i=edge[i].next)

	{

		int a=edge[i].to;

		if(vis[a])continue;

		vis[a]=1;

		if(!pre[a]||dfs(pre[a]))

		{

			pre[a]=b;

			pre[b]=a;

			return 1;

		}

	}

	return 0;

}

int main()

{

	while(1)

	{

		ct=0;ans=0;//

		memset(pre,0,sizeof pre);

		memset(head,0,sizeof head);

		scanf("%d",&n);

		if(!n)return 0;

		scanf("%d%d",&m,&k);

		int d,a,b;

		for(int i=1;i<=k;i++)

		{

			scanf("%d%d%d",&d,&a,&b);

			if(a*b==0)continue;

			add(a+100,b);

			add(b,a+100);

		}

		for(int i=1;i<m;i++)//最大匹配

			if(!pre[i])

			{

				memset(vis,0,sizeof vis);

				if(dfs(i))ans++;

			}

		printf("%d\n",ans);

	}

}