跑最长路
1 a-b>=c 建立b到a权值为c的路
2 a-b<=c-----> b-a>=-c 建立a到b权值为-c的路
3 a=b 建立a到b,b到a的双向权值为0的路
问满足以上所有条件的情况是否存在,则就是问是否存在负环。改写spfa为dfs.
indfs[ i ]表示 i 是否正在被dfs, book[ i ]表示 i 点是否访问过。如果一个点在dfs且再次回到路径小于上次就存在环。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
struct Edge{
int v,w,nxt;
};
int cnt,head[100000];
Edge edge[100000];
int book[10005],dis[10005],indfs[100005],n,m;
int read(){
int x=0,dign=1;
char c = getchar();
while(c<'0'||c>'9'){
if(c=='-')dign=-1;
c = getchar();
}
while(c>='0'&&c<='9'){
x = x*10 + c - '0';
c = getchar();
}
return x*dign;
}
void add(int u,int v,int w){
cnt++;
edge[cnt].v = v; edge[cnt].w = w;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
bool spfa(int u){
indfs[u] = 1;
for(int w,v,i=head[u];i;i=edge[i].nxt){
v = edge[i].v; w = dis[u] + edge[i].w;
if(!book[v]||dis[v]<w){
if(indfs[v])return false;//一个点通过一段路径回到这个点比之前更优存在环
book[v] = 1;
dis[v]=w;
if(!spfa(v))return false;
}
}
indfs[u] = 0;
return true;
}
int main()
{
n = read(); m = read();
for(int i=0;i<=n;i++)add(0,i,0);
for(int i=0;i<m;i++){
int t,a,b,c;
t = read();
if(t==3){
a = read(); b = read();
add(b,a,0);
add(a,b,0);
}else if(t==1){
a = read(); b = read(); c = read();
add(b,a,c);
}else{
a = read(); b = read(); c = read();
add(a,b,-c);
}
}
for(int i=1;i<=n;i++)dis[i] = -1;
dis[0] = 0; book[0] = 1;
if(!spfa(0))printf("No\n");
else printf("Yes\n");
return 0;
}