最优高铁环
C++ 代码
/*
本题求的是图中的环的平均值的最大值。可以发现这其实就是一个01分数规划
因此二分答案 mid,对于当前平均值 mid,我们让所有边都减去一个 mid,那么这是原图中平均值 >= mid 的环
就等价于新图中平均值 >= 0 的环,即正环。因此在新图中求一边正环即可,如果存在正环,那么平均值还可以放大,
二分右区间,否则缩小平均值,二分左区间。
*/
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 100010, M = 50010;
int n, m;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], cnt[N]; //队列、每个节点被更新的次数
double d[N]; //记录每个节点到起点的距离
bool st[N]; //记录每个节点是否在队列中
unordered_map<string, int> ids; //离散化
void add(int a, int b, int c) //添加边
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int get(string name) //查询当前字符串对应的编号
{
if(!ids.count(name)) ids[name] = ++n;
return ids[name];
}
int get_w(char c) //查询当前字符串的列车对应的速度
{
if(c == 'S') return 1000;
if(c == 'G') return 500;
if(c == 'D') return 300;
if(c == 'T') return 200;
if(c == 'K') return 150;
return 0;
}
bool check(double mid) //spfa判断正环
{
int hh = 0, tt = 1;
q[0] = 1;
memset(d, 0xcf, sizeof d);
d[1] = 0;
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
int count = 0;
while(hh != tt)
{
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
double weight = w[i] - mid;
if(d[j] < d[t] + weight)
{
d[j] = d[t] + weight;
cnt[j] = cnt[t] + 1;
//最后一个数据被卡,用一个小tips过,循环次数过多默认有环
if(++count > 100000) return true;
if(cnt[j] >= n) return true;
if(!st[j])
{
st[j] = true;
q[tt++] = j;
if(tt == N) tt = 0;
}
}
}
}
return false;
}
int main()
{
scanf("%d", &m);
memset(h, -1, sizeof h); //初始化邻接表
string line;
getchar();
int maxv = 0;
while(m--)
{
getline(cin, line);
string name = "";
int a = -1;
int c = 0;
for(int i = 0; i < line.size(); i++)
{
if(line[i] == '-')
{
if(a == -1) a = get(name);
name = "";
}
else name += line[i];
c += get_w(line[i]);
}
int b = get(name);
add(a, b, c); //添加边
maxv = max(maxv, c); //记录平均值的最大值
}
double l = 0, r = maxv; //浮点数二分
while(r - l > 1e-2)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
if(l == 0) l = -1; //如果最大平均值为0,说明不存在环
printf("%.0lf\n", l);
return 0;
}
%%%