小 K 的農(nóng)場

題目描述

小 K 在 MC 里面建立很多很多的農(nóng)場，總共 $n$ 個，以至于他自己都忘記了每個農(nóng)場中種植作物的具體數(shù)量了，他只記得一些含糊的信息（共 $m$ 個），以下列三種形式描述：

• 農(nóng)場 $a$ 比農(nóng)場 $b$ 至少多種植了 $c$ 個單位的作物；
• 農(nóng)場 $a$ 比農(nóng)場 $b$ 至多多種植了 $c$ 個單位的作物；
• 農(nóng)場 $a$ 與農(nóng)場 $b$ 種植的作物數(shù)一樣多。

但是，由于小 K 的記憶有些偏差，所以他想要知道存不存在一種情況，使得農(nóng)場的種植作物數(shù)量與他記憶中的所有信息吻合。

輸入格式

第一行包括兩個整數(shù) $n$ 和 $m$，分別表示農(nóng)場數(shù)目和小 K 記憶中的信息數(shù)目。

接下來 $m$ 行：

• 如果每行的第一個數(shù)是 $1$，接下來有三個整數(shù) $a,b,c$，表示農(nóng)場 $a$ 比農(nóng)場 $b$ 至少多種植了 $c$ 個單位的作物；
• 如果每行的第一個數(shù)是 $2$，接下來有三個整數(shù) $a,b,c$，表示農(nóng)場 $a$ 比農(nóng)場 $b$ 至多多種植了 $c$ 個單位的作物;
• 如果每行的第一個數(shù)是 $3$，接下來有兩個整數(shù) $a,b$，表示農(nóng)場 $a$ 種植的的數(shù)量和 $b$ 一樣多。

輸出格式

如果存在某種情況與小 K 的記憶吻合，輸出 Yes，否則輸出 No。

樣例 #1

樣例輸入 #1

3 3
3 1 2
1 1 3 1
2 2 3 2

樣例輸出 #1

Yes

提示

對于 $100\%$ 的數(shù)據(jù)，保證 $1\le n,m,a,b,c\le 5\times 10^3$。

分析

差分約束模型，把每個都分析一下：

1. 農(nóng)場 $a$ 比農(nóng)場 $b$ 至少多種植了 $c$ 個單位的作物：$x_a?c\ge x_b$,構(gòu)成（a,b,-c）
2. 農(nóng)場 $a$ 比農(nóng)場 $b$ 至多多種植了 $c$ 個單位的作物：$x_b+c\ge x_a$,構(gòu)成（b,a,c）
3. 農(nóng)場 $a$ 與農(nóng)場 $b$ 種植的作物數(shù)一樣多：$x_a=x_b\to x_a\ge x_b,x_b\ge x_a$，構(gòu)成（a,b,0）,(b,a,0)

代碼

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8+5,M=1e6;
vector<pair<int,int> > edges[M];
int dis[M];
int n,m,s;
int cnt[M];
bool inQueue[MAXN];
int q[MAXN],f=1,t=1;
void add(int u,int v,int w){edges[u].emplace_back(v,w);}
void read(){cin>>n>>m;for(int i=1,u,v,w,opt;i<=m;i++) {cin>>opt>>u>>v;if(opt<3) cin>>w;if(opt==1) add(u,v,-w);if(opt==2) add(v,u,w);if(opt==3) {add(u,v,0);add(v,u,0);} }
}
bool spfa(int s=0)
{memset(dis,0x3f,sizeof(dis));dis[s]=0;q[t++]=s;inQueue[s]=true;while(f<t){int x=q[f++];inQueue[x]=false;for(auto& edge:edges[x]){if(dis[edge.first]<=dis[x]+edge.second) continue;dis[edge.first]=dis[x]+edge.second;if(!inQueue[edge.first]){q[t++]=edge.first;inQueue[edge.first]=true;cnt[edge.first]++;if(cnt[edge.first]>=n+1) return false;}}}return true;
}
void solve(){for(int i=1;i<=n;i++) add(0,i,0);if(!spfa()) cout<<"No"; else cout<<"Yes";
}
int main()
{read();solve();return 0;
}

分析

1.超級源點

void solve(){for(int i=1;i<=n;i++) add(0,i,0);if(!spfa()) cout<<"No"; else cout<<"Yes";
}

差分約束需要超級源點，需要與每個點構(gòu)成一條邊，權(quán)值為0，因為spfa可以有效判斷負(fù)環(huán)，if(cnt[edge.first]>=n+1) return false;需要注意，此處為n+1，因為有超級源點

2.效率問題

STL庫中的queue效率低下，常數(shù)較高，在不開O2的前提下容易tle，推薦手打隊：

1. q.push(x)$\to$q[tail++]=x;
2. q.pop() $\to$ head++;
3. q.top() $\to$ q[head]