POJ Asteroids 匈牙利算法

题目链接

POJ Asteroids

题解

此题思路是：
每个行列看成一个点，把每个炸弹看成一条边，通过这个炸弹可以炸掉该行/列，使其它炸弹数量不用，从而使炸弹数量最少
用二分匹配算法
通过某点的行，去匹配该行的每一列的炸弹，和某点的列，去匹配列的每一行的炸弹（完成炸边），这样的话，总体匹配几次，就使最小的炸弹数量（也是最大分配问题）

AC代码

#include 
#include 
#include 
#include 
using namespace std;
const int N = 510, M = 10010;
int match[M], g[N][N], n;
bool vis[M];
bool find(int u) //匈牙利算法 
{for(int i = 1; i <= n; i++) //挨个行去匹配 {if(g[u][i] && !vis[i])  {vis[i] = true;if(!match[i] || find(match[i])) //该点没匹配过，或者匹配过但是却能为它的匹配找到下家{match[i] = u;return true;}}}return false;
}
int main()
{int k;while(scanf("%d%d",&n,&k) != EOF) {memset(g,0,sizeof(g));for(int i = 0; i < k; i++){int x,y;//炸弹为止scanf("%d%d",&x,&y);g[x][y] = 1; }int res = 0;//最小炸弹数量memset(match,0,sizeof(match));for(int i = 1; i <= n; i++) //总体去匹配{memset(vis,0,sizeof(vis));if(find(i) == true) res++;} cout << res << endl;}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！