LuoguP3199「HNOI2009」题解

发表于 更新于

经典的0/1分数规划模型

题目描述

题目描述

Inputs and Outputs examples

Inputs’ e.g. #1

1
2
3
4
5
6
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

Outputs’ e.g. #1

1
3.66666667

分析

其实这个东西在我做之前并不知道他其实是个0/1分数规划模型.

我们首先知道要求的是最小化环的平均权值.

显然这个东西是单调的,那么我们可以二分答案一下.

我们二分一下答案$mid$,然后我们把每一条边减去一下$mid$,然后用SPFA检查一下是否存在负环即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// luogu-judger-enable-o2
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 3e3 + 50;
const int MAXM = 2e4 + 10;
int n,m,a[MAXN];
struct Edge{
    int next,to;
    double dis;
}Graph[MAXM];
int head[MAXN],cnt;
int visited[MAXN],flag;
double dist[MAXN], l = -1e6, r = 1e6;
/* functions */
inline void Add_Edge(int from,int to,double dis){
    Graph[++cnt] = (Edge){head[from],to,dis};
    head[from] = cnt;
}
inline void check(int limit,double d){
    visited[limit] = true;
    for(int i=head[limit];i;i=Graph[i].next){
        if(dist[Graph[i].to] > dist[limit] + Graph[i].dis - d){
            if(visited[Graph[i].to] || flag) {flag = 1; break;}
            dist[Graph[i].to] = dist[limit]  + Graph[i].dis - d;
            check(Graph[i].to,d);
        }
    }
    visited[limit] = 0;
}
int main(int argc,char *argv[]){
    scanf("%d%d",&n,&m);
    FOR(i,1,m,1){
        int u,v; scanf("%d%d",&u,&v);
        double d; scanf("%lf",&d);
        Add_Edge(u,v,d);
    }
    while(r - l > 1e-10){
        double mid = (l + r)/2;
        memset(dist,0,sizeof(dist));
        memset(visited,false,sizeof(visited)); flag = 0;
        FOR(i,1,n,1){
            check(i,mid); if(flag) break;
        }
        if(flag) r = mid;
        else l = mid;
    }
    printf("%.8lf",l);
    return 0;
}

THE END