P3199 [HNOI2009]最小圈 01分数规划

题目描述

考虑带权的有向图G=(V,E)G=(V,E)G=(V,E)以及w:E→Rw:E\rightarrow Rw:E→R,每条边e=(i,j)(i≠j,i∈V,j∈V)e=(i,j)(i\neq j,i\in V,j\in V)e=(i,j)(i≠j,i∈V,j∈V)的权值定义为wi,jw_{i,j}wi,j?，令n=∣V∣n=|V|n=∣V∣。c=(c1,c2,?,ck)(ci∈V)c=(c_1,c_2,\cdots,c_k)(c_i\in V)c=(c1?,c2?,?,ck?)(ci?∈V)是GGG中的一个圈当且仅当(ci,ci+1)(1≤i<k)(c_i,c_{i+1})(1\le i<k)(ci?,ci+1?)(1≤i<k)和(ck,c1)(c_k,c_1)(ck?,c1?)都在EEE中，这时称kkk为圈ccc的长度同时令ck+1=c1c_{k+1}=c_1ck+1?=c1?，并定义圈c=(c1,c2,?,ck)c=(c_1,c_2,\cdots,c_k)c=(c1?,c2?,?,ck?)的平均值为μ(c)=∑i=1kwci,ci+1/k\mu(c)=\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}/kμ(c)=i=1∑k?wci?,ci+1??/k，即ccc上所有边的权值的平均值。令μ′(c)=Min(μ(c))\mu‘(c)=Min(\mu(c))μ′(c)=Min(μ(c))为GGG中所有圈ccc的平均值的最小值。现在的目标是：在给定了一个图G=(V,E)G=(V,E)G=(V,E)以及w:E→Rw:E\rightarrow Rw:E→R之后，请求出GGG中所有圈ccc的平均值的最小值μ′(c)=Min(μ(c))\mu‘(c)=Min(\mu(c))μ′(c)=Min(μ(c))
输入输出格式
输入格式：

第一行2个正整数，分别为nnn和mmm，并用一个空格隔开，只用n=∣V∣,m=∣E∣n=|V|,m=|E|n=∣V∣,m=∣E∣分别表示图中有nnn个点mmm条边。 接下来m行，每行3个数i,j,wi,ji,j,w_{i,j}i,j,wi,j?，表示有一条边(i,j)(i,j)(i,j)且该边的权值为wi,jw_{i,j}wi,j?。输入数据保证图G=(V,E)G=(V,E)G=(V,E)连通，存在圈且有一个点能到达其他所有点。

输出格式：

请输出一个实数μ′(c)=Min(μ(c))\mu‘(c)=Min(\mu(c))μ′(c)=Min(μ(c))，要求输出到小数点后8位。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(register int i = a;i <= n;++i)
#define lv(i,a,n) for(register int i = a;i >= n;--i)
#define clean(a) memset(a,0,sizeof(a))
const int INF = 1 << 30;
const double eps = 1e-10;
typedef long long ll;
typedef double db;
template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < ‘0‘ || c > ‘9‘)
        if(c == ‘-‘) op = 1;
    x = c - ‘0‘;
    while(c = getchar(), c >= ‘0‘ && c <= ‘9‘)
        x = x * 10 + c - ‘0‘;
    if(op) x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0) putchar(‘-‘), x = -x;
    if(x >= 10) write(x / 10);
    putchar(‘0‘ + x % 10);
}
const int N = 1e5 + 5;
struct node
{
    int l,r,nxt;
    db w;
}a[N];
int lst[N],len = 0;
int n,m,judge = 0;
void add(int x,int y,db w)
{
    a[++len].l = x;
    a[len].r = y;
    a[len].w = w;
    a[len].nxt = lst[x];
    lst[x] = len;
}
int vis[N];
db d[N];
void check(int now,db x)
{
    vis[now] = 1;
    for(int k = lst[now];k;k = a[k].nxt)
    {
        int y = a[k].r;
        if(d[y] > d[now] + a[k].w - x)
        {
            if(vis[y] || judge)
            {
                judge = 1;
                break;
            }
            d[y] = d[now] + a[k].w - x;
            check(y,x);
        }
    }
    vis[now] = 0;
}
int main()
{
    read(n);read(m);
    duke(i,1,m)
    {
        int x,y;
        db dis;
        read(x);read(y);
        scanf("%lf",&dis);
        add(x,y,dis);
    }
    db l = -1e6,r = 1e6;
    while(r - l > eps)
    {
        db mid = (l + r) / 2;
        clean(vis);
        clean(d); judge = 0;
        duke(i,1,n)
        {
            check(i,mid);
            if(judge)
            {
                break;
            }
        }
        if(judge) r = mid;
        else l = mid;
    }
    printf("%.8lf\n",l);
    return 0;
}