「BZOJ1486」[HNOI2009]最小圈

Description

考虑带权的有向图G=(V,E)G=(V,E)以及w:ERw:E\rightarrow R,每条边e=(i,j)(ij,iV,jV)e=(i,j)(i\neq j,i\in V,j\in V)的权值定义为wi,jw_{i,j},令n=Vn=|V|c=(c1,c2,,ck)(ciV)c=(c_1,c_2,\cdots,c_k)(c_i\in V)GG中的一个圈当且仅当(c_i,c_{i+1})(1\le i<k)(ck,c1)(c_k,c_1)都在EE中,这时称kk为圈cc的长度同时令ck+1=c1c_{k+1}=c_1,并定义圈c=(c1,c2,,ck)c=(c_1,c_2,\cdots,c_k)的平均值为μ(c)=i=1kwci,ci+1/k\mu(c)=\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}/k,即cc上所有边的权值的平均值。令μ(c)=Min(μ(c))\mu'(c)=Min(\mu(c))GG中所有圈cc的平均值的最小值。现在的目标是:在给定了一个图G=(V,E)G=(V,E)以及w:ERw:E\rightarrow R之后,请求出GG中所有圈cc的平均值的最小值μ(c)=Min(μ(c))\mu'(c)=Min(\mu(c))

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
`

Sample Output

1
3.66666667

HINT

对于100%的数据,n3000,m10000,wi,j107n\le 3000,m\le 10000,|w_{i,j}| \le 10^7

Solution

队列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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 3100, M = 21000;
int n, m;
struct Edge {
int u, v, nxt;
double w, s;
}e[M];
int head[N], en;
void addedge(int x, int y, double z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].s = z;
}
#define eps 1e-9
bool inq[N];
double d[N];
int cnt[N];
bool spfa() {
queue<int>q;
for(int i = 1; i <= n;++i) cnt[i] = inq[i] = 0, d[i] = 1e22;
d[1] = 0;
q.push(1);
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = 0;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(d[y] - (e[i].w + d[x]) > eps) {
d[y] = e[i].w + d[x];
if(!inq[y]) {
inq[y] = 1;
q.push(y);
if((++cnt[y]) > n - 1) {
return 0;
}
}
}
}
}
return 1;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
double z;
scanf("%lf", &z);
addedge(x, y, z);
}
double l = -1e7 + 7, r = 1e7 + 7;
while(r - l > eps) {
double mid = (l + r) / 2;
for(int i = 1; i <= en; ++i)
e[i].w = e[i].s - mid;
if(spfa()) l = mid;
else r = mid;
}
printf("%.8lf\n", l);
return 0;
}

dfs 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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 3100, M = 21000;
int n, m;
struct Edge {
int u, v, nxt;
double w, s;
}e[M];
int head[N], en;
void addedge(int x, int y, double z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].s = z;
}
#define eps 1e-9
bool vis[N];
double d[N];
bool spfa(int x) {
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(d[y] - (e[i].w + d[x]) > eps) {
d[y] = e[i].w + d[x];
if(vis[y] || !spfa(y)) return 0;
}
}
vis[x] = 0;
return 1;
}
bool check() {
for(int i = 1; i <= n; ++i) d[i] = vis[i] = 0;
for(int i = 1; i <= n; ++i) {
if(!spfa(i)) return 0;
}
return 1;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
double z;
scanf("%lf", &z);
addedge(x, y, z);
}
double l = -1e7 + 7, r = 1e7 + 7;
while(r - l > eps) {
double mid = (l + r) / 2;
for(int i = 1; i <= en; ++i)
e[i].w = e[i].s - mid;
if(check()) l = mid;
else r = mid;
}
printf("%.8lf\n", l);
return 0;
}

std

BZOJ卡内存
fi,jf_{i,j}表示从00好点到ii走了jj步的最小距离。
xjb转移一下就行了。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 3100, M = 21000;
int n, m;
struct Edge {
int u, v, nxt;
double w;
}e[M];
#define eps 1e-9
double f[N][N];
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) scanf("%d%d%lf",&e[i].u,&e[i].v,&e[i].w);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) f[i][j] = 1e99;
for(int i = 1; i <= n; ++i)
f[i][0] = 0;
for(int i = 0; i < n; ++i)
for(int j = 1; j <= m; ++j)
f[e[j].v][i + 1] = min(f[e[j].v][i + 1], f[e[j].u][i] + e[j].w);
double ans = 1e99;
for(int i = 1; i <= n; ++i){
double tmp = -1e99;
for(int j = 0; j < n; ++j){
tmp = max(tmp, (f[i][n] - f[i][j]) / (n - j));
}
ans = min(ans, tmp);
}

printf("%.8lf\n",ans);
return 0;
}