BZOJ 1486: [HNOI2009]最小圈( 二分答案 + dfs判负圈 )
2024-10-13 19:54:52
二分答案m, 然后全部边权减掉m, 假如存在负圈, 那么说明有平均值更小的圈存在. 负圈用dfs判断.
---------------------------------------------------------------------------
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define clr(x, c) memset(x, c, sizeof(x))
#define foreach(i, x) for(__typeof(x.begin()) i = x.begin(); i != x.end(); i++)
using namespace std;
const int maxn = 3009;
const double eps = 1e-9;
struct edge {
int to;
double dist, w;
};
vector<edge> G[maxn];
int n;
double d[maxn];
bool vis[maxn], F;
void dfs(int x) {
vis[x] = true;
foreach(e, G[x]) if(d[e->to] > d[x] + e->w) {
if(!vis[e->to]) {
d[e->to] = d[x] + e->w;
dfs(e->to);
} else
F = true;
if(F) break;
}
vis[x] = false;
}
bool check(double m) {
rep(i, n) {
foreach(it, G[i]) it->w = it->dist - m;
vis[i] = false, d[i] = 0;
}
F = false;
rep(i, n) {
dfs(i);
if(F) return true;
}
return false;
}
int main() {
freopen("test.in", "r", stdin);
int m;
cin >> n >> m;
rep(i, n) G[i].clear();
while(m--) {
int u, v;
double d;
scanf("%d%d%lf", &u, &v, &d); u--, v--;
G[u].push_back( (edge) {v, d, 0} );
}
double L = -1e7, R = 1e7;
while(R - L > eps) {
double m = (L + R) / 2;
check(m) ? R = m : L = m;
}
printf("%.8lf\n", L);
return 0;
}
---------------------------------------------------------------------------
1486: [HNOI2009]最小圈
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1447 Solved: 679
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
HINT
Source
最新文章
- 【性能为王】从PHP源码剖析array_keys和array_unique
- 使用FileSystemWatcher监控文件夹及文件
- Invalidate,Update与Refresh的区别
- php笔试题(1)--转载
- ecshop退出登录会清空购物车的bug优化,最完美解决方法
- python开源包提交到pypi社区
- 【阿里云产品公测】离线归档OAS,在也不用备份担心空间了
- [转]PLS-S-00201, identifier &#39;CALLDEMO.GET_EMPLOYEES&#39; must be declared 预编译错误原因及解决办法
- github果然强大
- ViewPager 滑动页(一)
- Json,Gson,FastJson解析笔记
- jsp的标签库和自定义标签
- Asp.NetCore轻松学-配置服务 apollo 部署实践
- Mongo安装与使用
- docker-compose.yml(3)
- Hadoop问题:There are 0 datanode(s) running and no node(s) are excluded in this operation.
- java内部类(一)
- Expo大作战(三十四)--expo sdk api之LinearGradient(线性渐变),KeepAwake(保持屏幕不休眠),IntentLauncherAndroid,Gyroscope,
- 使用函数式编程消除重复无聊的foreach代码(Scala示例)
- SPOJ 687 REPEATS - Repeats