HDU - 2444 The Accomodation of Students （判断二分图+匈牙利算法）
The Accomodation of StudentsTime Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 8705 Accepted Submission(s): 3830 Problem Description 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.
Input For each data set:
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 4 4 1 2 1 3 1 4 2 3 6 5 1 2 1 3 1 4 2 5 3 6
Sample Output No 3
Source 2008 Asia Harbin Regional Contest Online
Recommend gaojie |
就是让你先进行判断是否形成二分图，不能的话输出No,能的话输出最大匹配值；
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>ed[500];
int coler[500];
int vis[500];
int use[500];
bool dfs(int x, int col)
{
//cout << x << " " << col << endl;
coler[x] = col;
for (int s = 0; s < ed[x].size(); s++) {
if (coler[ed[x][s]] == col)return 0;
if (coler[ed[x][s]] == 0 && !dfs(ed[x][s], 3 - col))return 0;
}
return 1;
}
int find(int x)
{
for (int s = 0; s < ed[x].size(); s++) {
if (!vis[ed[x][s]]) {
vis[ed[x][s]] = 1;
if (use[ed[x][s]] == 0 || find(use[ed[x][s]]))
{
use[ed[x][s]] = x;
return 1;
}
}
}
return 0;
}
int main()
{
int n, m;
while (~scanf("%d%d", &n, &m))
{
memset(use, 0, sizeof(use));
memset(vis, 0, sizeof(vis));
memset(coler, 0, sizeof(coler));
for (int s = 1; s <= n; s++) {
ed[s].clear();
}
for (int s = 0; s < m; s++) {
int a, b;
scanf("%d%d", &a, &b);
ed[a].push_back(b);
ed[b].push_back(a);
}
int spot = 0;
for (int s = 1; s <= n; s++) {
if(coler[s]==0)
if (!dfs(s, 1)) {
cout << "No" << endl;
spot = 1;
break;
}
}
if (spot) continue;
int sum = 0;
for (int s = 1; s <= n; s++) {
memset(vis,0,sizeof(vis));
if (coler[s] == 1 && find(s)) {
sum++;
}
}
cout << sum << endl;
}
}
