P1993 小 K 的农场

小 K 的农场

题目描述

小 K 在 MC 里面建立很多很多的农场，总共 $n$ 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 $m$ 个），以下列三种形式描述：

• 农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
• 农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物；
• 农场 $a$ 与农场 $b$ 种植的作物数一样多。

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 $n$ 和 $m$，分别表示农场数目和小 K 记忆中的信息数目。

接下来 $m$ 行：

• 如果每行的第一个数是 $1$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；
• 如果每行的第一个数是 $2$，接下来有三个整数 $a,b,c$，表示农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物;
• 如果每行的第一个数是 $3$，接下来有两个整数 $a,b$，表示农场 $a$ 种植的的数量和 $b$ 一样多。

输出格式

如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。

样例 #1

样例输入 #1

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

样例输出 #1

Yes

提示

对于 $100\%$ 的数据，保证 $1\le n,m,a,b,c\le 5\times 10^3$。

分析

差分约束模型，把每个都分析一下：

1. 农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物：$x_a-c\ge x_b$,构成（a,b,-c）
2. 农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物：$x_b+c\ge x_a$,构成（b,a,c）
3. 农场 $a$ 与农场 $b$ 种植的作物数一样多：$x_a=x_b\to x_a\ge x_b,x_b\ge x_a$，构成（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";
}

差分约束需要超级源点，需要与每个点构成一条边，权值为0，因为spfa可以有效判断负环，if(cnt[edge.first]>=n+1) return false;需要注意，此处为n+1，因为有超级源点

2.效率问题

STL库中的queue效率低下，常数较高，在不开O2的前提下容易tle，推荐手打队：

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