首页 > 代码库 > POJ3041_Asteroids

POJ3041_Asteroids

2024-07-10 11:26:53   219人阅读

这个题目说，有一个N*N的规格的方格。某些格子里有*号，每次可以消除一行或者一列中所有的*号。最少需要消多少次？

新学到的，什么什么定理，最少点覆盖等于最大匹配数。

这个定理可以这样来理解（看别人的），对于最大匹配状态下的一条匹配边，不可能两边同时存在可连的未匹配点，因为这样就可以增广了，所以对于一条匹配边，只要选取在其有未匹配点的一边的点就可以了，对于其他的匹配边同理。

接下来就是上模版的时候了。。。

 

召唤代码君：

 

#include <cstdio>#include <vector>#define maxn 505using namespace std;vector<int> r[maxn],c[maxn];int tr[maxn],tc[maxn],fc[maxn],tagc[maxn];int n,m,ans,R,C;bool dfs(int cur,int T){	for (unsigned i=0; i<r[cur].size(); i++)	{		if (tagc[r[cur][i]]==T) continue;		tagc[r[cur][i]]=T;		if (fc[r[cur][i]]==0 || dfs(fc[r[cur][i]],T))		{			fc[r[cur][i]]=cur;			return true;		}	}	return false;}int main(){	scanf("%d%d",&n,&m);	for (int T=1; T<=m; T++)	{		scanf("%d%d",&R,&C);		if (tr[R]!=1) r[R].clear(),tr[R]=1;		if (tc[C]!=1) fc[C]=0,tagc[C]=0;		r[R].push_back(C);	}	for (int i=1; i<=n; i++)		if (tr[i]!=0 && dfs(i,i)) ans++;	printf("%d\n",ans);	return 0;}

　　


联系
我们