图论专题 F(差分约束)

关于差分约束的介绍可以直接看wikioi

链接在这里：差分约束 - OI Wiki (oi-wiki.org)

算法学习笔记(11): 差分约束 - 知乎 (zhihu.com)

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=1e5+5;
 5 int n,m,ans;
 6 int tot,head[MAX],adj[MAX<<1],nxt[MAX<<1],wei[MAX<<1],dis[MAX],cnt[MAX];
 7 queue <int> q;
 8 bool t[MAX];
 9 struct Edge{int u,v,w1,w2;bool operator <(const Edge &tt) const {return w1<tt.w1;}}edge[MAX];
10 inline int read(){
11     int an=0,x=1;char c=getchar();
12     while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
13     while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}
14     return an*x;
15 }
16 void addedge(int u,int v,int w){
17     tot++;
18     adj[tot]=v;wei[tot]=w;
19     nxt[tot]=head[u];
20     head[u]=tot;
21 }
22 bool spfa(){
23     int i,j,u,v;
24     for (i=1;i<=n;i++) cnt[i]=0;
25     while (!q.empty()){
26         u=q.front();q.pop();t[u]=false;
27         if (cnt[u]>n) return false;
28         for (i=head[u];i;i=nxt[i]){
29             v=adj[i];
30             if (dis[v]>dis[u]+wei[i]){
31                 dis[v]=dis[u]+wei[i];
32                 if (!t[v]){
33                     q.push(v),t[v]=true;
34                     cnt[v]++;
35                 }
36             }
37         }
38     }
39     return true;
40 }
41 int main(){
42     freopen ("f.in","r",stdin);
43     freopen ("f.out","w",stdout);
44     int i,j;
45     n=read();m=read();
46     for (i=1;i<=m;i++){
47         edge[i].u=read();
48         edge[i].v=read();
49         edge[i].w1=read();
50         addedge(edge[i].v,edge[i].u,edge[i].w1);
51     }
52     for (i=1;i<=n;i++) addedge(n+1,i,0);
53     memset(t,false,sizeof(t));
54     for (i=1;i<=n+1;i++) dis[i]=1e9;
55     q.push(n+1);t[n+1]=true;dis[n+1]=0;
56     if (spfa()) printf("YES");
57     else printf("NO");
58     return 0;
59 }