每日一题 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我觉得是影响不大的 甚至会更容易理解，因为不是更优就不会选这条路。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 10010 6 #define rep(i,s,e) for(register int i=s;i<=e;++i) 7 #define dwn(i,s,e) for(register int i=s;i>=e;--i) 8 using namespace std; 9 inline int read() 10 { 11 int x=0,f=1; 12 char c=getchar(); 13 while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} 14 while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} 15 return f*x; 16 } 17 int n,m,cnt; 18 int head[maxn],book[maxn],dis[maxn]; 19 struct node 20 { 21 int v,w,nex; 22 }edge[4*maxn]; 23 inline int add(int x,int y,int z) 24 { 25 edge[++cnt].v=y; 26 edge[cnt].w=z; 27 edge[cnt].nex=head[x]; 28 head[x]=cnt; 29 } 30 bool SPFA(int from) 31 { 32 book[from]=1; 33 for(int i=head[from];i;i=edge[i].nex) 34 { 35 int to=edge[i].v,val=edge[i].w; 36 if(dis[to]>dis[from]+val) 37 { 38 dis[to]=dis[from]+val; 39 if(book[to]==true) return false; 40 if(SPFA(to)==false) return false; 41 } 42 } 43 book[from]=0; 44 return true; 45 } 46 int main() 47 { 48 memset(dis,127,sizeof(dis)); 49 n=read();m=read(); 50 rep(i,1,m) 51 { 52 int in=read(); 53 if(in==1) 54 { 55 int a=read(),b=read(),c=read(); 56 add(a,b,-c); 57 } 58 else if(in==2) 59 { 60 int a=read(),b=read(),c=read(); 61 add(b,a,c); 62 } 63 else if(in==3) 64 { 65 int a=read(),b=read(); 66 add(a,b,0); 67 add(b,a,0); 68 } 69 } 70 rep(i,1,n) add(n+1,i,0); 71 dis[n+1]=0; 72 if(SPFA(n+1)==true) printf("Yes"); 73 else printf("No"); 74 return 0; 75 }
请各位大佬斧正