二分答案m, 然后全部边权减掉m, 假如存在负圈, 那么说明有平均值更小的圈存在. 负圈用dfs判断.
---------------------------------------------------------------------------
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define clr(x, c) memset(x, c, sizeof(x))
#define foreach(i, x) for(__typeof(x.begin()) i = x.begin(); i != x.end(); i++)
using namespace std;
const int maxn = 3009;
const double eps = 1e-9;
struct edge {
int to;
double dist, w;
};
vector<edge> G[maxn];
int n;
double d[maxn];
bool vis[maxn], F;
void dfs(int x) {
vis[x] = true;
foreach(e, G[x]) if(d[e->to] > d[x] + e->w) {
if(!vis[e->to]) {
d[e->to] = d[x] + e->w;
dfs(e->to);
} else
F = true;
if(F) break;
}
vis[x] = false;
}
bool check(double m) {
rep(i, n) {
foreach(it, G[i]) it->w = it->dist - m;
vis[i] = false, d[i] = 0;
}
F = false;
rep(i, n) {
dfs(i);
if(F) return true;
}
return false;
}
int main() {
freopen("test.in", "r", stdin);
int m;
cin >> n >> m;
rep(i, n) G[i].clear();
while(m--) {
int u, v;
double d;
scanf("%d%d%lf", &u, &v, &d); u--, v--;
G[u].push_back( (edge) {v, d, 0} );
}
double L = -1e7, R = 1e7;
while(R - L > eps) {
double m = (L + R) / 2;
check(m) ? R = m : L = m;
}
printf("%.8lf
", L);
return 0;
}
---------------------------------------------------------------------------
1486: [HNOI2009]最小圈
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1447 Solved: 679
[Submit][Status][Discuss]
Description
