[POJ3621]Sightseeing Cows（01分?jǐn)?shù)規(guī)劃）

2019-11-08 19:44:01

字體：大中小

供稿：網(wǎng)友

題目描述

傳送門題意：一張圖，每一個(gè)點(diǎn)有價(jià)值，每一條邊有花費(fèi)，求一條起點(diǎn)終點(diǎn)相同的路徑，滿足價(jià)值/花費(fèi)最小。其中點(diǎn)重復(fù)經(jīng)過(guò)價(jià)值不變，邊重復(fù)經(jīng)過(guò)代價(jià)累加。

題解

一定不會(huì)重復(fù)走邊對(duì)吧…所以是一個(gè)最優(yōu)比率環(huán)問(wèn)題將邊的價(jià)值看成是起點(diǎn)或終點(diǎn)的價(jià)值，二分R之后，對(duì)每一條邊計(jì)算di=ai?R?bi $d_i=a_i-R*b_i$ 然后用spfa判斷是否有正權(quán)環(huán)就行了，如果有的話一定存在更優(yōu)解

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005#define E 5005const double eps=1e-6;int n,m,x,y;int tot,point[N],nxt[E],v[E];double c[E];double val[N],e[E],ans;double dis[N];int cnt[N];bool vis[N];int q[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}bool spfa(){ memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis));; memset(cnt,0,sizeof(cnt)); int head=0,tail=0; for (int i=1;i<=n;++i) { vis[i]=1;++cnt[i]; q[(++tail)%n]=i; } while (head!=tail) { int now=q[(++head)%n]; vis[now]=0; for (int i=point[now];i;i=nxt[i]) if (dis[v[i]]<dis[now]+c[i]) { dis[v[i]]=dis[now]+c[i]; if (!vis[v[i]]) { vis[v[i]]=1; ++cnt[v[i]]; if (cnt[v[i]]>n) return true; q[(++tail)%n]=v[i]; } } } return false;}bool check(double L){ for (int i=1;i<=tot;++i) c[i]=val[v[i]]-L*e[i]; return spfa();}double find(){ double l=0.0,r=1e4,mid,ans=0.0; while (r-l>eps) { mid=(l+r)/2.0; if (check(mid)) ans=l=mid; else r=mid; } return ans;}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%lf",&val[i]); for (int i=1;i<=m;++i) { scanf("%d%d%lf",&x,&y,&e[i]); add(x,y); } ans=find();