1.虫洞 Wormholes（裸spfa判断负环问题）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
1. #in#include<bits/stdc++.h> using namespace std; int n,m,W; const int N=510,M=5210; int h[N],e[M],ne[M],w[M],idx; int dist[N],cnt[N],q[N];//cnt记录是某个点经过的边数 bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { memset(st,0,sizeof st);//情况上一层的状态 memset(cnt,0,sizeof cnt);//情况上一层的状态 int hh=0,tt=0; for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中 while(hh!=tt) { int t=q[hh++]; st[t]=false;//标记这个点已经不在队列中了 if(hh==N) hh=0;//循环数组 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i])//假如距离比他小 { dist[j]=dist[t]+w[i];//更新距离 cnt[j]=cnt[t]+1;//更新所走过的边数 if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照最小距离更新，所有是负环 if(!st[j])//假如不在队列中则加到队列中 { q[tt++]=j; st[j]=true; if(tt==N) tt=0; } } } } return false;//反之没负环 } void solve() { memset(h,-1,sizeof h);//初始化 idx=0; cin>>n>>m>>W; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } while(W--)//假如是虫洞，就建立负边 { int a,b,c; cin>>a>>b>>c; add(a,b,-c); } if(spfa()) puts("YES");//假如有负环 else puts("NO"); } int main() { int T; cin>>T; while(T--) solve(); return 0; }
栈优化
#include<bits/stdc++.h> using namespace std; int n,m,W; const int N=510,M=5210; int h[N],e[M],ne[M],w[M],idx; int dist[N],cnt[N],q[N];//cnt记录是某个点经过的边数 bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { memset(st,0,sizeof st);//情况上一层的状态 memset(cnt,0,sizeof cnt);//情况上一层的状态 int tt=0; for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中 while(tt!=0) { int t=q[--tt]; st[t]=false;//标记这个点已经不在队列中了 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i])//假如距离比他小 { dist[j]=dist[t]+w[i];//更新距离 cnt[j]=cnt[t]+1;//更新所走过的边数 if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照最小距离更新，所有是负环 if(!st[j])//假如不在队列中则加到队列中 { q[tt++]=j; st[j]=true; } } } } return false;//反之没负环 } void solve() { memset(h,-1,sizeof h);//初始化 idx=0; cin>>n>>m>>W; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } while(W--)//假如是虫洞，就建立负边 { int a,b,c; cin>>a>>b>>c; add(a,b,-c); } if(spfa()) puts("YES");//假如有负环 else puts("NO"); } int main() { int T; cin>>T; while(T--) solve(); return 0; }
2.观光奶牛（01分数规划+spfa判断负环）
朴素spfa
#include<bits/stdc++.h> using namespace std; int n,m; const int N=1010,M=5010; int h[N],e[M],ne[M],idx; double dist[N],wf[N],wt[M]; int cnt[N],q[N];//cnt记录是某个点经过的边数 bool st[N]; void add(int a,int b,int c) { e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(double mid) { memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); int hh=0,tt=0; for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中 while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0;//循环数组 st[t]=false;//标记这个点已经不在队列中了 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+wf[t]-mid*wt[i])//假如负和01分数规划分析的 { dist[j]=dist[t]+wf[t]-mid*wt[i];//则更新 cnt[j]=cnt[t]+1;//更新所走过的边数 if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照01分数规划更新，所有是负环 if(!st[j])//假如不在队列中则加到队列中 { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return false;//反之没负环 } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) cin>>wf[i]; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } double l=0,r=1000;//分析最大可能是1000，最小是0 while(r-l>1e-4)//二分答案，因为要输出两位小数，则精度得是两位小数，则二分则是多两位是4位 { double mid=(l+r)/2; if(spfa(mid)) l=mid; else r=mid; } printf("%.2lf\n",l); return 0; }
栈优化
#include<bits/stdc++.h> using namespace std; int n,m; const int N=1010,M=5010; int h[N],e[M],ne[M],idx; double dist[N],wf[N],wt[M]; int cnt[N],q[N];//cnt记录是某个点经过的边数 bool st[N]; void add(int a,int b,int c) { e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(double mid) { memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); int tt=0; for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中 while(tt!=0) { int t=q[--tt]; st[t]=false;//标记这个点已经不在队列中了 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+wf[t]-mid*wt[i])//假如负和01分数规划分析的 { dist[j]=dist[t]+wf[t]-mid*wt[i];//则更新 cnt[j]=cnt[t]+1;//更新所走过的边数 if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照01分数规划更新，所有是负环 if(!st[j])//假如不在队列中则加到队列中 { q[tt++]=j; st[j]=true; } } } } return false;//反之没负环 } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) cin>>wf[i]; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } double l=0,r=1000;//分析最大可能是1000，最小是0 while(r-l>1e-4)//二分答案，因为要输出两位小数，则精度得是两位小数，则二分则是多两位是4位 { double mid=(l+r)/2; if(spfa(mid)) l=mid; else r=mid; } printf("%.2lf\n",l); return 0; }
3.（单词环）Word Rings
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题建图很重要，按照前两个字母与后两个来建图然后前两个字母指向后两个字母边权为该字符串的长度
法一：还有建好图还得spfa假如直接跑就容易wa,这时我们可以加个优化，也就是做题经验，当更新次数超过最大输入的边数的2倍,我们就可以认为是有负环的
法二：还有一种优化方法是把循环队列换成栈，这样更快找到负环
#include<bits/stdc++.h> using namespace std; const int N=700,M=1e5+10; int h[N],e[M],ne[M],w[M],idx; double dist[N]; int n; bool st[N]; int cnt[N],q[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(double mid) { memset(st,0,sizeof st);//清空上一层状态 memset(cnt,0,sizeof cnt);//清空上一层状态 int hh=0,tt=0; int count=0;//用来标记运行的次数 for(int i=0;i<26*26;i++) q[tt++]=i,st[i]=true;//把所有点入队 while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0;//循环队列 st[t]=false;//标记这个点出队了 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i]-mid)//假如满足01分数规划分析的 { dist[j]=dist[t]+w[i]-mid; cnt[j]=cnt[t]+1;//更新走的边数 if(cnt[j]>=N) return true;//假如大于全部的点了，说明有的点已经重复走过了，有环 if(++count>2*n) return true;//假如运行超过最大边数的两倍也说明有环 if(!st[j])//假如不在队列中 { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return false;//则没有环 } int main() { char str[1010]; while(scanf("%d",&n),n) { memset(h,-1,sizeof h); idx=0; for(int i=0;i<n;i++) { scanf("%s",str); int len=strlen(str); if(len<2) continue; int a=(str[0]-'a')*26+(str[1]-'a'),b=(str[len-2]-'a')*26+(str[len-1]-'a');//把两个字母对应到26进制中 add(a,b,len);//把a->b连接起来边权是串的长度 } if(!spfa(0))//假如0都不通过则就是没环了 { puts("No solution"); continue; } double l=0,r=1000; while(r-l>1e-4)//二分 { double mid=(l+r)/2; if(spfa(mid)) l=mid;//假如满足 else r=mid; } printf("%lf\n",l); } return 0; }
栈优化
#include<bits/stdc++.h> using namespace std; const int N=700,M=1e5+10; int h[N],e[M],ne[M],w[M],idx; double dist[N]; int n; bool st[N]; int cnt[N],q[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa(double mid) { memset(st,0,sizeof st);//清空上一层状态 memset(cnt,0,sizeof cnt);//清空上一层状态 int tt=0; for(int i=0;i<26*26;i++) q[tt++]=i,st[i]=true;//把所有点入队 while(tt!=0) { int t=q[--tt]; st[t]=false;//标记这个点出队了 for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i]-mid)//假如满足01分数规划分析的 { dist[j]=dist[t]+w[i]-mid; cnt[j]=cnt[t]+1;//更新走的边数 if(cnt[j]>=N) return true;//假如大于全部的点了，说明有的点已经重复走过了，有环 if(!st[j])//假如不在队列中 { q[tt++]=j; st[j]=true; } } } } return false;//则没有环 } int main() { char str[1010]; while(scanf("%d",&n),n) { memset(h,-1,sizeof h); idx=0; for(int i=0;i<n;i++) { scanf("%s",str); int len=strlen(str); if(len<2) continue; int a=(str[0]-'a')*26+(str[1]-'a'),b=(str[len-2]-'a')*26+(str[len-1]-'a');//把两个字母对应到26进制中 add(a,b,len);//把a->b连接起来边权是串的长度 } if(!spfa(0))//假如0都不通过则就是没环了 { puts("No solution"); continue; } double l=0,r=1000; while(r-l>1e-4)//二分 { double mid=(l+r)/2; if(spfa(mid)) l=mid;//假如满足 else r=mid; } printf("%lf\n",l); } return 0; }
