題目描述

小K在MC里面建立很多很多的農(nóng)場，總共n個，以至于他自己都忘記了每個農(nóng)場中種植作物的具體數(shù)量了，他只記得一些含糊的信息（共m個），以下列三種形式描述：

• 農(nóng)場a比農(nóng)場b至少多種植了c個單位的作物，
• 農(nóng)場a比農(nóng)場b至多多種植了c個單位的作物，
• 農(nóng)場a與農(nóng)場b種植的作物數(shù)一樣多。

但是，由于小K的記憶有些偏差，所以他想要知道存不存在一種情況，使得農(nóng)場的種植作物數(shù)量與他記憶中的所有信息吻合。

輸入輸出格式

輸入格式：

?

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

接下來 m 行：

如果每行的第一個數(shù)是 1，接下來有 3 個整數(shù) a,b,c，表示農(nóng)場 a 比農(nóng)場 b 至少多種植

了 c 個單位的作物。

如果每行的第一個數(shù)是 2，接下來有 3 個整數(shù) a,b,c，表示農(nóng)場 a 比農(nóng)場 b 至多多種植

了 c 個單位的作物。如果每行的第一個數(shù)是 3，家下來有 2 個整數(shù) a,b，表示農(nóng)場 a 終止的

數(shù)量和 b 一樣多。

?

輸出格式：

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

?

輸入輸出樣例

輸入樣例#1：?
3 3 3 1 2 1 1 3 1 2 2 3 2 輸出樣例#1：?
Yes

說明

對于 100% 的數(shù)據(jù)保證：1 ≤ n，m，a，b，c ≤ 10000。

?

Solution

　　圖論題思路還是比較簡單的.

　　看到這題莫名想到白皮上的食物鏈那道題...

　　試想一下,如果說有一種情況不存在,那么肯定是與之前有沖突.

　　所以想到大概方向:

　　　　我們只要判斷是否有語句是假的即可.

　　然后想一想食物鏈那道題？

　　那道用的是并查集,那么在這里很顯然行不通.于是想到建一個有權圖？

?

　　關于這個圖,我們可以這樣建:

　　　1) 對于至少的,我們采用負邊.因為:a>=b+c 可以寫成: b-a<=-c

　　? ? 2) 對于至多的,我們采用正邊.同理.

　　? ? 3) 對于相等的,我們直接加一條權值為0的邊即可.?

?

　? ?然后再SPFA判斷負環(huán)即可.

? ? ? 關于為什么是判斷負環(huán)，也很好推其實.

? ? ? 因為如果是不滿足的情況即是對于一個點對

? ? ? 已經(jīng)滿足a大于b 但是又有另外一組關系使得b大于a .

? ? ? 那么我們就會沖突，此時即為不滿足.

? ? ??

?

代碼

　　

#include<bits/stdc++.h> using namespace std; const int maxn=100008; struct sj {int to;int next;int w; }a[maxn*2]; int size,head[maxn*2],dis[maxn*2]; int vis[maxn*2],pd,n,m; void add(int x,int y,int z) {a[++size].to=y;a[size].w=z;a[size].next=head[x];head[x]=size; } void spfa(int x) {vis[x]=1;for(int i=head[x];i;i=a[i].next){int to=a[i].to;if(dis[to]>dis[x]+a[i].w){if(pd||vis[to]) {pd=1;break;}dis[to]=dis[x]+a[i].w;spfa(to);}}vis[x]=0; } int main() {cin>>n>>m; for(int i=1;i<=m;i++){int p,x,y,z;scanf("%d",&p);if(p==1)scanf("%d%d%d",&x,&y,&z),add(x,y,-z);if(p==2)scanf("%d%d%d",&x,&y,&z),add(y,x,z);if(p==3)scanf("%d%d",&x,&y),add(x,y,0),add(y,x,0);}memset(dis,0x7f,sizeof(dis));for(int i=1;i<=n;i++){dis[i]=0;spfa(i);}if(pd) {cout<<"No";return 0;}cout<<"Yes";return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Kv-Stalin/p/9093732.html

總結

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

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