首页 > 代码库 > UVa 639 - Don't Get Rooked
UVa 639 - Don't Get Rooked
题目:在n*n的方格里,放入几个喷火器,他们会攻击同行、同列的点,问做多能放多少个。
分析:图论,搜索,二分图匹配。本题可以利用搜索求解,这里我使用的是二分图匹配。
建图,把原图每行每列的不同的连续区间分别看成一个新图中的点xi与yj;
则边<xi,yj>表示原图中对应位置的点,原图中可以互相攻击的点就对应到新图中相同的xi与yj;
则新图中的二分图最大匹配即为,原图中不能相互攻击的最大摆放数量。
说明:图论关键就是建图。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; char maps[5][5]; int g[17][17]; int line[5][5],row[5][5]; int used[17],link[17]; int dfs(int s, int n) { for (int i = 0 ; i <= n ; ++ i) if (g[s][i] && !used[i]) { used[i] = 1; if (link[i] == -1 || dfs(link[i], n)) { link[i] = s; return 1; } } return 0; } int main() { int n,x,y; while (~scanf("%d",&n) && n) { for (int i = 0 ; i < n ; ++ i) scanf("%s",maps[i]); memset(line, -1, sizeof(line)); memset(row, -1, sizeof(row)); int line_count = -1,row_count = -1; for (int i = 0 ; i < n ; ++ i) for (int j = 0 ; j < n ; ++ j) { if (j == 0 || maps[i][j] != '.') line_count ++; if (maps[i][j] == '.') line[i][j] = line_count; if (j == 0 || maps[j][i] != '.') row_count ++; if (maps[j][i] == '.') row[j][i] = row_count; } memset(g, 0, sizeof(g)); for (int i = 0 ; i < n ; ++ i) for (int j = 0 ; j < n ; ++ j) if (maps[i][j] == '.') g[line[i][j]][row[i][j]] = 1; int sum = 0; memset(link, -1 ,sizeof(link)); for(int i = 0 ; i <= line_count ; ++ i) { memset(used, 0, sizeof(used)); sum += dfs(i, row_count); } printf("%d\n",sum); } return 0; }
UVa 639 - Don't Get Rooked
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。