每日一题 day55 打卡
Analysis
这是我们一次考试的T1，但我忘了差分约束系统怎么写了，所以就直接输出Yes混了60分
首先转化题目：
1：表示农场 a 比农场 b 至少多种植了 c 个单位的作物。即a>=b+c 转化后为 b-a<=-c
2：表示农场 a 比农场 b 至多多种植了 c 个单位的作物。即a<=b+c 转化后为 a-b<=c
3：表示农场 a 与农场 b 种植数一样 即a=b 可以表示为 a-b<=0 与 b-a<=0
接下来就是判负环了 而为什么是判负环呢？ 因为由题意可得 a>b且b>a一定是不合法的（即情况1的矛盾）而正环、正+负环、以及中间穿插0的情况都是合法的（脑补即可）
至于情况3我觉得是影响不大的 甚至会更容易理解，因为不是更优就不会选这条路。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10010
#define rep(i,s,e) for(register int i=s;i<=e;++i)
#define dwn(i,s,e) for(register int i=s;i>=e;--i)
using namespace std;
inline int read()
{
int x=,f=;
char c=getchar();
while(c<''||c>'') {if(c=='-') f=-; c=getchar();}
while(c>=''&&c<='') {x=x*+c-''; c=getchar();}
return f*x;
}
int n,m,cnt;
int head[maxn],book[maxn],dis[maxn];
struct node
{
int v,w,nex;
}edge[*maxn];
inline int add(int x,int y,int z)
{
edge[++cnt].v=y;
edge[cnt].w=z;
edge[cnt].nex=head[x];
head[x]=cnt;
}
bool SPFA(int from)
{
book[from]=;
for(int i=head[from];i;i=edge[i].nex)
{
int to=edge[i].v,val=edge[i].w;
if(dis[to]>dis[from]+val)
{
dis[to]=dis[from]+val;
if(book[to]==true) return false;
if(SPFA(to)==false) return false;
}
}
book[from]=;
return true;
}
int main()
{
memset(dis,,sizeof(dis));
n=read();m=read();
rep(i,,m)
{
int in=read();
if(in==)
{
int a=read(),b=read(),c=read();
add(a,b,-c);
}
else if(in==)
{
int a=read(),b=read(),c=read();
add(b,a,c);
}
else if(in==)
{
int a=read(),b=read();
add(a,b,);
add(b,a,);
}
}
rep(i,,n) add(n+,i,);
dis[n+]=;
if(SPFA(n+)==true) printf("Yes");
else printf("No");
return ;
}
请各位大佬斧正（反正我不认识斧正是什么意思）