\(\text{Problem}\)

对于一张有向图，要你求图中最小圈的平均值最小是多少，即若一个圈经过 \(k\) 个节点，那么一个圈的平均值为圈上 \(k\) 条边权的和除以 \(k\)，现要求其中的最小值

\(\text{Solution}\)

经典的分数规划题

很容易想到二分答案

那么我们要找到一个 \(T\) 个点的环满足

\(\frac{\sum_{i=1}^T e_i}{T} \le mid\)

把 \(T\) 乘过来，移项得

\(\sum_{i=1}^T [e_i-mid] \le 0\)

于是 \(dfs\) 暴力寻找这样的环

这种 \(dfs\) 相当于 \(dfs\) 版本的 \(spfa\)，不会超时

注意这份代码是 \(\text{JZOJ 5173}\) 的

题目是一样的，输出的区别罢了

\(\text{Code}\)

#include<cstdio>

using namespace std;

const int N = 1005, M = 10005;

int n, m, vis[N], h[N];

double dis[N], mid;

struct edge{

	int to, nxt, w;

}e[M];

inline void add(int u, int v, int w)

{

	static int tot = 0;

	e[++tot] = edge{v, h[u], w}, h[u] = tot;

}

int dfs(int x)

{

	vis[x] = 1;

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		double w = 1.0 * e[i].w - mid;

		if (dis[x] + w <= dis[v])

		{

			dis[v] = dis[x] + w;

			if (vis[v] || dfs(v)) return 1;

		}

	}

	vis[x] = 0;

	return 0;

}

inline int check()

{

	for(register int i = 1; i <= n; i++) vis[i] = 0, dis[i] = 0;

	for(register int i = 1; i <= n; i++) if (dfs(i)) return 1;

	return 0;

}

int main()

{

	scanf("%d%d", &n, &m);

	for(register int i = 1, u, v, w; i <= m; i++)

		scanf("%d%d%d", &u, &v, &w), add(u, v, w);

	double l = 0, r = 1e7, ans, bz = 0;

	while (r - l > 1e-12)

	{

		mid = (l + r) / 2;

		if (check()) r = mid, ans = mid, bz = 1;

		else l = mid;

	}

	if (bz) printf("%.2lf", l);

	else printf("PaPaFish is laying egg!");

}

巴特西

HNOI2019 最小圈

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章