[POJ 3621] Sighting Cows

01分数规划的基本裸题。

因为路线一定是个环，所以找个最优比率生成环即可

二分一个比值，check一下即可。

#include <queue>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=1005;

int l,p,a[1005],inq[1005],cnt[1005],head[1005],ecnt;

struct Edge{int to,nxt,val;}e[N<<3];

void add(int bg,int ed,int val){e[++ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;}

double dis[1005];

bool ck(double x){

	queue<int>q;

	for(int i=1;i<=l;i++) q.push(i),dis[i]=0,inq[i]=1,cnt[i]=1;

	while(!q.empty()){

		int u=q.front();q.pop();inq[u]=0;

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

			int v=e[i].to;double dist=e[i].val;

			if(dis[v]>(double)dis[u]+x*dist-(double)a[u]){

				dis[v]=dis[u]+x*dist-(double)a[u];

				if(!inq[v]) q.push(v),inq[v]=1,cnt[v]++;

				if(cnt[v]>=l)return 1;

			}

		}

	}return 0;

}

int main() {

	scanf("%d%d",&l,&p);

	for(int i=1;i<=l;i++) scanf("%d",&a[i]);

	for(int u,v,b,i=1;i<=p;i++)

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

	double l=0,r=10000000,mid;

	while(r-l>1e-4){

		mid=(l+r)/2;

		if(ck(mid)) l=mid;

		else r=mid;

	}

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

}

巴特西

[POJ 3621] Sighting Cows

最新文章

热门文章