题意描述

Sightseeing Cows G

给定一张有向图，图中每个点都有点权 \(a_i\)，每条边都有边权 \(e_i\)。

求图中一个环，使 “环上个点权之和” 除以 “环上各边权之和” 最大。输出最大值。

解释一下，原题目中并没有点明这是一个环，但是从：

奶牛们不会愿意把同一个建筑物参观两遍。

可以看出，不管怎么走，走环一定是最优的，因为重复走相当于无故增加分母。

算法分析

据说这是一道 0/1 分数规划的题目，但是其实可以用更加通俗易懂的方法来解释。

假设用 \(v_i,e_i(1\leq i\leq k)\) 分别表示环上的点权和边权。

那么显然题目就是要找到最大的 \(\frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)。

利用二分答案，当 \(\sum^k_{i=1} (mid\times e_i-v_i)<0\) 时：\(mid<\frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)，令 \(l=mid\)。

反之，当 \(\sum^k_{i=1} (mid\times e_i-v_i)\geq 0\)：\(mid\geq \frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)，令 \(r=mid\)。

那么就将 \(e(x,y)\) 转化为 \(mid\times e_i-a[x]\)，利用 SPFA 判断是否有负环即可。

代码实现

应为题目不保证图的连通性，所以 SPFA 开始的时候将所有点都入队。

利用二分答案将最优解变为判定即可。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#define N 10010

#define M 50010

using namespace std;

int n,m,a[N],head[N],cnt=0,sum[N];

bool vis[N];

double dis[N];

struct Edge{

	int nxt,to,val;

}ed[N<<1];

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();

	return x*f;

}

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

	ed[++cnt].nxt=head[u];

	ed[cnt].to=v,ed[cnt].val=w;

	head[u]=cnt;

	return;

}

bool chck(double mid){

	queue<int>q;

	for(int i=1;i<=n;i++){

		q.push(i);

		dis[i]=0,vis[i]=true,sum[i]=1;

	}

	while(!q.empty()){

		int u=q.front();q.pop();

		vis[u]=false;

		if(++sum[u]>=n) return true;

		for(int i=head[u];i;i=ed[i].nxt){

			int v=ed[i].to;

			double w=ed[i].val;

			if(dis[v]>dis[u]+(double)(mid*w-(double)a[u])){//注意一下 double 与 int

				dis[v]=dis[u]+(double)(mid*w-(double)a[u]);

				if(!vis[v]) q.push(v),vis[v]=true;

			}

		}

	}

	return false;

}

int main(){

	n=read(),m=read();

	for(int i=1;i<=n;i++) a[i]=read();

	for(int i=1;i<=m;i++){

		int u=read(),v=read(),w=read();

		add(u,v,w);

	}

	double l=0.0,r=1000010.0,mid,eps=1e-5;

	while(r-l>eps){

		mid=(l+r)/2;

		if(chck(mid)) l=mid;

		else r=mid;

	}

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

	return 0;

}

完结撒花

巴特西

P2868 [USACO07DEC]Sightseeing Cows G

题意描述

算法分析

代码实现

最新文章

热门文章