关键词：
[BZOJ1486][HNOI2009]最小圈
试题描述
输入
见“试题描述”
输出
输入示例
4 5 1 2 5 2 3 5 3 1 5 2 4 3 4 1 3
输出示例
3.66666667
数据规模及约定
见“试题描述”
题解
分数规划，二分答案 x 后每条边的边权减去 x，若有负环则表明答案小于等于 x。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
return x * f;
}
#define maxn 3010
#define maxm 10010
#define LL long long
int n, m, head[maxn], nxt[maxm], to[maxm];
LL dist[maxm], eval[maxm];
void AddEdge(int a, int b, LL c) {
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
return ;
}
LL d[maxn];
bool vis[maxn];
bool spfa(int u) {
vis[u] = 1;
for(int e = head[u]; e; e = nxt[e]) if(d[to[e]] >= d[u] + eval[e]) {
if(vis[to[e]]) return 1;
d[to[e]] = d[u] + eval[e];
if(spfa(to[e])) return 1;
}
vis[u] = 0;
return 0;
}
bool has_ncyc() {
memset(vis, 0, sizeof(vis));
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; i++)
if(spfa(i)) return 1;
return 0;
}
int main() {
LL l = 0, r = 0;
n = read(); int M = read();
for(int i = 1; i <= M; i++) {
int a = read(), b = read(); LL c = (LL)read() * 2000000000ll;
AddEdge(a, b, c); r += c;
}
l = -r;
while(l < r) {
LL mid = l + r >> 1;
for(int i = 1; i <= m; i++) eval[i] = dist[i] - mid;
if(has_ncyc()) r = mid; else l = mid + 1;
}
printf("%.8lf
", (double)l / 2e9);
return 0;
}
bzoj1486[hnoi2009]最小圈
bzoj1486[HNOI2009]最小圈题意：定义图中一个环的平均值为环上边权和除以（浮点除法）边数，求一个图中的最小环平均值，保留8位。n≤3000，m≤10000，有负权边。题解：这就是比较明显的01分数规划了，见bzoj1690。同时根据题解二... 查看详情
[bzoj1486][hnoi2009]最小圈
[BZOJ1486][HNOI2009]最小圈bzojluogu题意你有一张有向图，保证连通，保证存在至少一个环。你需要找到一个环，最小化环的平均权值。环的平均值定义为环的总权值除以环长。sol分数规划。可以看做每条边的\(b_i=1\)。二分一个\(mid\)，... 查看详情
bzoj1486hnoi2009—最小圈
...规定一个数值u表示图中一个环的权值/环中节点个数。求最小的u。Solution 尼玛今天考试题，不知道是考二分的话这真的做不出。。 二分一个答案ans，这个答案可行当且仅当ans>=∑w/cnt，cnt表示环 查看详情
bzoj_1486_[hnoi2009]最小圈_01分数规划
BZOJ_1486_[HNOI2009]最小圈_01分数规划DescriptionInputOutputSampleInput45125235315243413SampleOutput3.66666667 二分答案，边权减去答案，判负环即可。然而spfa判负环会T掉，于是我使用了dfs判负环的方法。dfs判负环代码：voiddfs(intx)vis[x]=1;inti;for(i... 查看详情
bzoj1486：[hnoi2009]最小圈——题解(代码片段)
https://www.lydsy.com/JudgeOnline/problem.php?id=1486https://www.luogu.org/problemnew/show/P3199题面太鬼畜就不粘了。这题唯一正确的解法是https://www.luogu.org/blog/user7868/solution-p3199虽然我看不懂。当然为了AC这道题于是抛弃自己的灵魂写了dfs-spf 查看详情
bzoj1486[hnoi2009]最小圈
【算法】二分+spfa【题解】据说这个叫分数规划？0-1分数规划二分答案a，则对于任意的环有w/k≤a即w-ak≤0，若满足条件则a变小，否则a变大。因为w=w1+w2+...+wk，所以变形为(w1-a)+(w2-a)+...+(wk-a)≤0。于是问题转化为在图中找负环。不... 查看详情
bzoj千题计划227：bzo1486:[hnoi2009]最小圈j
http://www.lydsy.com/JudgeOnline/problem.php?id=1486 二分答案dfs版spfa判负环 #include<queue>#include<cstdio>#include<cstring>#include<iostream>#defineN3001#defineM10001usingn 查看详情
bzoj1486[hnoi2009]最小圈分数规划+spfa
题目描述样例输入45125235315243413样例输出3.66666667题解分数规划+Spfa判负环二分答案mid，并将所有边权减去mid，然后再判负环，若有负环则调整下界，否则调整上界，直至上下界基本重合。证明：显然 由于有(c+d)/(a+b+k)＞(c+d)/(a+... 查看详情
bzoj1486最小圈[分数规划+负权环]
Description考虑带权的有向图(G=(V,E))以及(w:E ightarrowR),每条边(e=(i,j)(i eqj,iinV,jinV))的权值定义为(w_{i,j})，令(n=|V|)。(c=(c_1,c_2,cdots,c_k)(c_iinV))是(G)中的一个圈当且仅当((ci,ci+1)(1≤i<k))和((ck,c1)) 查看详情
[hnoi2009]最小圈
hnoi2009最小圈Description #include<iostream>#include<cstdio>#include<cstring>#definemaxn3005#definemaxe10005usingnamespacestd;structEdge{ intv; doublew; int 查看详情
[hnoi2009]最小圈
Description对于一张有向图，要你求图中最小圈的平均值最小是多少，即若一个圈经过k个节点，那么一个圈的平均值为圈上k条边权的和除以k，现要求其中的最小值Input第一行2个正整数，分别为n和m以下m行，每行3个数，表示边连接... 查看详情
[hnoi2009]最小圈(代码片段)
https://zybuluo.com/ysner/note/1144886题面给一有向图，询问圈的最小平均值。解析先二分圈的平均值的最小值，记当前答案为\(mid\)。这时候，把所有的边权都减掉\(mid\)。这样判断原图中是否包含有平均值小于等于\(mid\)的圈，就转化成... 查看详情
洛谷p3199[hnoi2009]最小圈
题目描述对于一张有向图，要你求图中最小圈的平均值最小是多少，即若一个圈经过k个节点，那么一个圈的平均值为圈上k条边权的和除以k，现要求其中的最小值。输入输出格式输入格式：第一行2个正整数，分别为n和m以下m行... 查看详情
bzoj1488[hnoi2009]图的同构
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=14881488:[HNOI2009]图的同构TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 591 Solved: 388[Submit][Status][Discuss] 查看详情
bzoj1483:[hnoi2009]梦幻布丁
1483:[HNOI2009]梦幻布丁TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 3481 Solved: 1374[Submit][Status][Discuss]DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前 查看详情
bzoj1483[hnoi2009]梦幻布丁
1483:[HNOI2009]梦幻布丁TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 3485 Solved: 1376[Submit][Status][Discuss]DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前 查看详情
bzoj1483:[hnoi2009]梦幻布丁
每次只要修改链头实际代表的颜色即可//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include&l 查看详情
bzoj1483:[hnoi2009]梦幻布丁
...每次把小的合并到大的部分，均摊复杂度$O(MlogN)$。 //BZOJ1483//byCydiater//2016.10.25#include<iostream>#include<cstring>#include<cstdlib> 查看详情