小 K 在 MC 里面建立很多很多的农场，总共 \(n\) 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 \(m\) 个），以下列三种形式描述：
但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
第一行包括两个整数 \(n\) 和 \(m\)，分别表示农场数目和小 K 记忆中的信息数目。
接下来 \(m\) 行：
如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。
对于 \(100%\) 的数据，保证 \(1 \le n,m,a,b,c \le 10000\)
差分约束
众所周知，差分约束可以解决形如\(x_i-x_j\leq y\)的方程组
具体咋做，看这里，然而现在并没有写
那么我们应该对这个题的三种情况做转化：
然后别忘了建虚拟节点就行，差分约束传统技能
然而这个题把普通spfa卡了，开O2才能过
但是spfa最多也就\(O(nm)\)，边就算最多也是\(2m+n\)，算起来是\(3\cdot 10^8\)，2s应该能过，所以就很费解，应该是常数过大
然后改成Bellman-Ford想卡常数，然而更慢了
看题解里是dfs-spfa，但这种方法似乎并不稳定，而且考试的时候也没人告诉你这题卡普通spfa还是dfs-spfa...
所以最后用了一种玄学优化方法
曾经见到过一种用spfa玄学优化的dij做法，在这，最后虽然没能严谨证明出来，但用它从来没炸过对拍是验证猜想的唯一方法
而且这种方法实测用时是普通dij的四分之一，想卡常的时候能用
然后上文说的这个spfa优化就是把松弛操作在只有目前这个点不在堆中才进行，这应该是为了统计松弛次数
那个dij是无论在不在堆中都松弛，然后只有不在堆中的点才入堆
总之都很玄学，都不会证明正确性
所以可以有代码了
60-70分的普通spfa，开O2能AC,4.2s左右
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<queue>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
int fir[10006],nex[40006],to[40006],w[40006],tot;
int cnt[10005],in[10005];
int dis[10005];
std::queue<int>q;
inline void add(int a,int b,int c){
to[++tot]=b;w[tot]=c;
nex[tot]=fir[a];fir[a]=tot;
}
inline int spfa(){
q.push(n+1);in[n+1]=1;
std::memset(dis,0x3f,sizeof dis);dis[n+1]=0;
while(!q.empty()){
reg int u=q.front();q.pop();in[u]=0;
for(reg int v,i=fir[u];i;i=nex[i]){
v=to[i];
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
if(!in[v]){
if(++cnt[v]==n) return 0;
in[v]=1;q.push(v);
}
}
}
}
return 1;
}
int main(){
n=read();m=read();
for(reg int a,b,c,i=1;i<=m;i++){
c=read();a=read();b=read();
if(c==1) c=read(),add(a,b,-c);
else if(c==2) c=read(),add(b,a,c);
else add(a,b,0),add(b,a,0);
}
for(reg int i=1;i<=n;i++) add(n+1,i,0);
std::puts(spfa()?"Yes":"No");
return 0;
}
经过玄学优化的spfa，用时2.4s，比上面的开O2快一倍
然而，那些dfs-spfa居然能不开O2，0ms，很是迷惑
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<utility>
#include<cstring>
#include<queue>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m;
int fir[10006],nex[40006],to[40006],w[40006],tot;
int cnt[10005],in[10005];
int dis[10005];
std::priority_queue<std::pair<int,int> >q;
inline int min(int a,int b){return a<b?a:b;}
inline void add(int a,int b,int c){
to[++tot]=b;w[tot]=c;
nex[tot]=fir[a];fir[a]=tot;
}
inline int spfa(){
std::memset(dis,0x3f,sizeof dis);dis[n+1]=0;
q.push(std::make_pair(0,n+1));in[n+1]=1;
while(!q.empty()){
reg int u=q.top().second;q.pop();in[u]=0;
for(reg int v,i=fir[u];i;i=nex[i]){
v=to[i];
if(dis[v]>dis[u]+w[i]&&!in[v]){
dis[v]=dis[u]+w[i];
if(++cnt[v]>n) return 0;
q.push(std::make_pair(-dis[v],v));in[v]=1;
}
}
}
return 1;
}
int main(){
n=read();m=read();
for(reg int a,b,c,i=1;i<=m;i++){
c=read();a=read();b=read();
if(c==1) c=read(),add(a,b,-c);
else if(c==2) c=read(),add(b,a,c);
else add(a,b,0),add(b,a,0);
}
for(reg int i=1;i<=n;i++) add(n+1,i,0);
std::puts(spfa()?"Yes":"No");
return 0;
}
原文：https://www.cnblogs.com/suxxsfe/p/12578100.html