bzoj1690/poj3621[Usaco2007 Dec]奶牛的旅行

本文主要是介绍bzoj1690/poj3621[Usaco2007 Dec]奶牛的旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj poj

题目大意：

有N 个景点，参观第i 个景点会给奶牛带来Fi 点欢乐度。景点间有M 条道路，道路都是单行道，第i 条道路从Si 开始通向Ti，长度为Li。奶牛们可以选择从任意一个景点出发，在晚上结束的时候，奶牛必须回到这个起点和约翰汇合。

奶牛们想让欢乐度尽量大，但经讨厌走路，所以需要设计一条游览线路。定义一条游览线路的“欢乐指数”为该线路上所有景点的欢乐度之和与路程长度的比值。欢乐指数越大的线路越受奶牛的欢迎。在旅游的时候，奶牛们是乐意重复路过同一个景点的，但参观同一景点只记一次欢乐度。奶牛至少要参观两个景点，保证给定的道路系统里至少能找出一条环形线路，请帮助奶牛规划处一条欢乐指数最大的线路来吧。

题解：

0-1分数规划+Bellman-Ford

于是这是0-1分数规划中最优比率环问题啊。

于是需要知识储备qwq，并不熟(也不想打那么长东西)的我就跳过233。

我是get到关于0-1分数规划的链接

跳过之后就没有其他东西了尴尬qwq

二分答案，知道↑之后就可以推导出若sigma(xi*(mid*Li-F[a[i].x]))<=0(图中有负环了)，即找到的答案比假设的答案要优。

啊啊啊因为把推导过程打出来真的很费时间啊，不写了><

(如果再看这道题发现不会做的话，回想一下关大学霸的推导√

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1010
#define maxn 10100const int inf=0x7fffffff;
struct node
{int x,y,next;double c,d;
}a[maxn];int n,len,first[N],w[N];
double d[N];int cnt[N];bool v[N];
void ins(int x,int y,int c)
{a[++len].x=x;a[len].y=y;a[len].c=c;a[len].next=first[x];first[x]=len;
}
int head,tail,list[N];
bool BM()
{for (int i=2;i<=n;i++) d[i]=(double)inf,cnt[i]=v[i]=0;head=1;tail=2;list[1]=1;d[1]=0;cnt[1]=1;v[1]=1;while (head!=tail){int x=list[head];for (int k=first[x];k!=-1;k=a[k].next){int y=a[k].y;if (d[y]>a[k].d+d[x]){d[y]=a[k].d+d[x];if (!v[y]){list[tail++]=y;if (tail>n) tail=1;v[y]=true;cnt[y]++;}if (cnt[y]>n) return true;}}head++;v[x]=false;if (head>n) head=1;}return false;
}
int main()
{//freopen("sightsee.in","r",stdin); //freopen("sightsee.out","w",stdout);int m,i,x,y,c;double l,r,ret;scanf("%d%d",&n,&m);len=0;l=r=ret=0;memset(first,-1,sizeof(first));for (i=1;i<=n;i++) scanf("%d",&w[i]);for (i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);ins(x,y,c);r+=(double)c;}while (r-l>=0.0001){double mid=(l+r)/2.0;for (i=1;i<=m;i++)a[i].d=mid*a[i].c-(double)w[a[i].x];//这里的话同时取起点或者终点的话就好???if (BM()) {ret=mid;l=mid+0.0001;}else r=mid-0.0001;}printf("%.2lf\n",ret);return 0;
}

这篇关于bzoj1690/poj3621[Usaco2007 Dec]奶牛的旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---