专栏首页Zaqdt_ACMHDU 4185 Oil Skimming(思维+二分图最大匹配数)

HDU 4185 Oil Skimming(思维+二分图最大匹配数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4185

       题意是输入n*n的地图,然后问最多有多少个1*2或者2*1的'#'。

       思路就是用二分图,将相邻的'#'连一条边,然后在n*n的图内跑一个最大匹配数。难就难在如何去建图,我们把每个'#'的坐标记为一个数,然后对于两个相邻的'#',直接用刚才所标记的数进行建边,坑点是因为是n*n的地图,如果有n*n个'#'的话,就需要开maxn*maxn个数组,还有就是vector初始化的时候也是n*n,这一点需要注意。


AC代码:

#include <bits/stdc++.h>
#define maxn 610
using namespace std;
vector<int> G[maxn];
int pre[maxn][maxn];
int mat[maxn * maxn];
bool vis[maxn * maxn];
string str[maxn];
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
int T,n,cnt;

void init(){
	cnt = 1;
	memset(mat,-1,sizeof(mat));
	memset(pre,0,sizeof(pre));
	for(int i=0;i<=n*n;i++){
		G[i].clear();
	}
}

bool dfs(int x){
	for(int i=0;i<G[x].size();i++){
		int v = G[x][i];
		if(vis[v] == false){
			vis[v] = true;
			if(mat[v] == -1 || dfs(mat[v])){
				mat[v] = x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int Case = 1;
	scanf("%d",&T);
	while(T--){
		init();
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			cin>>str[i];
			for(int j=0;j<n;j++)
				if(str[i][j] == '#') pre[i][j] = cnt ++;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(str[i][j] == '#'){
					for(int k=0;k<4;k++){
						int xx = i + dir[k][0];
						int yy = j + dir[k][1];
						if(xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
						if(str[xx][yy] == '#'){
							G[pre[xx][yy]].push_back(pre[i][j]);
							G[pre[i][j]].push_back(pre[xx][yy]);
						}
					}
				}
			}
		}
		int ans = 0;
		for(int i=1;i<=cnt;i++){
			memset(vis,false,sizeof(vis));
			if(dfs(i)) ans ++;
		}
		printf("Case %d: %d\n",Case ++, ans / 2);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 2255 奔小康赚大钱(二分图最佳匹配--KM算法)

            二分图带全匹配的裸题,直接贴板子就行,对于二分图最佳匹配可以用网络流去写,还有KM算法也可以解决这个问题,这个算法的中心思想就是依次选择最大权的...

    Ch_Zaqdt
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

    题目链接:http://codeforces.com/contest/1077/problem/D

    Ch_Zaqdt
  • Hebuter Daily Training 201810

    有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,...

    xiaohejun
  • Kolakoski序列产生器

    xiaoxi666
  • HDU 2255 奔小康赚大钱(二分图最佳匹配--KM算法)

            二分图带全匹配的裸题,直接贴板子就行,对于二分图最佳匹配可以用网络流去写,还有KM算法也可以解决这个问题,这个算法的中心思想就是依次选择最大权的...

    Ch_Zaqdt
  • 2-Sat+输出可行解(个人模版)

    2-Sat+输出可行解: 1 //LightOJ 1251 2 #include<stdio.h> 3 #include<string.h> 4...

    Angel_Kitty
  • P1629 邮递员送信

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack
  • HUST 1017 - Exact cover

    Time Limit: 15s Memory Limit: 128MB Special Judge Submissions: 7636 Solved: 38...

    attack
  • CSU 1326: The contest(分组背包)

    http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326 题意:       n个题目,每个题目都有一个价值P...

    用户1624346

扫码关注云+社区

领取腾讯云代金券