FOJ 2232 匈牙利算法找二分图最大匹配
2024-09-06 12:36:11
尽量让每一个随从击败一个对手且随从全部存活,关键是为每一个随从找对手(递归过程),"腾"。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int used[];
int g[][]; //建立随从和对手的对战关系
int ee[];
int n;
struct people{
int live;
int attack;
}man[],enemy[];
bool find(int j) {
for(int k=;k<=n;k++) {
if(g[j][k] && used[k]==) {
used[k]=;
if(ee[k]== || find(ee[k])) {
ee[k]=j;
return true;
}
}
}
return false;
} int main() {
int test,all;
scanf("%d",&test);
while(test--) {
cin>>n;
all=;
memset(ee,,sizeof(ee));
memset(g,,sizeof(g));
for(int i=;i<=n;i++) {
scanf("%d%d",&man[i].live,&man[i].attack);
}
for(int i=;i<=n;i++) {
scanf("%d%d",&enemy[i].live,&enemy[i].attack);
}
for(int i=;i<=n;i++) {
for(int j=;j<=n;j++) {
g[i][j]=man[i].attack>=enemy[j].live&&man[i].live>enemy[j].attack;
}
}
int flag=;
for(int i=;i<=n;i++) {
memset(used,,sizeof(used));
if(!find(i)) {
flag=;
break;
}
}
if(flag==) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
return ;
}
最新文章
- 2016huasacm暑假集训训练四 递推_A
- Bzoj3943 [Usaco2015 Feb]SuperBull
- MyEclipse------execute()使用方法
- NRF51822之pstorage介绍
- MySQL Replication的相关文件
- 如何用Java解析CSV文件
- 未完成的任务之:下载、安装、体验 Gentoo
- Ogre实现简单地形
- 2-3 tree使用
- SQL SERVER 中 实现主表1行记录,子表多行记录 整合成一条虚拟列
- Kafka权威指南——broker的常用配置
- 使用samba共享文件夹,提供给window访问
- crontab清理日志
- ios中uitableview上拉刷新和下拉刷新(1)
- Navicat导出opencart2.3数据字典
- Go语言的传参和传引用[转]
- 相等(==)、严格相等(===)、NaN、null、undefined、空和0
- BSD Socket~TCP~Example Code
- Least slack time scheduling
- Docker 入门笔记