“那是一条神奇的天路诶~~把第一个神犇送上天堂” 怕不是某大佬早就A了这题，然鹅我又调了很久很久。。。
好吧就是0/1分数规划，但是跑的dfs的spfa（好像题解说bfs过不了？？？？不知） 发现把spfa写成bool的很难调。。。于是重构了一遍代码。。。
#include<cstdio> #include<iostream> #include<cstring> #define R register int using namespace std; const int M=20010,N=7010; const int eps=1E-2; inline int g() { R ret=0; register char ch; while(!isdigit(ch=getchar())) ; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret; } int n,m,cnt; int vr[M],nxt[M],c[M],p[M],fir[N]; double d[N],md; bool vis[N],flg; inline void add(int u,int v,int cc,int pp) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,c[cnt]=cc,p[cnt]=pp;} inline void spafa(int u) { vis[u]=true; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i]; register double w=md*p[i]-c[i]; if(d[v]>d[u]+w) { d[v]=d[u]+w; if(vis[v]) {flg=true; return ;} else spafa(v); } } vis[u]=false; } signed main() { n=g(),m=g(); for(R i=1,u,v,c,p;i<=m;++i) u=g(),v=g(),c=g(),p=g(),add(u,v,c,p); register double l=0,r=200; while(l+eps<r) { flg=false; memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); md=(l+r)/2; for(R i=1;i<=n;++i) if(!flg) spafa(i); else break; if(flg) l=md+0.01; else r=md-0.01; } if(l) printf("%.1lf ",l); else printf("-1 "); }
2019.04.20 ...已经快5月了。。。