題目連結
分析
可以發現,這是一道0/1分數規劃的題目,需要二分答案,然後判定是否存在負環,是以說bfs貌似不高效,那就用dfs吧,若二分答案為0,即不合法
代碼
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
struct node{int y,w,p,next;}e[30001];
int ls[7011],n,m; bool v[7011],flag; double dis[7011];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline bool dfs(int x,double mid){
v[x]=1;
for (rr int i=ls[x];i;i=e[i].next)
if (dis[e[i].y]>dis[x]+e[i].p*mid-e[i].w){
if (v[e[i].y]) return 0;
dis[e[i].y]=dis[x]+e[i].p*mid-e[i].w;
if (!dfs(e[i].y,mid)) return 0;
}
v[x]=0;
return 1;
}
signed main(){
n=iut(); m=iut();
for (rr int i=1;i<=m;++i){
rr int x=iut();
e[i]=(node){iut(),iut(),iut(),ls[x]}; ls[x]=i;
}
for (rr int i=1;i<=n;++i)
e[i+m]=(node){i,0,0,ls[n+1]},ls[n+1]=m+i;
rr double l=0,r=200;
while (l+1e-2<r){
rr double mid=(l+r)/2;
memset(dis,42,sizeof(dis));
memset(v,0,sizeof(v)); dis[n+1]=0;
if (dfs(n+1,mid)) r=mid; else l=mid;
}
if (!l) return !printf("-1");
else return !printf("%.1lf",l);
}