HDU 3609 二分图多重匹配
2024-10-21 03:24:05
Escape
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 13005 Accepted Submission(s): 3258
Problem Description
2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.
Input
More set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000
Output
Determine whether all people can live up to these stars
If you can output YES, otherwise output NO.
If you can output YES, otherwise output NO.
Sample Input
1 1
1
1
2 2
1 0
1 0
1 1
Sample Output
YES
NO
AC代码
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n")
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl
#define ffread(a) fastIO::read(a)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+;//左集合大小
const int MAXM = ;//右集合大小
int uN,vN;//左右集合的数量
int g[MAXN][MAXM];
int linker[MAXM][MAXN];
bool used[MAXM];
int num[MAXM];//右集合的限制
bool dfs(int u)
{
for(int v = ; v < vN; v++)
if(g[u][v] && !used[v])
{
used[v] = true;
if(linker[v][] < num[v])
{
linker[v][++linker[v][]] = u;
return true;
}
for(int i = ; i <= num[v]; i++)
if(dfs(linker[v][i]))
{
linker[v][i] = u;
return true;
}
}
return false;
}
int hungary()
{
int res = ,flag=;
for(int i = ; i < vN; i++)
linker[i][] = ;
for(int u = ; u < uN; u++)
{
memset(used,false,sizeof(used));
if(dfs(u))
res++;
else //当前人不能匹配 直接就是NO了
{
flag=;
break;
}
}
return flag;
}
int main()
{
while(scanf("%d%d",&uN,&vN)!=EOF)
{
for(int i=;i<uN;i++)
for(int j=;j<vN;j++)
scanf("%d",&g[i][j]);
for(int i=;i<vN;i++)
scanf("%d",&num[i]);
if(hungary())
puts("NO");
else
puts("YES");
}
}
最新文章
- crontab安装和用法(定时任务)
- 七牛整合php上传从微信下载接口下载下来的文件
- [导读]Learning from Imbalanced Classes
- springMvc对json的支持
- jQuery使用之(四)处理页面的表单元素
- HDU Destroy Transportation system(有上下界的可行流)
- Error LNK2019: unresolved external symbol ";char * __stdcall _com_util::ConvertBSTRToString(wchar_t *)";
- 生成并返回 json 结果文件
- Windows下lex 与 yacc的使用
- Oracle百问百答(四)
- MySQL percona-toolkit工具包的使用教程
- Neutron数据库同步错误 NotImplementedError: No support for ALTER of constraints in SQLite dialect
- js跨域及解决方法
- 不知道的JavaScript
- 2014.3.6-C语言学习小结
- c++ 类的默认八种函数
- 18 UI美化自定义形状shape
- gin+gorm
- Sublime 个人常用快捷键
- Java并发知识分享
热门文章
- Android系统级技巧合集
- python大文件读取
- 如何在运行时改变App的图标
- C++中vector用法
- vue 组件内 directives指令的调用方式 <;base-table v-auto-height:tableHeight=";{vm:this, diffHeight:ahTable.diffHeight}";
- chart 图片组件 生成后不能动态更新,需要销毁dom,从新载入 用 v-if 和 this.$nextTick(() =>; {
- vue 数据没有驱动视图?
- rfcn讲解博客
- Hibernate初始化环境的基本封装
- zeromq编译与应用