hdu 4185 Oil Skimming （二分匹配）

本文主要是介绍hdu 4185 Oil Skimming （二分匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

第一次写自己的博客呢，有点小激动，不对的地方希望大家帮忙改进。吐舌头

题意:   题意很简单，构造出模型就是在一个N*N的矩阵中，求上下或左右相连的"#"的最大组数（两个为一组）。大一接触的题目还是太少，一开始以为是连通块问题很开心地翻开了紫书狂敲代码，结果不停WA，赛后才知道原来是二分匹配问题哭，就赶紧去学了学，看了几份题解报告以后才彻底弄懂这道题。其实这道题就是匈牙利算法的典型应用，其核心思想是用增广路径求二分图的最大匹配。

分析：对于每一个#先遍历一遍进行编号，然后对于每一个#，遍历一下四周有没有#，如果有的话二者就可以匹配在一起，由于这是一个无向图，只要看它右边和下边有没有#，建双向边就可就好，详细分析见解析。

建图如下：(已为所有#编好号)

         0            1

         3            2

         4            5

         6          （第一次不太会用博客，没找到插入直线的方法，请自行脑补连通的#之间有一条线。其中连通的有：01,  10,   02,   20,  13,  31,  32,  23,   45,   54,   65,   56）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 666;
char s[maxn][maxn];//输入原字符型矩阵
int link[maxn][maxn],p[maxn][maxn],x[maxn],y[maxn],vis[maxn];//ink[x][y]表示x与y按题意可以连通；//P[x][y]为“#”编号； x[i]=j;y[j]=i;表示i与j匹配；vis[j]判断j是否已经有匹配；
int num;
bool find_(int i)//判断第i个#是否可以找到与之匹配的#
{for(int j = 0; j < num; j++){if(link[i][j] && !vis[j])//第i,j个#连通并且j尚未找到匹配的{vis[j] = 1;//标记j有与之匹配的#了if(y[j] == -1 || find_(y[j]))//j尚未与任何#匹配在一起或者与j匹配的#即y[j]还可以找到其他#和它匹配{y[j] = i;//标记i j匹配 x[i] = j;return true;}}}return false;
}
int match_()//寻找最大匹配数，调用find()函数；
{int ans = 0;memset(x, -1, sizeof(x));//开始匹配前，清空数组memset(y, -1, sizeof(y));for(int i = 0; i < num; i++)//遍历num个#{memset(vis, 0, sizeof(vis));//第i个#尚未与其他#匹配if(find_(i)) ans++;//第i个#找到了与之相匹配的#; ans++;}return ans / 2;//无向图，故除以二
}
int main()
{int t, n, kase = 0;scanf("%d",&t);while(t--){num = 0;scanf("%d",&n);memset(p, 0, sizeof(p));memset(link, 0, sizeof(link));memset(s, 0, sizeof(s));for(int i = 0; i < n; i++)//输入scanf("%s",s[i]);for(int i = 0; i < n; i++)//为#编号{for(int j = 0; j < n; j++){if(s[i][j] == '#')p[i][j] = num++;}}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(s[i][j] == '#')//遍历所有的#，若有符合条件的#与之连通，标记二者{if(j < n-1 && s[i][j+1] == '#'){link[p[i][j]][p[i][j+1]] = 1;//无向图，i与j匹配和j与i匹配含义相同link[p[i][j+1]][p[i][j]] = 1;}if(i < n-1 && s[i+1][j] == '#'){link[p[i][j]][p[i+1][j]] = 1;link[p[i+1][j]][p[i][j]] = 1;}}}}
//        for(int i = 0; i < n; i++)
//        {
//            for(int j = 0; j < n; j++)
//                cout << p[i][j] << " ";
//            cout << endl;
//        }
//        cout << endl << endl;
//        for(int i = 0; i < n; i++)
//        {
//            for(int j = 0; j < n; j++)
//                cout << link[i][j] << " ";
//            cout << endl;
//        }int pp = match_();//输出最大匹配数printf("Case %d: %d\n",++kase,pp);}return 0;
}

这篇关于hdu 4185 Oil Skimming （二分匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---