HDU-2444（二分图最大匹配+交叉染色法）

116 阅读 0 评论 77 点赞

我是靠谱客的博主昏睡水蜜桃，最近开发中收集的这篇文章主要介绍HDU-2444（二分图最大匹配+交叉染色法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.

Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.

Calculate the maximum number of pairs that can be arranged into these double rooms.

Input

For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.

Proceed to the end of file.

Output

If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.

Sample Input

Sample Output

No
3

先要判断这个图是不是二部图，判断用交叉染色法：就是将一个未染色的点染成白色，将与他周围相邻的点染成黑色，将黑色周围的点再染成白色，如果某个点已经染过色，并且和他周围相邻的点的颜色相同，则该图不是二部图。

就相当于染白色的点属于集合A，染黑色的点属于集合B，染过色的，且和周围颜色相同的及属于集合A，有属于集合B，这样不满足二部图的性质。所以他不是二部图。

判断二部图之后，利用匈牙利算法求最大匹配，无向图的最大匹配需要除以2.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 210;
int n,m;
int col[maxn];
struct Edge
{
int to;
int next;
}edge[maxn*maxn];
int head[maxn],tot;
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
memset(col,0,sizeof(col));
}
void addedge(int u,int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot ++;
}
int linker[maxn];
bool used[maxn];
bool dfs(int u)
{
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(!used[v])
{
used[v] = true;
if(linker[v] == -1 || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int res = 0;
memset(linker,-1,sizeof(linker));
for(int u = 1;u <= n;u ++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res ++;
}
return res;
}
bool judge_circul(int u)
{
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(!col[v])
{
col[v] = !col[u];
if(!judge_circul(v))
return false;
}
else if(col[v] == col[u])return false;
}
return true;
}
int main()
{
while(cin >> n >> m)
{
if(n == 1)
{
cout << "No" << endl;
break;
}
int u,v;
init();
while(m --)
{
cin >> u >> v;
addedge(u,v);
addedge(v,u);
}
col[1] = 1;
int ans = hungary();
if(!judge_circul(1))
cout << "No" <<endl;
else
cout << ans / 2 <<endl;
}
return 0;
}