luogu P1993 小K的農場

analysis

就是判斷一組不等式是否有解

于是建立差分限制系統,有三個不等式(因為這個題沒有要求作物個數的正負,我們完全可以使其為負):

c a s e 1 : a i − b i > = c i case1:a_i-b_i>=c_i case1:ai​−bi​>=ci​

c a s e 2 : a i − b i &lt; = c i case2:a_i-b_i&lt;=c_i case2:ai​−bi​<=ci​

c a s e 3 : { a i − b i &gt; = 0 a i − b i &lt; = 0 case3:\begin{cases} a_i-b_i&gt;=0\\ a_i-b_i&lt;=0 \end{cases} case3:{ai​−bi​>=0ai​−bi​<=0​

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
template<typename T>void read(T &x){
	x=0;T neg=1;char r=getchar();
	while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
	while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
	x*=neg;
}
const int maxn=10000+10;
const int maxm=10000+10;
int n,m;
struct node{
	int e;
	int w;
	int nxt;
}edge[maxn<<1];
int head[maxn];
int cnt=0;
inline void addl(int u,int v,int w){
	edge[cnt].e=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
bool vis[maxn];
int dis[maxn];
bool flag;
void spfa(int u){
	if(flag)
		return;
	vis[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].nxt){
		int v=edge[i].e;
		if(dis[v]>dis[u]+edge[i].w){
			if(vis[v]){
				flag=true;
				return;
			}
			dis[v]=dis[u]+edge[i].w;
			spfa(v);
		}
	}
	vis[u]=false;
}
int main(){
	#ifndef ONLINE_JUDGE
    freopen("datain.txt","r",stdin);
    #endif
    read(n);
    read(m);
    clean(head,-1);
    loop(i,1,m){
    	int op,ai,bi,ci;
    	read(op);
		read(ai);
    	read(bi);
    	if(op!=3)
			read(ci);
		else ci=0; 
    	if(op==1)
    		addl(ai,bi,-ci);
    	else if(op==2)
    		addl(bi,ai,ci);
		else if(op==3){
    		addl(ai,bi,ci);
    		addl(bi,ai,ci);
		}
	}
	clean(dis,0x3f);
	dis[0]=0;
	loop(i,1,n)
		addl(0,i,0);
	clean(vis,false);
	flag=false;
	spfa(0);
	if(!flag)
		printf("Yes\n");
	else printf("No\n");
	return 0;
}