每日一题 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 }

请各位大佬斧正

12-26 09:47