https://www.luogu.org/problemnew/show/P1993

題解：SPFA+差分約束系統(tǒng)

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int a,b,c,dis[N],vis[N]; char str; struct node{int v,w;node(){};node(int _v,int _w):v(_v),w(_w){} }x; vector<node>G[N]; bool SPFA(int u){vis[u]=1;for(int i=0,j=G[u].size();i<j;i++){int v=G[u][i].v;if(dis[v]<dis[u]+G[u][i].w){dis[v]=dis[u]+G[u][i].w;if(vis[v])return 0;if(!SPFA(v))return 0;}}vis[u]=0;return 1; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d",&k);if(k==1){scanf("%d%d%d",&a,&b,&c);G[b].push_back({a,c});}else if(k==2){scanf("%d%d%d",&a,&b,&c);G[a].push_back({b,-c});}else if(k==3){scanf("%d%d",&a,&b);G[a].push_back({b,0});G[b].push_back({a,0});}}for(int i=1;i<=n;i++){G[0].push_back({i,0});dis[i]=-INF;}cout<<(SPFA(0)?"Yes":"No")<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

原博客

#include<bits/stdc++.h> #define il inline #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; const int N=50005,inf=23333333; int n,m,to[N],net[N],w[N],dis[N],cnt,h[N],tot[N]; bool vis[N];il int gi(){int a=0;char x=getchar();while(x<'0'||x>'9')x=getchar();while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();return a; }il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;}il bool spfa(int u){vis[u]=1;for(int i=h[u];i;i=net[i])if(dis[to[i]]<dis[u]+w[i]){dis[to[i]]=dis[u]+w[i];if(vis[to[i]])return 0;if(!spfa(to[i]))return 0;}vis[u]=0;return 1; }int main(){n=gi(),m=gi();int f,a,b,c;while(m--){f=gi(),a=gi(),b=gi();if(f==1)c=gi(),add(b,a,c);else if(f==2)c=gi(),add(a,b,-c);else if(f==3)add(a,b,0),add(b,a,0);}For(i,1,n)add(0,i,0),dis[i]=-inf;if(!spfa(0))cout<<"No";else cout<<"Yes";return 0; }

?

總結(jié)

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

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