Luogu P1768 天路 0/1分数规划+dfs spfa

“那是一条神奇的天路诶~~把第一个神犇送上天堂” 怕不是某大佬早就A了这题，然鹅我又调了很久很久。。。

---

好吧就是0/1分数规划，但是跑的dfs的spfa（好像题解说bfs过不了？？？？不知） 发现把spfa写成bool的很难调。。。于是重构了一遍代码。。。

#include<cstdio>

#include<iostream>

#include<cstring>

#define R register int

using namespace std;

const int M=,N=;

const int eps=1E-;

inline int g() {

    R ret=; register char ch; while(!isdigit(ch=getchar())) ;

    do ret=ret*+(ch^); 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=,u,v,c,p;i<=m;++i) u=g(),v=g(),c=g(),p=g(),add(u,v,c,p);

    register double l=,r=;

    while(l+eps<r) { flg=false; memset(d,,sizeof(d)); memset(vis,,sizeof(vis));

        md=(l+r)/; for(R i=;i<=n;++i) if(!flg) spafa(i); else break;

        if(flg) l=md+0.01; else r=md-0.01;

    } if(l) printf("%.1lf\n",l); else printf("-1\n");

}

---

2019.04.20 ...已经快5月了。。。