mage 技术 bottom sub .html 攻击 ava string ostream
题目链接:https://vjudge.net/problem/HDU-1281
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5465 Accepted Submission(s): 3224
题解:
注意题目要求:不能放置棋子的格子,并不会影响攻击(即不是我们平时所遇到的墙),所以就不需要再对每一行和每一列都进分割了(参考HDU1045)。
1.把每一行看成一个点,编号为其行数;把每一列也看成一个点,编号为其列数。如果在[x][y]处可以放置棋子,则在连一条边 x-->y。
2.求出最大匹配数cnt。
3.枚举删除每一个可放置点,然后再求出最大匹配数,如果此时的最大匹配数小于cnt,则表明此处为关键位置。
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <sstream>
- #include <algorithm>
- using namespace std;
- const int INF = 2e9;
- const int MOD = 1e9+7;
- const int MAXN = 100+10;
- int n, uN, vN;
- int M[MAXN][MAXN], link[MAXN];
- bool vis[MAXN];
- bool dfs(int u)
- {
- for(int i = 1; i<=vN; i++)
- if(M[u][i] && !vis[i])
- {
- vis[i] = true;
- if(link[i]==-1 || dfs(link[i]))
- {
- link[i] = u;
- return true;
- }
- }
- return false;
- }
- int hungary()
- {
- int ret = 0;
- memset(link, -1, sizeof(link));
- for(int i = 1; i<=uN; i++)
- {
- memset(vis, 0, sizeof(vis));
- if(dfs(i)) ret++;
- }
- return ret;
- }
- int main()
- {
- int k, kase = 0;
- while(scanf("%d%d%d", &uN, &vN, &k)!=EOF)
- {
- memset(M, false, sizeof(M));
- for(int i = 1; i<=k; i++)
- {
- int x, y;
- scanf("%d%d", &x, &y);
- M[x][y] = true;
- }
- int cnt = hungary();
- int ans = 0;
- for(int i = 1; i<=uN; i++)
- for(int j = 1; j<=vN; j++)
- {
- if(!M[i][j]) continue;
- M[i][j] = false;
- if(hungary()<cnt) ans++;
- M[i][j] = true;
- }
- printf("Board %d have %d important blanks for %d chessmen.\n", ++kase, ans, cnt);
- }
- }
HDU1281 棋盘游戏 —— 二分图最大匹配 + 枚举
来源: http://www.bubuko.com/infodetail-2390368.html