【题目描述】
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量//代码效果参考：http://www.lyjsj.net.cn/wz/art_24259.html
了，他只记得一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。【输入格式】 farm.in
第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息数目。
接下来m行：
如果每行的第一个数是1，接下来有3个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物。
如果每行的第一个数是2，接下来有3个整数a,b,c，表示农场a比农场b至多多种植了c个单位的作物。
如果每行第一个数是3，家下来有2个整数a,b，表示农场a终止的数量和b一样多。
【输出格式】 farm.out
如果存在某种情况与小K的记忆吻合，输出“Yes”，否则输出“No”。
【样例输入】
3 3
3 1 2
1 1 3 1
2 2 3 2
【样例输出】
Yes
样例解释：三个农场种植数量可以为(2,2,1)。
对于100%的数据 1<=n,m,a,b,c<=10000.
裸的spfa_dfs判负环
1 #include
2 #include
3 using namespace std;
4
5 struct Edge
6 {
7 int to,w,next;
8 }E【10000001】;
9 int node=0,head【10001】,dist【10001】;
10 bool vis【10001】;
11
12 int n,m;
13 bool flag;
14
15 void insert(int u,int v,int w)
16 {
17 E【++node】=(Edge){v,w,head【u】};
18 head【u】=node;
19 }
20
21 void spfa_dfs(int s)
22 {
23 vis【s】=1;
24 for(int i=head【s】;i;i=E【i】.next)
25 {
26 int to=E【i】.to,w=E【i】.w;
27 if(dist【s】+w[span style="color: rgba(0, 0, 0, 1)">dist【to】)
28 {
29 if(vis【to】){flag=1;return;}
30 else
31 {
32 dist【to】=dist【s】+w;
33 spfa_dfs(to);
34 }
35 }
36 }
37 vis【s】=0;
38 }
39
40 bool check()
41 {
42 flag=0;
43 memset(dist,0x7f,sizeof(dist));
44 memset(vis,0,sizeof(vis));
45 for(int i=1;i<=n;i++)
46 {
47 dist【i】=0;
48 spfa_dfs(i);
49 if(flag) return 1;
50 }
51 return 0;
52 }
53
54 int read()
55 {
56 int x=0,f=1;char ch=getchar();
57 while(ch[span style="color: rgba(128, 0, 0, 1)">'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
58 while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();}
59 return xf;
60 }
61
62 int main()
63 {
64 n=read();m=read();
6//代码效果参考：http://www.lyjsj.net.cn/wz/art_24257.html
5 for(int i=1;i<=m;i++)66 {
67 int f,a,b,c;
68 f=read();
69 switch(f)
70 {
71 case 1:
72 a=read();b=read();c=read();
73 insert(a,b,-c);
74 break;
75 case 2:
76 a=read();b=read();c=read();
77 insert(b,a,c);
78 break;
79 case 3:
80 a=read();b=read();
//代码效果参考：http://www.lyjsj.net.cn/wx/art_24255.html
81 insert(a,b,0);82 insert(b,a,0);
83 break;
84 }
85 }
86 if(check()) printf("No");
87 else printf("Yes");
88 return 0;
89 }
