POJ 3621 Sightseeing Cows
图论,最优比率环路,01规划
传送门:POJ
题意
一群奶牛(奶牛。。。)要出去玩,一张无向图,每个点有欢乐值,每条边有路程。求一个旅行路线(环,从哪出发回到哪),每个地方可以走多次,但欢乐值只计算一次。使得总欢乐值/总路程 值最大。
思路
-
首先是01规划问题。01规划大概就是,给定两个数组,a[i]表示选取i的收益,b[i]表示选取i的代价。如果选取i,定义x[i]=1否则x[i]=0。每一个物品只有选或者不选两种方案,求一个选择方案使得
R=∑a[i]∗x[i]b[i]∗x[i]
取得最值,即所有选择物品的总收益/总代价的值最大或是最小。最优比率环就是01规划的一种
传送门:Hhaile的专栏:01规划问题
-
设所求最值为ans,
即对于所有的环都有
∑i=1nv[i]e[i]<=res
变形得 ∑i=1nv[i]<=res∗∑i=1ne[i]
再得 ∑i=1n(res∗e[i]−v[i])>=0
临界条件是上式取等,res有最大值。即:随着k值变化, ∑ni=1(k∗e[i]−v[i]) 值单调。该式另一个意思是是否存在负环,如果恒正,那么不存在负环;若可以取到负值,那么至少存在一个负环。所以二分答案,用spfa判断负环,使上式恰好取0的k值就是我们要的res。
- 判断负环的方法:定义一个数组,表示出队次数。每次一个点出队更新别的点时,次数++。如果出队次数大于总点数,那么就存在负环。如果最后队列空了,就是求出了最短路,那么就不存在负环。
代码
有一点值得注意一下,我二分时左端点取0,右端点非常迷。最开始10007能过,变成1000倍1000000倍都过了,但是10,100,10000,100000倍就T了,不知道怎么回事
最后一列的代码长度,1599是对应右端点10007,1602是1000 0007,1607是1000 000 0007。为什么从1603直接到1606呢?因为数字后面加了ll。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAX_N=;
const int MAX_M=;
const double eps=;
const int oo=;
typedef long long LL;
struct Graph{
int next;
int to;
int cost;
}G[MAX_M];
int head[MAX_M];
int happy[MAX_N];
int vis[MAX_N];
double d[MAX_N];
bool inque[MAX_N];
bool spfa(int n,double ave)
{
for(int i=;i<=n;i++)
{
d[i]=(double) oo;
}
memset(vis,,sizeof(vis));
memset(inque,,sizeof(inque));
queue<int> que;
while(!que.empty()) que.pop();
d[]=;que.push();inque[]=true;
while(!que.empty())
{
int cur=que.front();que.pop();
inque[cur]=false;
vis[cur]++;
if(vis[cur]>=n) return true;
for(int i=head[cur];~i;i=G[i].next)
{
int to=G[i].to;
if(d[to]>d[cur]+(double) G[i].cost*ave-(double) happy[cur])
{
d[to]=d[cur]+(double) G[i].cost*ave-(double) happy[cur];
if(!inque[to])
{
que.push(to);
inque[to]=true;
}
}
}
}
return false;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==)
{
memset(head,-,sizeof(head));
memset(G,,sizeof(G));
memset(happy,,sizeof(happy));
for(int i=;i<=n;i++)
{
scanf("%d",&(happy[i]));
}
for(int i=;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
G[i].to=b;G[i].cost=c;G[i].next=head[a];head[a]=i;
}
double l=,r=;
while(r-l>eps)
{
double mid=(l+r)*();
if(spfa(n,mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
}
return ;
}