bzoj1486[hnoi2009]最小圈

关键词：

bzoj1486[HNOI2009]最小圈

题意：

定义图中一个环的平均值为环上边权和除以（浮点除法）边数，求一个图中的最小环平均值，保留8位。n≤3000，m≤10000，有负权边。

题解：

这就是比较明显的01分数规划了，见bzoj1690。同时根据题解二分60次就行了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 3010
#define INF 0x3fffffff
using namespace std;

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();
    return f*x;
}
struct e{int t; double w; int n;}es[maxn*4]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,0,g[f]}; g[f]=ess;}
double w[maxn*4]; int n,m;
void rebuild(double x){inc(i,1,m)es[i].w=w[i]-x;}
bool ins[maxn],f; double d[maxn];
void dfs(int x){
    ins[x]=1;
    for(int i=g[x];i;i=es[i].n){
        if(f)return;
        if(d[es[i].t]>d[x]+es[i].w){
            if(ins[es[i].t]){f=1; return;} d[es[i].t]=d[x]+es[i].w; dfs(es[i].t);
        }
    }
    ins[x]=0;
}
bool spfa(){
    memset(ins,0,sizeof(ins)); memset(d,0,sizeof(d)); f=0;
    inc(i,1,n){dfs(i); if(f)return 0;} return 1;
}
int main(){
    n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); scanf("%lf",&w[i]); pe(x,y);}
    double l=-10000000,r=10000000; int t=60;
    while(t--){
        double mid=(l+r)/2; rebuild(mid); if(!spfa())r=mid;else l=mid;
    }
    printf("%.8lf",l); return 0;
}

20160922

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> 查看详情