首页 > 代码库 > UVALive 6525 Attacking rooks(二分图最大匹配)
UVALive 6525 Attacking rooks(二分图最大匹配)
Attacking rooks
在一个n*n的图中,‘X’代表卒,在‘.’的地方放置尽量多的车,使得它们不互相攻击。问最多可放置车的数目。
和Fire Net一样,但这里图是100*100的,搜索会超时(其实我还脑残的试了试).
正解是二分图匹配,将每行中连续为.的作为X集合中一个点,同样,将每列中连续为.的点作为Y集合中的一个点。对原图中每个‘.‘,将其对应的X集合和Y集合中的标号建边,便形成了二分图,对该图求最大匹配,每形成一个匹配即选择该点放车,那么与它相同编号的行和列都被覆盖了,都不能被选择了。最大匹配数就是最多可以放的车数。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1000000007; const int maxn = 50010; struct node { int v; int next; }edge[10010]; char G[110][110]; int mapr[110][110],mapc[110][110]; int n; int cnt,pre[10010]; int a,b; int match[10010]; int chk[10010]; void add(int u,int v) { edge[cnt] = ((struct node){v,pre[u]}); pre[u] = cnt++; } void init() { int i,j; a = 1,b = 1; memset(mapr,0,sizeof(mapr)); memset(mapc,0,sizeof(mapc)); cnt = 0; memset(pre,-1,sizeof(pre)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(G[i][j] == ‘.‘) { if(G[i][j] != G[i][j-1]) mapr[i][j] = a++; else mapr[i][j] = mapr[i][j-1]; } } } for(int j = 1; j <= n; j++) { for(int i = 1; i <= n; i++) { if(G[i][j] == ‘.‘) { if(G[i][j] != G[i-1][j]) mapc[i][j] = b++; else mapc[i][j] = mapc[i-1][j]; } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(G[i][j] == ‘.‘) add(mapr[i][j], mapc[i][j]); } } } int dfs(int p) { for(int i = pre[p]; i != -1; i = edge[i].next) { int v = edge[i].v; if(!chk[v]) { chk[v] = 1; if(match[v] == -1 || dfs(match[v])) { match[v] = p; return 1; } } } return 0; } int main() { while(~scanf("%d",&n)) { memset(G,‘0‘,sizeof(G)); for(int i = 1; i <= n; i++) scanf("%s",G[i]+1); init(); memset(match,-1,sizeof(match)); int ans = 0; for(int i = 1; i <= a; i++) { memset(chk,0,sizeof(chk)); ans += dfs(i); } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。