HDU2444 :The Accomodation of Students(二分图染色+二分图匹配)
The Accomodation of Students
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9477 Accepted Submission(s): 4165
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444
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.
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:
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6
Sample Output:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int link[N][N],match[N],check[N],color[N];
int n,m,ans=; inline void init(){
ans=;memset(color,-,sizeof(color));
memset(link,,sizeof(link));memset(match,-,sizeof(match));
} inline int dfs(int x){
for(int i=;i<=n;i++){
if(link[x][i] && !check[i]){
check[i]=;
if(match[i]==- || dfs(match[i])){
match[i]=x;
return ;
}
}
}
return ;
}
inline bool ok(int x){ //二分图染色
for(int i=;i<=n;i++){
if(link[x][i]){
if(color[i]==-){
color[i]=-color[x];
if(!ok(i)) return false;
}else if(color[i]==color[x]) return false ;
}
}
return true;
}
/*dfs实现 ,连通图直接调用ok(1,0)
inline bool ok(int x,int c){
color[x]=c;
for(int i=1;i<=n;i++){
if(link[x][i]){
if(color[i]==-1){
if(!ok(i,1-color[x])) return false;
}else if(color[i]==color[x]) return false ;
}
}
return true;
}
*/
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
link[a][b]=;
link[b][a]=;
}
bool flag=false ;
for(int i=;i<=n;i++){
if(color[i]==-){
color[i]=;
if(!ok(i)){
flag=true;break;
}
}
}
if(flag){
puts("No");continue;
}
for(int i=;i<=n;i++){
memset(check,,sizeof(check));
if(dfs(i)) ans++;
}
printf("%d\n",ans/);
}
return ;
}
最新文章
- webpack配置别名alias出现的错误匹配
- Android带边框表格的实现
- Mongodb插入记录
- Integrated Circuit Intro
- HDU 1394 Minimum Inversion Number(线段树/树状数组求逆序数)
- JS生成二维码,支持中文字符
- Unity3d物体模型(实现旋转缩放平移自动旋转)
- ApexSql Log
- 前端学PHP之正则表达式基础语法
- TopCoder SRM 566 Div 1 - Problem 1000 FencingPenguins
- MyCat分片规则--笔记(二)
- Java的家庭记账本程序(H) :微信小程序 image 标签,在模拟器中无法显示图片?(已解决)
- R画图的颜色搭配
- luogu P1072 $Hankson$ 的趣味题
- Android webview clearHistory 不符合逾期的解决办法
- WP8.1学习系列(第二章)——Toast通知
- 洛咕 P2465 [SDOI2008]山贼集团
- Mysql优化之索引
- 微信小程序四(设置底部导航)
- Linux Shell之表达式