M - Jamie's Contact Groups - poj 2289（二分图多重匹配）
2024-08-24 11:33:30
题意：某个人通讯录有很多人，现在他想把这个人分组，给的数据是可以把这个人分在那些组里面，现在他想知道分组后，人最多的那个组至少有多少人。
分析：因为没有给组限制有多少人，可以使用二分求出来最小的那个，感觉还是挺暴力的.....不过时间确实很少 500多ms
********************************************************************
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std; const int MAXN = ;
const int MAXM = ; bool G[MAXN][MAXM], used[MAXM];
int M, N;
struct Link
{///标记与y相连的边
int len, link[MAXN];
}Ly[MAXN]; bool Find(int i, int Mid)
{
for(int j=; j<M; j++)
{
if(G[i][j] && !used[j])
{
used[j] = true; if( Ly[j].len < Mid )
{
Ly[j].link[ Ly[j].len++ ] = i;
return true;
}
for( int k=; k<Ly[j].len; k++ )
{
if( Find( Ly[j].link[k], Mid ) == true )
{
Ly[j].link[k] = i;
return true;
}
}
}
} return false;
}
bool XYL(int Mid)
{///匈牙利的缩写....
memset(Ly, false, sizeof(Ly)); for(int i=; i<N; i++)
{
memset(used, false, sizeof(used));
if( Find(i, Mid) == false )
return false;
} return true;
} int main()
{
while(scanf("%d%d", &N, &M)!= EOF && M+N)
{
int i, v;
char ch, s[]; memset(G, false, sizeof(G));///记得初始化 for(i=; i<N; i++)
{
scanf("%s", s);
while(scanf("%d%c", &v, &ch))
{
G[i][v] = true;
if( ch == '\n' )
break;///不能输入的时候终止
}
} int L = , R = N, ans=N; while(L <= R)
{
int Mid = (L+R)>>; if( XYL(Mid) == true )
{
ans = Mid;
R = Mid - ;
}
else
L = Mid + ;
} printf("%d\n", ans);
} return ; }
最新文章
- [django]表格的添加与删除实例(可以借鉴参考)
- 移动h5开发资源整理
- static 类成员变量 和 static const类成员变量
- DOM--4 响应用户操作和事件（2）
- topcoder SRM 618 DIV2 MovingRooksDiv2
- oracle触发器及异常处理 简单例子
- [vijos P1014] 旅行商简化版
- ERP客户关系渠管理（二十）
- 键盘--android 隐藏系统键盘
- 从问题看本质: 研究TCP close_wait的内幕
- Jenkins详细安装与构建部署使用教程（转）
- HDU 1983 BFS&amp;&amp;DFS
- 清理微信浏览网站的缓存,Cookie
- CentOS 7 部署GitLab
- 比原链（Bytom）先知节点 Windows接入文档
- jersey 开启gzip
- Pancake Sorting LT969
- AndroidStudio意外崩溃，电脑重启，导致重启打开Androidstudio后所有的import都出错
- GDOI2018 涛涛摘苹果 [CDQ分治]
- 【CSS】Bootstrap中select2+popover冲突