题解: 差分约束 模板题
差分约束系统 联系 最短路
对于操作1:$ a-bgeqslant c ightarrow bleqslant a-c $ 也就是说a向b连一条-c的边
对于操作2:$ a-bleq c $ 也就是b向a连一条c的边
对于操作三:$ a-bleq 0 $ 和 $ b-aleq 0 $ 也就是a向b连一条0的边 b向a连一条0的边
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
const int inf=1e9+7;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
queue<int>que;
bool vis[MAXN];
int du[MAXN];
bool vi[MAXN];
int dis[MAXN],n;
vector<int>vec;
bool spfa(int t){
vec.pb(t);
que.push(t);vis[t]=1;du[t]++;dis[t]=0;
while(!que.empty()){
int t1=que.front();que.pop();vis[t1]=0;
link(t1){
vi[j->t]=1;
vec.pb(j->t);
if(dis[j->t]>dis[t1]+j->v){
dis[j->t]=dis[t1]+j->v;
if(!vis[j->t]){
vis[j->t]=1;du[j->t]++;que.push(j->t);
if(du[j->t]>n)return 0;
}
}
}
}
return 1;
}
int main(){
n=read();int m=read();
int op,x,y,z;
while(m--){
int op=read();x=read();y=read();
if(op==1)z=read(),add(x,y,-z);
else if(op==2)z=read(),add(y,x,z);
else add(x,y,0),add(y,z,0);
}
inc(i,1,n)dis[i]=inf;
inc(i,1,n){
if(vi[i])continue;
bool flag=spfa(i);
for(int j=0;j<vec.size();j++)vis[vec[j]]=du[vec[j]]=0,dis[vec[j]]=inf;
vec.clear();
if(!flag){printf("No
");return 0;}
}
printf("Yes
");
}
3436: 小K的农场
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2144 Solved: 1011
[Submit][Status][Discuss]
Description
背景
小K是个特么喜欢玩MC的孩纸。。。
描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得
一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多
多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存
不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
Input
第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息的数目接下来m行：如果每行的第一个数是1，接
下来有三个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物如果每行第一个数是2，接下来有三个整数a
，b，c，表示农场a比农场b至多多种植了c个单位的作物如果每行第一个数是3，接下来有两个整数a,b，表示农场a
种植的数量与b一样。1<=n,m,a,b,c<=10000
Output
如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”
Sample Input
3 3
3 1 2
1 1 3 1
2 2 3 2
3 1 2
1 1 3 1
2 2 3 2
Sample Output
Yes
样例解释
三个农场种植的数量可以为（2,2,1）
样例解释
三个农场种植的数量可以为（2,2,1）