最短路练习

T1 Sightseeing Cows G

我们先考虑如何求平均乐趣值。

1.总乐趣为 \(\sum^n_{i = 1}f_i \times s_i\)，其中 \(f_i\) 为第 \(i\) 个点的乐趣值，\(s_i\) 表示选不选。

2.路径是个环，总长度为 \(\sum^n_{i = 1}e_i \times s_i\) 其中 \(e_i\) 为从点 \(i\) 出发所走的边。

所以最大平均乐趣值就是 \(\max \dfrac{\sum^n_{i = 1}f_i \times s_i}{\sum^n_{i = 1}e_i \times s_i}\)。

于是就是 \(0/1\) 分数规划了。当然我们在处理时需要把整个式子 \(\times -1\)，因为 SPFA 在处理负环时无法计算出一条大于 \(0\) 的路径。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10,maxm = 5e4 + 5;
struct edge
{
	int to,nxt;
	double w;
}e[maxm << 1];
int head[maxm],tot;
void add_edge(int u,int v,double w)
{
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].to = v;
	e[tot].w = w;
}
double dis[maxn];
int f[maxn],u[maxm],v[maxm],w[maxm];
int num[maxn];
int n,m;
void init()
{
	memset(head,0,sizeof(head));
	tot = 0;
}
bool vis[maxn];
bool spfa(int s)
{
	queue<int> q;
	for(int i = 1;i <= n;i++)
	{
		q.push(i);
		dis[i] = 0;
		vis[i] = num[i] = 1;
	}
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = head[u];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].w)
			{
				dis[v] = dis[u] + e[i].w;
				if(!vis[v])
				{
					q.push(v);
					vis[v] = 1;
					if(++num[v] >= n)
					{
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
bool check(double x)
{
	init();
	for(int i = 1;i <= m;i++)
	{
		add_edge(u[i],v[i],x * w[i] - f[u[i]]);
	}
	return spfa(1);
}
int main()
{
	cin >> n >> m;
	double l = 0,r = 0;
	for(int i = 1;i <= n;i++)
	{
		cin >> f[i];
		r += f[i];
	}
	for(int i = 1;i <= m;i++)
	{
		cin >> u[i] >> v[i] >> w[i];
	}
	while(r - l > 1e-5)
	{
		double mid = l + (r - l) / 2;
		if(check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	printf("%.2lf",l);
	return 0;
}