hdu2413 二分+二分匹配
匹配 二分
2023-09-11 14:13:59 时间
题意:
地球和外星球大战,地球有n个飞船,外星球有m个飞船,每个飞船有自己的其实战舰和战舰增长率,星球于星球之间有距离,问你最少多少年地球可以打败外星球,每个星球最多只能和一个星球对战...
思路:
题意的最后一句话告诉我们这个题目满足二分图,我们可以二分枚举多少年打败,每次都重新建图,对于H[i] , 和 A[j],如果当前二分:
地球和外星球大战,地球有n个飞船,外星球有m个飞船,每个飞船有自己的其实战舰和战舰增长率,星球于星球之间有距离,问你最少多少年地球可以打败外星球,每个星球最多只能和一个星球对战...
思路:
题意的最后一句话告诉我们这个题目满足二分图,我们可以二分枚举多少年打败,每次都重新建图,对于H[i] , 和 A[j],如果当前二分:
(mid - map[i][j]) * H[i].p + H[i].st >= A[i].p * mid + A[i].st ,(地球攻击外星球,所以跑路的时间是地球付出) 就建边i,j,然后二分匹配,如果得到的匹陪数是外星战舰数,那么满足,则 up = mid - 1.........
#include<stdio.h> #include<string.h> #define N_node 250 + 100 #define N_edge 250 * 250 + 1000 #define INF 2000000000 typedef struct { int to ,next; }STAR; typedef struct { __int64 st ,p; }NODE; NODE H[N_node] ,A[N_node]; STAR E[N_edge]; __int64 map[N_node][N_node]; int mk_gx[N_node] ,mk_dfs[N_node]; int list[N_node] ,tot; void add(int a ,int b) { E[++tot].to = b; E[tot].next = list[a]; list[a] = tot; } int DFS_XYL(int s) { for(int k = list[s] ;k ;k = E[k].next) { int to = E[k].to; if(mk_dfs[to]) continue; mk_dfs[to] = 1; if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])) { mk_gx[to] = s; return 1; } } return 0; } void Buid(__int64 mid ,int n ,int m) { memset(list ,0 ,sizeof(list)); tot = 1; for(int i = 1 ;i <= n ;i ++) for(int j = 1 ;j <= m ;j ++) { __int64 h = (mid - map[i][j]) * H[i].p + H[i].st; __int64 a = mid * A[j].p + A[j].st; if(h >= a) add(i ,j); } } bool OK(int n ,int m) { int sum = 0; memset(mk_gx ,255 ,sizeof(mk_gx)); for(int i = 1 ;i <= n ;i ++) { memset(mk_dfs ,0 ,sizeof(mk_dfs)); sum += DFS_XYL(i); } return sum == m; } int main () { int i ,j ,n ,m; while(~scanf("%d %d" ,&n ,&m) && n + m) { for(i = 1 ;i <= n ;i ++) scanf("%I64d %I64d" ,&H[i].st ,&H[i].p); for(i = 1 ;i <= m ;i ++) scanf("%I64d %I64d" ,&A[i].st ,&A[i].p); for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= m ;j ++) scanf("%I64d" ,&map[i][j]); if(n < m) { printf("IMPOSSIBLE\n"); continue; } __int64 low ,mid ,up; low = 0; up = INF; int ans = -1; while(low <= up) { mid = (low + up) >> 1; Buid(mid ,n ,m); if(OK(n ,m)) { up = mid - 1; ans = mid; } else low = mid + 1; } if(ans == -1) printf("IMPOSSIBLE\n"); else printf("%d\n" ,ans); } return 0; }
相关文章
- hdu1526 二分匹配+ floyd
- POJ 3014:Asteroids(二分匹配,匈牙利算法)
- 【华为OD机试真题 python】字符串匹配 【2022 Q4 | 200分】
- 图像的视差匹配(Stereo Matching)
- 一则> ORA-12704: character set mismatch 字符集不匹配的错误处理 原因:varchar2 跟nvarchar2
- hihoCoder #1122 : 二分图二•二分图最大匹配之匈牙利算法
- <转> 二分图多重匹配问题
- 前端自动化测试框架Jest中的匹配器
- 从零开始学正则(二),如何用正则匹配特定位置?理解正则的锚,先行断言
- 匹配手机号码
- UVaLive 6525 Attacking rooks (二分图最大匹配)
- HDU 3729 I'm Telling the Truth (二分匹配)
- Java经典实例:在文本中匹配换行符
- 文件上传和字段匹配
- grep, egrep, fgrep - 打印匹配给定模式的行
- 正则表达式加参数匹配
- 【POJ 1698】Alice's Chance(二分图多重匹配)
- 二分图的最大匹配
- hdu5414(2015多校10)--CRB and String(字符串匹配)
- hdu 1083 Courses (最大匹配)
- 【bzoj2044】三维导弹拦截 dp+二分图最大匹配
- 【bzoj3291】Alice与能源计划 模拟费用流+二分图最大匹配
- 【bzoj4443】[Scoi2015]小凸玩矩阵 二分+二分图最大匹配