本文共 1049 字，大约阅读时间需要 3 分钟。
差分约束，关键在于找不等式，然后建图
这个题 spfa 判断负环时，如果以更新次数大于等于N判断有负环，会超时
只要判断更新次数大于sqrt(N)就可以，原理不知道
代码：
#include #include #include #include #include #include #include #include #include #include #include #include //#define ull unsigned long longusing namespace std;const int INF=0x3f3f3f3f;const int MOD=1000000007;const double eps=1e-6;const int N=10005;const int M=1000005;int head[N],I;struct node{ int j,next; double d;}edge[M];double dist[N];queue qt;bool had[N];int in[N];void add(int i,int j,double d){ edge[I].j=j; edge[I].d=d; edge[I].next=head[i]; head[i]=I++;}bool spfa(int n){ while(!qt.empty()) qt.pop(); for(int i=0;i dist[x]+edge[t].d) { dist[j]=dist[x]+edge[t].d; if(!had[j]) { had[j]=true; ++in[j]; qt.push(j); if(in[j]>sqrt(1.0*n)) return false; } } } } return true;}void init(int n,int m,double L,double U){ memset(head,-1,sizeof(head));I=0; for(int i=0;i
转载于:https://www.cnblogs.com/liulangye/archive/2013/05/22/3093220.html