P1993 小 K 的農場

題解：

農場 a 比農場 b 至少多種植了 c 個單位的作物；
這句話說明：a - b > = c
轉化可得 b - a < = - c
add(a,b,-c)
農場 a 比農場 b 至多多種植了 c 個單位的作物；
說明：a - b <= c
add(b,a,c)
農場 a 與農場 b 種植的作物數一樣多。
說明a - b < = 0
b - a < = 0
add(a,b,0)
add(b,a,0)

代碼：

#include<bits/stdc++.h> #define MAXN 50005 #define inf int(16843009) using namespace std; int N,M,s,t; struct edge{int v,w;edge(int v=0, int w=0):v(v),w(w){}; }; vector<edge> adj[MAXN]; int d[MAXN], cnt[MAXN]; bool inq[MAXN];bool spfa(int s){memset(d, 1, sizeof(d));queue<int> q;d[s] = 0; q.push(s); inq[s] = 1;int u,v,w;while(!q.empty()){ u = q.front(); q.pop(); inq[u] = 0;for(int i=0;i<adj[u].size();i++){v = adj[u][i].v; w = adj[u][i].w;if(d[u] + w < d[v]){d[v] = d[u] + w;cnt[v] = cnt[u] + 1;//cnt[v] = s->v最短路包含的邊數 if(cnt[v] >= N+1) return 1;//判負環 if(inq[v]==0){q.push(v); inq[v] = 1;} }}} return 0; }int main(){//freopen("P1993_2.in","r",stdin);scanf("%d%d", &N, &M);int d,u,v,w;for(int i=1;i<=M;i++){cin>>d;if(d==1){scanf("%d%d%d", &v, &u, &w);adj[v].push_back(edge(u,-w));}else if(d==2){scanf("%d%d%d", &v, &u, &w);adj[u].push_back(edge(v,w));}else if(d==3){scanf("%d%d", &v, &u);adj[u].push_back(edge(v,0));adj[v].push_back(edge(u,0));}}s = 0;for(int i=1;i<=N;i++){adj[0].push_back(edge(i,0));}if(spfa(0)){printf("No\n");}else cout<<"Yes"<<endl;return 0; }

總結

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

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