C++ 代码
差分约束问题,如果T了记得打快读QwQ
最主要的还是连边,记得注意一下,代码中连的边是为跑最短路服务的,仅供参考
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define maxn 550017
int to[maxn<<2],nxt[maxn<<2],head[maxn<<2];
int val[maxn],dis[maxn],tot[maxn];
int minn,maxx,cnt,n,m,k;
int vis[maxn],flag;
queue<int> q;
inline int read(){
char c=getchar();int x=0;int f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
void add(int u,int v,int w){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
val[cnt]=w;
}
void spfa(int u){
if(tot[u]>=n){
flag=1;
return;
}
vis[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]<dis[u]+val[i]){
dis[v]=dis[u]+val[i];
if(!vis[v]){
vis[v]=1;
spfa(v);
if(flag) return;
tot[v]++;
}
}
}
vis[u]=0;
}
signed main(){
n=read();k=read();
for(int i=1;i<=k;i++){
int x,a,b;
x=read();a=read();b=read();
if(x==1){add(a,b,0);add(b,a,0);}
if(x==2){
if(a==b) flag=1;
add(a,b,1);
}
if(x==3) add(b,a,0);
if(x==4){
if(a==b) flag=1;
add(b,a,1);
}
if(x==5) add(a,b,0);
}
for(int i=n;i>=1;i--){
add(0,i,1);
}
vis[0]=1;dis[0]=0;
spfa(0);
if(flag){printf("-1");return 0;}
int ans=0;
for(int i=1;i<=n;i++){
ans+=dis[i];
}
printf("%lld",ans);
return 0;
}
你好 现在已经tle了
这位甚至没有用栈优化就过了,还是140ms
u可以到v,v也可以到u,其中有一个边权为正就是正环,这里使用的不是spfa最长路算法就不能保证这个环中的其他边一定为正吧?(环上有边权为正那么就是正环这个解释是合理的但是是建立在spfa等算法遍历建图建边的情况下 而这里的tarjan建边是不考虑边权的)
我觉得SPFA能够过本题是因为这里的数据太水了,SPFA最坏时间复杂度
O(nm)
,本题N、M按照题目描述应为1e5
级。考虑在洛谷的糖果那道题,同样是1e5的数据,但是spfa也跑过了,看来他们都没有恶意卡spfa
$DFS$版的$SPFA$确实很难卡掉,基本上都是$O(m)$左右的