poj 3041 Asteroids

本文主要是介绍poj 3041 Asteroids，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：n*n的格子里面有k个小行星，每一能消除一行或一列，那么最小消除多少次可以把全部消除掉

思路：把行和列连到一起，可以构成一个二分图，那么只需要求最大匹配数即为所求

<pre name="code" class="cpp">#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int N=1001;int n1,n2,k;int mp[N][N],vis[N],link[N];int dfs(int x)
{int i;for(i=1; i<=n2; i++){if(!mp[x][i]&&!vis[i]){vis[i]=1;if(link[i]==-1||dfs(link[i])){link[i]=x;return 1;}}}return 0;
}int main(){int i,x,y,s;int cas = 0;while(~scanf("%d%d",&n1,&k)){s=0;n2=n1;for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){mp[i][j]=1;}}for(i=0; i<k; i++){scanf("%d%d",&x,&y);mp[x][y]=0;}memset(link,-1,sizeof(link));for(i=1; i<=n1; i++){memset(vis,0,sizeof(vis));if(dfs(i))s++;}printf("%d\n",s);}return 0;
}

这篇关于poj 3041 Asteroids的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---