目录
B:HDU-2444 The Accomodation of Students
F:HDU-2389 Rain on your Parade
二分图定义与需要掌握的基础知识可参考二分图基础或二分图基础。
判断是否二分图
判断二分图的常见方法是染色法：用两种颜色，对所有顶点逐个染色，且相邻顶点染不同的颜色，如果发现相邻顶点染了同一种颜色，就认为此图不为二分图。 当所有顶点都被染色，且没有发现同色的相邻顶点，就退出。
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 505;
int m,n;
int color[N];
int edge[N][N];
bool dfs(int v, int c){
color[v] = c; //将当前顶点涂色
for(int i = 0; i < n; i++){ //遍历所有相邻顶点，即连着的点
if(edge[v][i] == 1){ //如果顶点存在
if(color[i] == c) //如果颜色重复，就返回false
return false;
if(color[i] == 0 && !dfs(i,-c)) //如果还未涂色，就染上相反的颜色-c,并dfs这个顶点，进入下一层
return false; //返回false
}
}
return true; //如果所有顶点涂完色，并且没有出现同色的相邻顶点，就返回true
}
void solve(){
for(int i = 0; i < n; i++){
if(color[i] == 0){
if(!dfs(i, 1)){
printf("NOT BICOLORABLE.
");
return;
}
}
}
printf("BICOLORABLE.
");
}
int main(){
int u,v;
while(cin >> n >> m){
memset(color, 0, sizeof(color));
memset(edge, 0, sizeof(edge));
for(int i = 0; i < m; i++){
cin >> u >> v; //因为是无向图，所以要往两个方向添加边
edge[u][v] = 1; //正着添加
edge[v][u] = 1; //反着添加
}
solve();
}
return 0;
}匈牙利算法（参考二分图匹配）
原理
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
-------等等，看得头大？那么请看下面的版本：
通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（-_-||暂时不考虑特殊的性取向），如果一对男女互有好感，那么你就可以把这一对撮合在一起，现在让我们无视掉所有的单相思（好忧伤的感觉），你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。
本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做：
===============================================================================
一： 先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，got it，连上一条蓝线
===============================================================================
二：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，got it
===============================================================================
三：接下来是3号男生，很遗憾1号女生已经有主了，怎么办呢？
我们试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子。
(黄色表示这条边被临时拆掉)
与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配()重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程)
此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去
2号男生可以找3号妹子~~~ 1号男生可以找2号妹子了~~~ 3号男生可以找1号妹子
所以第三步最后的结果就是：
===============================================================================
四： 接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好。
===============================================================================
这就是匈牙利算法的流程，其中找妹子是个递归的过程，最最关键的字就是“腾”字
其原则大概是：有机会上，没机会创造机会也要上
模板
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int line[N][N];
int girl[N],used[N];
int k,m,n;
bool found(int x)
{
for(int i=1; i<=n; i++)
{
if(line[x][i]&&!used[i])
{
used[i]=1;
if(girl[i]==0||found(girl[i]))
{
girl[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int x,y;
while(scanf("%d",&k)&&k)
{
scanf("%d %d",&m,&n);
memset(line,0,sizeof(line));
memset(girl,0,sizeof(girl));
for(int i=0; i<k; i++)
{
scanf("%d %d",&x,&y);
line[x][y]=1;
}
int sum=0;
for(int i=1; i<=m; i++)
{
memset(used,0,sizeof(used));
if(found(i)) sum++;
}
printf("%d
",sum);
}
return 0;
}KM算法（参考KM算法）
原理
现在有N男N女，有些男生和女生之间互相有好感，我们将其好感程度定义为好感度，我们希望把他们两两配对，并且最后希望好感度和最大。
怎么选择最优的配对方法呢？
首先，每个女生会有一个期望值，就是与她有好感度的男生中最大的好感度。男生呢，期望值为0，就是……只要有一个妹子就可以啦，不挑~~
这样，我们把每个人的期望值标出来。
接下来，开始配对。
配对方法：
我们从第一个女生开始，分别为每一个女生找对象。
每次都从第一个男生开始，选择一个男生，使男女两人的期望和要等于两人之间的好感度。
注意：每一轮匹配，每个男生只会被尝试匹配一次！
具体匹配过程：
==============为女1找对象===============
（此时无人配对成功）
根据 “男女两人的期望和要等于两人之间的好感度”的规则
女1-男1：4+0 != 3
女1-男3：4+0 == 4
所以女1选择了男3
女1找对象成功
==============为女1找对象成功============
==============为女2找对象===============
（此时女1—男3）
根据配对原则，女2选择男3
男3有主女1，女1尝试换人
我们尝试让女1去找别人
尝试失败
为女2找对象失败！
==============为女2找对象失败============
这一轮参与匹配的人有：女1，女2，男3。
怎么办？？？很容易想到的，这两个女生只能降低一下期望值了，降低多少呢？
任意一个参与匹配女生能换到任意一个这轮没有被选择过的男生所需要降低的最小值
比如：女1选择男1，期望值要降低1。 女2选择男1，期望值要降低1。 女2选择男2，期望值要降低2。
于是，只要期望值降低1，就有妹子可能选择其他人。所以妹子们的期望值要降低1点。
同时，刚才被抢的男生此时非常得意，因为有妹子来抢他，于是他的期望值提高了1点（就是同妹子们降低的期望值相同）。
于是期望值变成这样（当然，不参与刚才匹配过程的人期望值不变）
==============继续为女2找对象=============
（此时女1—男3）
女2选择了男1
男1还没有被配对
女2找对象成功！
==============为女2找对象成功=============
==============为女3找对象===============
（此时女1—男3，女2-男1）
女3没有可以配对的男生……
女3找对象失败
==============为女3找对象失败============
此轮只有女3参与匹配
此时应该为女3降低期望值
降低期望值1的时候，女3-男3可以配对，所以女3降低期望值1
==============继续为女3找对象============
（此时女1—男3， 女2-男1）
女3相中了男3
此时男3已经有主女1，于是女1尝试换人
女1选择男1
而男1也已经有主女2，女2尝试换人
前面说过，每一轮匹配每个男生只被匹配一次
所以女2换人失败
女3找对象再次失败
==============为女3找对象失败============
这一轮匹配相关人员：女1，女2，女3，男1，男3
此时，只要女2降低1点期望值，就能换到男2
（前面提过 只要任意一个女生能换到任意一个没有被选择过的男生所需要降低的最小值）
我们把相应人员期望值改变一下
==============还是为女3找对象============
（此时女1—男3， 女2-男1）
女3选择了男3
男3有主女1，女1尝试换人
女1换到了男1
男1已经有主女2，女2尝试换人
女2换人男2
男2无主，匹配成功！！！
==============为女3找对象成功=============
匹配成功！！！撒花~~
到此匹配全部结束
此时
女1-男1，女2-男2，女3-男3
好感度和为最大：9
虽然不停换人的过程听起来很麻烦，但其实整个是个递归的过程，实现起来比较简单。比较复杂的部分就是期望值的改变，但是可以在递归匹配的过程中顺带求出来。
模板
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d
", KM());
}
return 0;
}例题
A:HDU-1045 Fire Net：经典的二分图匹配问题，其实二分图问题难的在于建图，建图以后直接打模板就行了。横竖分区。先看每一列，同一列相连的空地同时看成一个点，显然这样的区域不能够同时放两个点。若一列被墙隔成两部分，则墙的上半部分和下半部分分别看成两个点。这些点作为二分图的X部。同理在对所有的行用相同的方法缩点，作为Y部。连边的条件（即x部内一点能和y部内一点匹配的条件）是两个区域有相交部分(即'.'的地方)。最后求最大匹配就是答案。若不懂可以看代码，代码挺好理解的，AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 8;
int cnt_row, cnt_col;
int row[N][N], col[N][N], r[N], c[N];
char mp[N][N];
bool path[N][N], vis[N];
int dfs(int rr)
{
for(int i = 0; i < cnt_col; i++)
{
if(path[rr][i] && vis[i] == false)
{
vis[i] = true;
if(c[i] == -1 || dfs(c[i]))
{
c[i] = rr;
r[rr] = i;
return 1;
}
}
}
return 0;
}
int hungarian()
{
int ans = 0;
memset(r, -1, sizeof(r));
memset(c, -1, sizeof(c));
for(int i = 0; i < cnt_row; i++)
if(r[i] == -1)
{
memset(vis, false, sizeof(vis));
ans += dfs(i);
}
return ans;
}
int main()
{
int n;
while(scanf("%d", &n) && n)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf(" %c", &mp[i][j]);
memset(row, -1, sizeof(row));
memset(col, -1, sizeof(col));
cnt_row = cnt_col = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
if(mp[i][j] == '.' && row[i][j] == -1)
{
for(int k = j; mp[i][k] == '.' && k < n; k++) //相连的'.'看成一个点
row[i][k] = cnt_row;
cnt_row++;
}
if(mp[i][j] == '.' && col[i][j] == -1)
{
for(int k = i; mp[k][j] == '.' && k < n; k++)
col[k][j] = cnt_col;
cnt_col++;
}
}
memset(path, false, sizeof(path));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(mp[i][j] == '.') //连边的条件
path[row[i][j]][col[i][j]] = true;
printf("%d
", hungarian());
}
return 0;
}B:HDU-2444 The Accomodation of Students:首先利用染色法判断一下这个图是否是一个二分图，然后找最大二分匹配，找的过程中为了简单化，把两边均看成有n个点，即正反都记录，求出最终结果，然后用找到的匹配数除以2 就是正确答案
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 505;
int m,n;
int color[N];
int edge[N][N];
int girl[N],used[N];
bool dfs(int v, int c){
color[v] = c; //将当前顶点涂色
for(int i = 0; i < n; i++){ //遍历所有相邻顶点，即连着的点
if(edge[v][i] == 1){ //如果顶点存在
if(color[i] == c) //如果颜色重复，就返回false
return false;
if(color[i] == 0 && !dfs(i,-c)) //如果还未涂色，就染上相反的颜色-c,并dfs这个顶点，进入下一层
return false; //返回false
}
}
return true; //如果所有顶点涂完色，并且没有出现同色的相邻顶点，就返回true
}
int solve(){
for(int i = 0; i < n; i++){
if(color[i] == 0){
if(!dfs(i, 1)){
return 0;
}
}
}
return 1;
}
bool found(int x)
{
for(int i=1; i<=n; i++)
{
if(edge[x][i]&&!used[i])
{
used[i]=1;
if(girl[i]==0||found(girl[i]))
{
girl[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
int u,v;
while(cin >> n >> m){
memset(color, 0, sizeof(color));
memset(edge, 0, sizeof(edge));
for(int i = 0; i < m; i++){
cin >> u >> v; //因为是无向图，所以要往两个方向添加边
edge[u][v] = 1; //正着添加
edge[v][u] = 1; //反着添加
}
if(!solve()||n==1){
printf("No
");
continue;
}
memset(girl,0,sizeof(girl));
int sum=0;
for(int i=1; i<=n; i++)
{
memset(used,0,sizeof(used));
if(found(i)) sum++;
}
printf("%d
",sum/2);
}
return 0;
}C:HDU-1083 Courses:一道模板题，AC代码：
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int N = 505;
int m,n;
int edge[N][N];
int used[N];
int girl[N];
bool found(int x)
{
for(int i=1; i<=m; i++)
{
if(edge[x][i]&&!used[i])
{
used[i]=1;
if(girl[i]==0||found(girl[i]))
{
girl[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
int u,v,t;
cin>>t;
while(t--){
cin>>n>>m;
memset(edge, 0, sizeof(edge));
memset(girl,0,sizeof(girl));
for(int i = 1; i <=n; i++){
cin>>u;
for(int j=1;j<=u;j++){
cin>>v;
edge[i][v] = 1;
}
}
int sum=0;
for(int i=1; i<=n; i++)
{
memset(used,0,sizeof(used));
if(found(i))
sum++;
}
if(sum==n)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}D:HDU-1281 棋盘游戏:这是一道匈牙利算法加暴力的题目。将横坐标和纵坐标分别看成是两幅图，（相当于分别为每一行找到对应能匹配的列，然后换下一行）二分图匹配，最后在便利每一个给出的可能的节点，看是否为重要点。AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int xx[121], yy[121];
int ma[121][121];
int n, m, k;
bool v[121];
int match[121];
bool bfs(int a)
{
for(int j=1;j<=m;j++)
{
if(ma[a][j]==1&&v[j]==false)
{
v[j] = true;
if(match[j]==-1||bfs(match[j]))
{
match[j] = a;
return true;
}
}
}
return false;
}
int XYL()
{
int sum = 0;
memset(match, -1, sizeof(match));
for(int i=1;i<=n;i++)
{
memset(v, false, sizeof(v));
if(bfs(i)==true)
sum++;
}
return sum;
}
int main()
{
int t = 0;
while(~scanf("%d %d %d", &n, &m, &k))
{
t++;
memset(ma, 0, sizeof(ma));
for(int i=0;i<k;i++)
{
scanf("%d %d", &xx[i], &yy[i]);
if(!ma[xx[i]][yy[i]])
ma[xx[i]][yy[i]] = 1;
}
int s = XYL();
int ans = 0;
for(int i=0;i<k;i++)
{
ma[xx[i]][yy[i]] = 0;
int ss = XYL();
if(ss<s)
ans++;
ma[xx[i]][yy[i]] = 1;
}
printf("Board %d have %d important blanks for %d chessmen.
", t, ans, s);
}
return 0;
}E:HDU-2819 Swap:构建二分图行和列匹配，如果不能完全匹配，那么就输出-1。可以的话，根据match[i]匹配的结果，就是答案的列应该怎么排列的结果，最后一定是存在只交换列（或者行）就可以满足题意的方式。AC代码：
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,G[110][110],match[110],vis[110],VIS,f[110],ans[110][2];
bool dfs(int u)
{
int i;
for(i=1;i<=n;i++)
if(G[i][u] && vis[i]!=VIS)
{
vis[i]=VIS;
if(match[i]==0 || dfs(match[i]))
{
match[i]=u;
return true;
}
}
return false;
}
int main()
{
int i,j,k,ret;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&G[i][j]);
memset(match,0,sizeof(match));
ret=0;
for(i=1;i<=n;i++)
{
VIS++;
if(dfs(i))
ret++;
}
if(ret<n)
{
printf("-1
");
continue;
}
m=0;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=n;i++)
{
if(match[i]!=f[i])
{
for(j=i+1;j<=n;j++)
if(match[i]==f[j])
break;
m++;
ans[m][0]=i;
ans[m][1]=j;
f[j]=f[i];
}
}
printf("%d
",m);
for(i=1;i<=m;i++)
printf("C %d %d
",ans[i][0],ans[i][1]);
}
}F:HDU-2389 Rain on your Parade:需要用到HK算法，可以在网上查找HK的思路，AC代码（HK模板）：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN=3005;//最大点数
const int INF=0x3f3f3f3f;//距离初始值
int Map[MAXN][MAXN];//二分图
int cx[MAXN];//cx[i]表示左集合i顶点所匹配的右集合的顶点序号
int cy[MAXN];//cy[i]表示右集合i顶点所匹配的左集合的顶点序号
int n,m,dis;
int dx[MAXN],dy[MAXN];//dx[i]表示左集合i顶点所在层数
bool vis[MAXN];//dy[i]表示在有集合i顶点所在的层数
int xp[3005],yp[3005],s[3005];
int xu[3005],yu[3005];
bool searchpath(){
queue<int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=n;++i){
//cx[i]表示左集合i顶点所匹配的右集合的顶点序号
if(cx[i]==-1){
//将未遍历的节点入队并初始化次节点距离为0
Q.push(i);
dx[i]=0;
}
}
//广度搜索增广路径
while(!Q.empty()){
int u=Q.front();
Q.pop();
if(dx[u]>dis)break;//找到新的增广路就跳出
//取右侧节点
for(int i=1;i<=m;++i){
//右侧节点的增广路径的距离
if(Map[u][i]&&dy[i]==-1){
dy[i]=dx[u]+1;//v对应的距离为u对应距离加1
if(cy[i]==-1)dis=dy[i];//找到了一条增广路
else{
dx[cy[i]]=dy[i]+1;
Q.push(cy[i]);
}
}
}
}
return dis!=INF;
}
//寻找路径深度搜索
int findpath(int s){
for(int i=1;i<=m;++i){
//如果该点没有被遍历过并且距离为上一节点+1
if(!vis[i]&&Map[s][i]&&dy[i]==dx[s]+1){
//对该点染色
vis[i]=1;
if(cy[i]!=-1&&dy[i]==dis)continue;//因为是广搜，也可能是左集合里两个同层次的点同时找到了右集合里的同一个点作为新的增广路，那么这个点在被用过一次后，第二次就不能用了
if(cy[i]==-1||findpath(cy[i])){
cy[i]=s;cx[s]=i;
return 1;
}
}
}
return 0;
}
//得到最大匹配的数目
int MaxMatch(){
int res=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(searchpath()){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i){
if(cx[i]==-1)res+=findpath(i);
}
}
return res;
}
int main(){
int T;
scanf("%d",&T);
for(int q=1;q<=T;++q){
memset(Map,0,sizeof(Map));
int t;
scanf("%d",&t);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d%d",&xp[i],&yp[i],&s[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&xu[i],&yu[i]);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if((xp[i]-xu[j])*(ll)(xp[i]-xu[j])+(yp[i]-yu[j])*(ll)(yp[i]-yu[j])<=t*(ll)t*s[i]*s[i]){
Map[i][j]=1;
}
}
}
printf("Scenario #%d:
%d
",q,MaxMatch());
}
return 0;
}G:HDU-4185 Oil Skimming:和A题思路差不多，把有相关的两个点连在一起即可，AC代码：
#include<stdio.h>
#include<string.h>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
const int inf=0x3f3f3f3f;
using namespace std;
int g[602][602];
int vis[602];
int line[602];
int sum;
int find1(int v)
{
for(int i=1; i<=sum; i++)
{
if(vis[i]==0&&g[v][i])
{
vis[i]=1;
if(line[i]==-1||find1(line[i]))
{
line[i]=v;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
int r=0;
char a[602][602];
int pos[602][602];
while(t--)
{
int n;
scanf("%d",&n);
memset(g,0,sizeof(g));
memset(pos,0,sizeof(pos));
memset(vis,0,sizeof(vis));
memset(line,-1,sizeof(line));
sum=0;
for(int i=0; i<n; i++)
{
scanf("%s",a[i]);
for(int j=0; j<n; j++)
if(a[i][j]=='#')//编号
pos[i][j]=++sum;
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
if(a[i][j]=='#')//上下左右有石油的话就将这两块联系一下
{
if(i-1>=0&&a[i-1][j]=='#')
g[pos[i-1][j]][pos[i][j]]=g[pos[i][j]][pos[i-1][j]]=1; //由于纵坐标一样，相当于从这4个中选出来一个匹配
if(i+1<n&&a[i+1][j]=='#')
g[pos[i+1][j]][pos[i][j]]=g[pos[i][j]][pos[i+1][j]]=1;
if(j-1>=0&&a[i][j-1]=='#')
g[pos[i][j-1]][pos[i][j]]=g[pos[i][j]][pos[i][j-1]]=1;
if(j+1<n&&a[i][j+1]=='#')
g[pos[i][j+1]][pos[i][j]]=g[pos[i][j]][pos[i][j+1]]=1;
}
}
int ans=0;
for(int i=1; i<=sum; i++)
{
memset(vis,0,sizeof(vis));
if(find1(i))
ans++;
}
printf("Case %d: %d
",++r,ans/2);
}
}H:POJ-3020 Antenna Placement:二分匹配 中 最小路径覆盖
最小路径覆盖：取图中的一些路径，使之能覆盖图中所有顶点（本题关键），并且任何顶点有且只有一条路径与之关联。也就是说，如果把这些路径中的每条路径从它的起始点走到终点，那么恰好可以经过图中的顶点有且只有一次。 最小路径覆盖与二分匹配的关系： 最小路径覆盖＝ 总顶点数－最大匹配数；（无向图 记得 /2）AC代码：
#include<stdio.h>
#include<string.h>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
const int inf=0x3f3f3f3f;
using namespace std;
int g[602][602];
int vis[602];
int line[602];
int sum;
int find1(int v)
{
for(int i=1; i<=sum; i++)
{
if(vis[i]==0&&g[v][i])
{
vis[i]=1;
if(line[i]==-1||find1(line[i]))
{
line[i]=v;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
char a[602][602];
int pos[602][602];
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(g,0,sizeof(g));
memset(pos,0,sizeof(pos));
memset(vis,0,sizeof(vis));
memset(line,-1,sizeof(line));
sum=0;
for(int i=0; i<n; i++)
{
scanf("%s",a[i]);
for(int j=0; j<m; j++)
if(a[i][j]=='*')//编号
pos[i][j]=++sum;
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(a[i][j]=='*')//上下左右有石油的话就将这两块联系一下
{
if(i-1>=0&&a[i-1][j]=='*')
g[pos[i-1][j]][pos[i][j]]=g[pos[i][j]][pos[i-1][j]]=1;
if(i+1<n&&a[i+1][j]=='*')
g[pos[i+1][j]][pos[i][j]]=g[pos[i][j]][pos[i+1][j]]=1;
if(j-1>=0&&a[i][j-1]=='*')
g[pos[i][j-1]][pos[i][j]]=g[pos[i][j]][pos[i][j-1]]=1;
if(j+1<n&&a[i][j+1]=='*')
g[pos[i][j+1]][pos[i][j]]=g[pos[i][j]][pos[i][j+1]]=1;
}
}
int ans=0;
for(int i=1; i<=sum; i++)
{
memset(vis,0,sizeof(vis));
if(find1(i))
ans++;
}
printf("%d
",sum-ans/2);
}
}