orz云神...

真的給跪了...BFS版spfa T 掉了...然后DFS版的就A了...我現(xiàn)在很迷茫....

這就是個(gè)普通的差分約束...?

------------------------------------------------------------------------------

#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#include<iostream>#define rep(i, n) for(int i = 0; i < n; ++i)#define clr(x, c) memset(x, c, sizeof(x))using namespace std;const int maxn = 10010;struct edge {int to, w;edge*next;} E[maxn << 1], *pt = E, *head[maxn];inline void add_edge(int u, int v, int d) {pt->to = v, pt->w = d;pt->next = head[u];head[u] = pt++;}int d[maxn], inS[maxn], cnt[maxn], n;stack<int> S;bool spfa() {rep(i, n)S.push(i), inS[i] = true, cnt[i] = 1, d[i] = 0;while(!S.empty()) {int x = S.top(); S.pop();inS[x] = false;for(edge*e = head[x]; e; e = e->next) if(d[e->to] > d[x] + e->w) { ? ?d[e->to] = d[x] + e->w; ? ?if(!inS[e->to]) {if(++cnt[e->to] > n) return false; ? ? ? ?S.push(e->to), inS[e->to] = true; ? ?}}}return true;}inline int read() {char c = getchar();for(; !isdigit(c); c = getchar());int ans = 0;for(; isdigit(c); c = getchar()) ? ?ans = ans * 10 + c - '0';return ans;}void init() {clr(head, 0);n = read();int m = read();while(m--) {int t = read(), u = read() - 1, v = read() - 1;if(t == 3)? ? ?add_edge(u, v, 0), add_edge(v, u, 0);else {int w = read();t == 1 ? add_edge(u, v, -w) : add_edge(v, u, w);}}}int main(){freopen("test.in", "r", stdin);init();printf(spfa() ? "Yes\n" : "No\n");return 0;}?

??

------------------------------------------------------------------------------?

3436: 小K的農(nóng)場(chǎng)

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?351??Solved:?186
[Submit][Status][Discuss]

Description

?背景

??? 小K是個(gè)特么喜歡玩MC的孩紙。。。

?描述

??? 小K在MC里面建立很多很多的農(nóng)場(chǎng)，總共n個(gè)，以至于他自己都忘記了每個(gè)農(nóng)場(chǎng)中種植作物的具體數(shù)量了，他只記得一些含糊的信息（共m個(gè)），以下列三種形式描述：農(nóng)場(chǎng)a比農(nóng)場(chǎng)b至少多種植了c個(gè)單位的作物，農(nóng)場(chǎng)a比農(nóng)場(chǎng)b至多多種植了c個(gè)單位的作物，農(nóng)場(chǎng)a與農(nóng)場(chǎng)b種植的作物數(shù)一樣多。但是，由于小K的記憶有些偏差，所以他想要知道存不存在一種情況，使得農(nóng)場(chǎng)的種植作物數(shù)量與他記憶中的所有信息吻合。輸入格式

?

Input

?? 第一行包括兩個(gè)整數(shù)n和m，分別表示農(nóng)場(chǎng)數(shù)目和小K記憶中的信息的數(shù)目

??? 接下來(lái)m行：

??? 如果每行的第一個(gè)數(shù)是1，接下來(lái)有三個(gè)整數(shù)a,b,c，表示農(nóng)場(chǎng)a比農(nóng)場(chǎng)b至少多種植了c個(gè)單位的作物??? 如果每行第一個(gè)數(shù)是2，接下來(lái)有三個(gè)整數(shù)a，b，c，表示農(nóng)場(chǎng)a比農(nóng)場(chǎng)b至多多種植了c個(gè)單位的作物

??? 如果每行第一個(gè)數(shù)是3，接下來(lái)有兩個(gè)整數(shù)a,b，表示農(nóng)場(chǎng)a種植的數(shù)量與b一樣多輸出格式

Output

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

Sample Input

33
312
1131
2232

Sample Output

Yes

樣例解釋

三個(gè)農(nóng)場(chǎng)種植的數(shù)量可以為（2,2,1）。


對(duì)于100%的數(shù)據(jù)，1<=n,m,a,b,c<=10000

HINT

Source

Kpmcup#0 By Greens

?

轉(zhuǎn)載于:https://www.cnblogs.com/JSZX11556/p/4657366.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3436: 小K的农场( 差分约束 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。