【【henuacm2016级暑期训练】动态规划专题 O】Robot Rapping Results Report
2024-08-27 22:37:50
【链接】 我是链接,点我呀:)
【题意】
让你确定一个最小的k
使得1..k这些比赛的结果能够推导出所有人之间的实力大小
【题解】
如果关系越多。那么就越能确定所有人之间的大小关系。
(多一点也能唯一确定。不嫌多
那么就二分一下k.
做一个拓扑排序。
如果能做唯一的拓扑排序。那么就ok
否则返回false.
【代码】
#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int M = 1e5;
int n,m,ru[M+10];
vector<pair<int,int> > g[M+10];
pair<int,int> a[M+10];
queue<int> dl;
bool ok(int mid){
memset(ru,0,sizeof ru);
for (int i = 1;i <= mid;i++){
ru[a[i].second]++;
}
int cnt = 0;
while (!dl.empty()) dl.pop();
for (int i = 1;i <= n;i++)
if (ru[i]==0){
dl.push(i);
}
while (!dl.empty()){
int x = dl.front();dl.pop();
cnt++;
if (!dl.empty()) return false;
for (auto y:g[x]){
if (y.second>mid) continue;
ru[y.first]--;
if (ru[y.first]==0) dl.push(y.first);
}
}
if (cnt==n) return true;
return false;
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= m;i++){
int x,y;
cin >> x >> y;
a[i] = {x,y};
g[x].push_back({y,i});
}
int l = 1,r = m,temp = -1;
while (l<=r){
int mid = (l+r)>>1;
if (ok(mid)){
r = mid - 1;temp = mid;
}else{
l = mid + 1;
}
}
cout<<temp<<endl;
return 0;
}
最新文章
- Android ooVoo Apk附件关联分析
- Vector 和 ArrayList 区别
- Ajax注册验证用户名是否存在 ——引自百度经验
- DOS下快速删除文件
- 如何重启Activity
- java连接access数据库
- Armitage主屏幕说明与命令行启动
- create tablespace 与 heap_insert 函数
- sublime text 2 前端编码神器-快捷键与使用技巧介绍
- 使用runloop阻塞线程的正确写法
- SciPy - 科学计算库(上)
- [JLOI2015]城池攻占
- AtomicInteger类的使用
- Java集合-ArrayList源码解析-JDK1.8
- Java基础 -- 访问控制权限
- 接口测试(二) 优化项目分层及cookies值带入
- mysql 开发进阶篇系列 47 物理备份与恢复(xtrabackup 的完全备份恢复,恢复后重启失败总结)
- 如何自学 Android 的?
- Json 文件中value的基本类型
- How To Use the AWK language to Manipulate Text in Linux
热门文章
- 最简单的tomcat安装部署
- mysql查询优化--临时表和文件排序(Using temporary; Using filesort问题解决)
- [Design]Ppt处理大段文字
- POJ 1091
- wordpress迁移以及遇到的一些问题[mysql备份导入导出][固定链接404]
- Hadoop使用Java进行文件修改删除操作
- [Node.js] Manage Configuration Values with Environment Variables
- STM32F030, 使用嘀嗒定时器Systick实现LED闪烁
- 有关计数问题的DP 划分数
- 2014秋C++ 第7周项目 数据类型和表达式