[POJ 3621] Sightseeing Cows 最大密度环

传送门·Teleport!

题目大意

有向图中点有点权, 边有边权, 每个点的点权只能只能取一次, 可以任意选择起点, 求一个点权和除以边权和最大的回路。

解题报告

样例!

Input:
5 8
6
22
10
17
9
1 2 3
2 3 11
3 4 5
3 5 9
4 5 5
5 1 5
5 2 2
4 2 7
Output:
2.52

既然学了01分数规划，那就写两个题解吧。。
首先设选择的边权为数列wi，点权为数列vi
那么题目要求最小化
$$ans = \frac {\sum {v_i}} {\sum {w_i}}$$
01分数的套路。。定义个浮点数g,如果下面A式的关系是可以满足的
$${\sum {v_i}} – g{\sum {w_i}} > 0$$
变形上面式子可以得到
$$ ans = \frac {\sum {v_i}} {\sum {w_i}} > g$$
那么我们就可以二分一下g，如果存在一种选择方法满足上面提到的A式，那么根据变形肯定存在一个比g更优的答案，否然不存在更优的答案。当区间宽度\<EPS时g就是答案啦！
那么新的问题来了，怎么确定是否有一种选择方案使得A式被满足呢?
首先发现最优的选取方案必然是一个简单环，(如果不是简单环，那么把路径中密度最大的一个简单环取出就可以成为新的更优答案。)，然后对于每条边把它的权值设为vi(点权值)-g*wi(边权值),把所有点全部塞到队列里跑最长路spfa，如果一个点进入队列超过N次那么必然存在一个正权环，说明这个环的答案比g更优，二分成功。否然失败。另外，SunIsMe使用了dfs找环，虽然感觉很玄学，但是确实跑得飞快。。
接下来贴上代码！

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>

const double EPS = 1e-4;

const int MAXN = 1010;
const int MAXM = 7000;
int N, M;
struct Node {
    int v, nxt;
    double w;
} d[MAXM];
int head[MAXN], etot;
int addEdge (int a, int b, double c) {
    etot ++;
    d[etot].v = b;
    d[etot].w = c;
    d[etot].nxt = head[a];
    head[a] = etot;
    return etot;
}
inline void clear () {
    memset (head, 0, sizeof head);
    etot = 0;
}

int fun[MAXN];
int inp[MAXM][3];
#include <queue>
std :: queue<int> que;
double dis[MAXN];
int cnts[MAXN];
bool vis[MAXN];

bool check (double mid) {
    clear();
    for(int i = 1; i<=M; i++)
        addEdge(inp[i][0], inp[i][1], fun[inp[i][1]]-mid*inp[i][2]);
    while(!que.empty()) que.pop();
     memset(cnts, 0, sizeof cnts); memset(vis, 1, sizeof vis);
    for(int i = 1; i<=N; i++)
        que.push(i), dis[i] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop(); vis[u] = false;
        cnts[u]++;
        if(cnts[u] >= N) return true;
        for(int e = head[u]; e; e = d[e].nxt)
            if(dis[d[e].v] < dis[u] + d[e].w) {
                dis[d[e].v] = dis[u] + d[e].w;
                if(!vis[d[e].v]) {
                    vis[d[e].v] = true;
                    que.push(d[e].v);
                }
            }
    }
    return false;
}

int main () {
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=N; i++)
        scanf("%d", &fun[i]);
    for(int i = 1; i<=M; i++)
        scanf("%d%d%d", &inp[i][0], &inp[i][1], &inp[i][2]);
    double l = 0, r = 2000;
    while(r-l > EPS) {
        double mid = (l+r)/2.0;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf\n", l);
}