lg1993

发表于 | 阅读数 次

链接:lg1993

题解

  • 裸的差分约束，判环注意要用dfs判，spfa判环会TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=xi;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
const int inf=0x3f3f3f3f;
int head[N],nxt[N],to[N],w[N],vis[N],dis[N],cnt,n,m,ans;
inline void adde(int a,int b,int c){
	to[++cnt]=b;
	w[cnt]=c;
	nxt[cnt]=head[a];
	head[a]=cnt;
}
int spfa(int u){
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i])if(dis[to[i]]<dis[u]+w[i]){
		dis[to[i]]=dis[u]+w[i];
		if(vis[to[i]])return 0;
		if(!spfa(to[i]))return 0;
	}
	vis[u]=0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,m){
		int op,a,b,c;
		scanf("%d",&op);
		if(op!=3)scanf("%d%d%d",&a,&b,&c);
		else scanf("%d%d",&a,&b);
		if(op==1)adde(b,a,c);
		else if(op==2)adde(a,b,-c);
		else adde(a,b,0),adde(b,a,0);
	}
	rep(i,1,n)adde(0,i,0),dis[i]=-inf;
	puts(spfa(0)?"Yes":"No");
	return 0;
}