HDU - 2444 二分图最大匹配 之 判断二分图+匈牙利算法
2024-09-07 09:35:36
题意：第一行给出数字n个学生，m条关系，关系表示a与b认识，判断给定数据是否可以构成二分图，如果可以，要两个互相认识的人住一个房间，问最大匹配数（也就是房间需要的最小数量）
思路：要看是否可以构成二分图，就是二分图的判断，这里主要记录一下自己想的判断方法：用一个数组记录分类，0表示这个人没有被分类，1，2表示二分图两个部分，边输入边判断是否是二分图，如果两个人都是0，那么将这两个人分别赋值1，2即可，若两人数值不相同，但有一个为0，将为零的这个赋值1或2，，若两人值相等且不为0，说明矛盾了，flag=1。分出两个不同的1，2两组后，套模板即可。（网上用广搜判断）
#include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#define N 220
using namespace std;
int book[N],n,m,e[N][N],L[N];
bool dfs(int u)
{
for(int i=1; i<=n; i++)
{
if(!book[i]&&e[u][i])//如果没有被连过并且可以连
{
book[i]=1;//标记一下，协助寻找增广路（找数据代入一遍就明白了）
if(dfs(L[i])||L[i]==0)//寻找增广路
{
L[i]=u;//记录路径
return 1;
}
}
}
return 0;
}
bool bfs()
{
//相当于染色,e[v][i]的v和i不能是相同颜色
//0 1两种颜色，如果遇到已经染过颜色的，并且相同，就false
int judge[220];
memset(judge,-1,sizeof(judge));
queue<int> q;
q.push(1);
judge[1]=0;
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=1;i<=n;++i)
{
if(e[v][i])
{
if(judge[i]==-1)
{
judge[i]=(judge[v]+1)%2;
q.push(i);
}
else
{
if(judge[i]==judge[v])
return false;
}
}
}
}
return true;
}
int main()
{
int a[220],x[220],y[220],t1,t2;
while(~scanf("%d%d",&n,&m))
{
for(int i=1; i<=n; i++)
{
a[i]=0;
for(int j=1; j<=n; j++)
e[i][j]=e[j][i]=0;
}
int flag=0;
/* 以下二分图的判断 */
for(int i=1; i<=m; i++)
{
scanf("%d%d",&t1,&t2);
e[t1][t2]=e[t2][t1]=1;
x[i]=t1,y[i]=t2;
if(a[t1]==a[t2]&&a[t1]==0)
a[t1]=1,a[t2]=2;
else if(a[t1]!=a[t2]&&a[t1]==0)
{
if(a[t2]==2)
a[t1]=1;
else a[t1]=2;
}
else if(a[t1]!=a[t2]&&a[t2]==0)
{
if(a[t1]==2)
a[t2]=1;
else a[t2]=2;
}
else if(a[t1]==a[t2])
flag=1;
}
/*以上 二分图的判断*/
if(flag)
printf("No\n");
else
{
memset(L,0,sizeof(L));
int sum=0;
for(int i=1; i<=n; i++)
{
memset(book,0,sizeof(book));
if(dfs(i)&&a[i]==1)//注意条件！！！
sum++;
}
printf("%d\n",sum);
}
}
return 0;
}
最新文章
- ABP理论学习之功能管理
- AIX 5L 系统管理技术 —— 存储管理——卷组
- asp.net 读取一个文本文件，并输出到网页显示 通过 一般处理程序实现
- android服务之启动方式
- IRelationalOperator空间关系接口简介
- codechef Arranging Cup-cakes题解
- CSS框模型（框模型概述、内边距、边框、外边距、外边距合并）
- java中的多线程——进度2
- 引用 模块编译Makefile模板
- VUE2.0实现购物车和地址选配功能学习第四节
- vue-ajax小封装
- 在64位系统下，指向int型的指针占的内存空间多大？
- 转：visualvm监控远程机器上的Java程序
- pythonのdjango 在控制台用log打印操作日志
- MySQL Execution Plan--IN子查询包含超多值引发的查询异常1
- mysql数据表的基本操作:表结构操作，字段操作
- BZOJ1283 序列 网络流区间覆盖模型
- 在多任务（RTOS）环境中使用看门狗
- js中用户名的正则（字符，数字，下划线，减号）
- redis、memcache、mongoDB 对比