背景
小K是个特么喜欢玩MC的孩纸。。。
描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得
一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多
多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存
不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”
用dis表示不等式，然后跑最短路或者最长路即可。 9520ms
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=100010; int Laxt[maxn],Next[maxn],To[maxn],Len[maxn]; int cnt,vis[maxn],num[maxn],dis[maxn],N; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } bool SPFA() { queue<int>q; memset(dis,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[10]=1; num[0]++; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[v]<dis[u]+Len[i]){ dis[v]=dis[u]+Len[i]; if((++num[v])==N) return false; if(!vis[v]) vis[v]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }
然后优化了一下，把次数改为前者+1，而不是自加1。4452ms。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=20010; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],Len[maxn<<1]; int cnt,vis[maxn],num[maxn],dis[maxn],N; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } bool SPFA() { queue<int>q; memset(dis,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[0]=1; num[0]++; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[v]<dis[u]+Len[i]){ dis[v]=dis[u]+Len[i]; num[v]=num[u]+1; if(num[v]==N) return false; if(!vis[v]) vis[v]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }
把queue改为stack，然后就124ms了，估计不是因为queue比stack快，而是数据使然。
（据说是改为stck变为深搜DFS了！）
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=20010; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],Len[maxn<<1]; int cnt,vis[maxn],num[maxn],dis[maxn],N; void add(int u,int v,int w){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w; } bool SPFA() { stack<int>q; memset(dis,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[0]=1; num[0]++; while(!q.empty()){ int u=q.top(); q.pop(); vis[u]=0; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(dis[v]<dis[u]+Len[i]){ dis[v]=dis[u]+Len[i]; num[v]=num[u]+1; if(num[v]==N) return false; if(!vis[v]) vis[v]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }
BZOJ3436: 小K的农场（差分约束裸题&DFS优化判环）
原文：https://www.cnblogs.com/hua-dong/p/9997927.html