HDU3605 Escape —— 二分图多重匹配
2024-08-29 13:39:12
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3605
Escape
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 10349 Accepted Submission(s): 2476
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.
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
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
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
1
1
2 2
1 0
1 0
1 1
Sample Output
YES
NO
NO
题解:
二分图多重匹配的裸题,但要适当修改以防止超时。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
//#define LOCAL
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+;
const int maxn = 1e5+; int n, m;
int linker[][maxn];
int g[maxn][];
bool used[];
int num[]; bool dfs(int u)
{
for(int v = ; v<=m; 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;
} bool hungary()
{
for(int v = ; v<=m; v++)
linker[v][] = ;
for(int u = ; u<=n; u++)
{
memset(used,,sizeof(used));
if(!dfs(u)) return false; //如果这个人匹配不到,则直接退出。否则会超时。
}
return true;
} int main()
{
#ifdef LOCAL
freopen("", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i = ; i<=n; i++)
for(int j = ; j<=m; j++)
scanf("%d",&g[i][j]);
for(int i = ; i<=m; i++)
scanf("%d",&num[i]); if(hungary()) puts("YES");
else puts("NO");
}
}
最新文章
- 在网上摘录一段对于IOC的解析,比较直观,大家观摩观摩
- 移动端 css实现自适应正圆 ( 宽高随着手机屏幕宽度自适应 )
- 首师大附中科创教育平台 我的刷题记录 0325 50212228海岛帝国:LYF的太空运输站
- js之规范代码写法
- AS3全局与局部坐标转换
- python 练习多级菜单思路
- iscroll.js的使用
- PHP基础语法: echo,var_dump, 常用函数:随机数:拆分字符串:explode()、rand()、日期时间:time()、字符串转化为时间戳:strtotime()可变参数的函数:PHP里数组长度表示方法:count($attr[指数组]);字符串长度:strlen($a)
- 触发UIButton长按事件
- SOAP 简单对象访问协议
- MVC与三层架构的关系
- nginx 编译参数
- Java 基础知识总结
- CoreData归纳使用
- 指令-arModal-点击提示框模板
- ssh连接远程主机执行脚本的环境变量问题
- 关于HashMap的一些深入探索与理解
- 爬虫json数据的处理
- importlib的用法
- PAT甲题题解-1042. Shuffling Machine (20)-模拟