题面太鬼畜就不粘了。
这题唯一正确的解法是虽然我看不懂。
当然为了AC这道题于是抛弃自己的灵魂写了dfs-spfa结果跑的飞快。
这样的题算是出锅了吧……
简单讲下做法，二分答案，对每条边减去这个答案搜负环，如果存在的话该答案合法，否则不合法。
#include#include #include #include #include #include using namespace std;typedef double dl;const dl INF=1e7;const dl eps=1e-9;const int N=3e3+5;const int M=1e4+5;struct node{ int to,nxt; dl w;}e[M];int cnt,head[N],n,m,sum[N];bool vis[N],ok;dl dis[N];queue q;inline void add(int u,int v,dl w){ e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}void spfa(int u){ vis[u]=1; for(int i=head[u];i&&!ok;i=e[i].nxt){ int v=e[i].to;dl w=e[i].w; if(dis[v]>=dis[u]+w){ dis[v]=dis[u]+w; if(vis[v]||ok){ok=1;return;} spfa(v); } } vis[u]=0;}bool pan(dl delta){ for(int i=1;i<=m;i++)e[i].w-=delta; for(int i=1;i<=n;i++)vis[i]=0,dis[i]=0; ok=0; for(int i=1;i<=n&&!ok;i++) spfa(i); for(int i=1;i<=m;i++)e[i].w+=delta; return ok;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v;dl w; scanf("%d%d%lf",&u,&v,&w); add(u,v,w); } dl l=-INF,r=INF; while(fabs(r-l)>eps){ dl mid=(l+r)/2; if(pan(mid))r=mid; else l=mid; } printf("%.8lf\n",l); return 0;}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客： +
+++++++++++++++++++++++++++++++++++++++++++