题目大意
有向图中点有点权, 边有边权, 每个点的点权只能只能取一次, 可以任意选择起点, 求一个点权和除以边权和最大的回路。
解题报告
样例!
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);
}
Join the discussion