Description

背景 小K是個特么喜歡玩MC的孩紙。。。 描述 小K在MC里面建立很多很多的農場，總共n個，以至于他自己都忘記了每個農場中種植作物的具體數量了，他只記得 一些含糊的信息（共m個），以下列三種形式描述：農場a比農場b至少多種植了c個單位的作物，農場a比農場b至多 多種植了c個單位的作物，農場a與農場b種植的作物數一樣多。但是，由于小K的記憶有些偏差，所以他想要知道存 不存在一種情況，使得農場的種植作物數量與他記憶中的所有信息吻合。

Input

第一行包括兩個整數n和m，分別表示農場數目和小K記憶中的信息的數目接下來m行：如果每行的第一個數是1，接 下來有三個整數a,b,c，表示農場a比農場b至少多種植了c個單位的作物如果每行第一個數是2，接下來有三個整數a ，b，c，表示農場a比農場b至多多種植了c個單位的作物如果每行第一個數是3，接下來有兩個整數a,b，表示農場a 種植的數量與b一樣。1<=n,m,a,b,c<=10000

?

Output

如果存在某種情況與小K的記憶吻合，輸出”Yes”，否則輸出”No”

?

Sample Input

3 3
3 1 2
1 1 3 1
2 2 3 2

Sample Output

Yes 差分約束有一段時間沒做了，又看了一遍，感覺比以前有了更好的認識。 接下來是證明： 然后，相等的情況，只需要連一條邊，不然的話，相當于一個 0 的長度的環，又不能松弛，也不會死循環在里面，但是，在遍歷鄰接表的時候； 每次都做了無用的比較。 1 /************************************************************** 2 Problem: 3436 3 User: TreeDream 4 Language: C++ 5 Result: Accepted 6 Time:140 ms 7 Memory:2220 kb 8 ****************************************************************/ 9 10 #include <bits/stdc++.h> 11 12 using namespace std; 13 14 const int maxn = 10010; 15 16 struct Edge 17 { 18 int from,to,dist; 19 }; 20 21 inline int getint() 22 { 23 int w=0,q=0; char c=getchar(); 24 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 25 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 26 } 27 28 struct BellmanFord 29 { 30 int n,m; 31 vector<Edge> edges; 32 vector<int> G[maxn]; 33 bool inq[maxn]; 34 int d[maxn]; 35 int p[maxn]; 36 int cnt[maxn]; 37 38 void init(int n) 39 { 40 this->n = n; 41 for(int i=0; i<n; i++) G[i].clear(); 42 edges.clear(); 43 } 44 45 void AddEdge(int from,int to,int dist) 46 { 47 edges.push_back((Edge) 48 { 49 from,to,dist 50 }); 51 m = edges.size(); 52 G[from].push_back(m-1); 53 } 54 55 bool negativeCycle() 56 { 57 queue<int> Q; 58 memset(inq,0,sizeof(inq)); 59 memset(cnt,0,sizeof(cnt)); 60 for(int i=0; i<n; i++) 61 { 62 d[i] = 0; 63 inq[0] = true; 64 Q.push(i); 65 } 66 67 while(!Q.empty()) 68 { 69 int u = Q.front(); 70 Q.pop(); 71 inq[u] = false; 72 for(int i=0; i<G[u].size(); i++) 73 { 74 Edge& e = edges[G[u][i]]; 75 if(d[e.to]>d[u]+e.dist) 76 { 77 d[e.to] = d[u] + e.dist; 78 p[e.to] = G[u][i]; 79 if(!inq[e.to]) { 80 Q.push(e.to); 81 inq[e.to] = true; 82 if(++cnt[e.to]>n) 83 return true; 84 } 85 } 86 } 87 } 88 return false; 89 } 90 91 }; 92 93 BellmanFord sol; 94 95 int main() 96 { 97 int n,m; 98 n = getint(); 99 m = getint(); 100 101 sol.init(n+1); 102 int a,b,c; 103 int flag; 104 while(m--) 105 { 106 flag = getint(); 107 //scanf("%d",&flag); 108 if(flag==2) 109 { 110 a = getint(); 111 b = getint(); 112 c = getint(); 113 //scanf("%d%d%d",&a,&b,&c); 114 sol.AddEdge(b,a,c); 115 } 116 else if(flag==1) 117 { 118 a = getint(); 119 b = getint(); 120 c = getint(); 121 //scanf("%d%d%d",&a,&b,&c); 122 sol.AddEdge(a,b,-c); 123 } 124 else if(flag==3) 125 { 126 a = getint(); 127 b = getint(); 128 //scanf("%d%d",&a,&b); 129 sol.AddEdge(a,b,0); 130 //sol.AddEdge(b,a,0); 131 } 132 } 133 for(int i=0; i<n; i++) 134 sol.AddEdge(0,i,0); 135 136 if(sol.negativeCycle()) 137 { 138 puts("No"); 139 } 140 else puts("Yes"); 141 142 return 0; 143 } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/6576816.html

總結

以上是生活随笔為你收集整理的BZOJ 3436 小K的农场 差分约束的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。