sgu 236 Greedy Path

本文从WordPress迁移而来, 查看全部WordPress迁移文章

分数规划 spfa判负环

题意:给出一个有向图,每条边有一个权值和时间花费。如果图中无环,输出0,如果有环,找出一个最大的环,最大的意思是环上的权和 / 时间和 最大。

典型的分数规划问题,转化为图论模型解决

设 tot(cost) / tot(time) > k -> tot(time)*k - tot(cost) < 0

也就是 t1 k-c1 + t2 k - c2 + t3 k - c3 ……. tm k - cm < 0

可以设每条边的权为 ti * k - ci,然后在图中找是否存在负环

如果存在负环,那么就是原式 tot(time)*k - tot(cost) < 0 成立,找到了一个解,那么就可以试着把k调大,因为我们要tot(cost) / tot(time) 最大,这样就是一个二分答案的过程

spfa_dfs版本一直wa,只好写了个bfs版本的

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define cl memset
#define pb push_back
const int N = 60;
const double esp = 1e-8;
const double inf = 1e10;

int n,num[N],pre[N];
double d[N];
struct edge{
int v,c,t;
edge(int x,int y,int z){
v = x; c = y; t = z;
}
};
vector<edge>e[N];
vector<int>path;
queue<int>que;
bool vis[N];

int spfa_bfs(double p){
que.push(1); vis[1] = true;
while(!que.empty()){
int u = que.front();
que.pop(); vis[u] = false;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i].v;
double w = e[u][i].t * p - e[u][i].c;
if(d[u] + w < d[v]){
pre[v] = u;
d[v] = d[u] + w;
if(!vis[v]){
que.push(v); vis[v] = true; num[v]++;
if(num[v] == n) return v;
}
}
}
}
return 0;
}

int check(double p){
while(!que.empty()) que.pop();
cl(vis,false,sizeof(vis));
cl(num,0,sizeof(num));
cl(pre,-1,sizeof(pre));
for(int i = 1; i <= n ; i++)
d[i] = (i == 1 ? 0 : inf);
return spfa_bfs(p);
}

void find_path(int point){
int res,start;
cl(vis,false,sizeof(vis));
while(true){
vis[point] = true;
point = pre[point];
if(vis[point]) break;
}
start = point; res = 0; path.clear();
while(true){
res++;
path.pb(point);
point = pre[point];
if(point == start) break;
}
printf("%d\n",res);
for(int i = path.size() - 1; i >= 0; i--)
printf("%d ",path[i]);
puts("");
}

void binary(){
double low = esp , high = inf , mid;
while(low + esp < high){
mid = (low + high) / 2.0;
int res = check(mid);
if(res != 0) low = mid;
else high = mid;
}
int point = check(low);
if(point == 0){ //无环
puts("0"); return ;
}
find_path(point); //寻找路径并输出
}

int main(){
int m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 0; i <= n; i++)
e[i].clear();
while(m--){
int u,v,c,t;
scanf("%d%d%d%d",&u,&v,&c,&t);
e[u].pb(edge(v,c,t));
}
binary(); //二分答案
}
return 0;
}