负环问题通常可以使用SPFA的dfs和bfs实现来完成。需要注意的是SPFA的bfs实现复杂度可能会飙到O(n^3)因而不适合使用，所以我们通常采用dfs实现。（虽然感觉这玩意的复杂度也不是特别稳定？）
需要注意两个问题
- 求负环时跑最短路还是最长路要根据题意决定
- 无需设置初态dis为infinity,否则可能会T掉
10082. 「一本通 3.3 例 1」Word Rings
简单的建图,注意这里要跑最长路
#include <bits/stdc++.h>
using namespace std;
vector <pair<int,double> > g[1000005];
namespace SPFA {
int m,ins[1000005],vis[1000005],fg=0,t1,t2,t3;
double dis[1000005];
vector <pair<int,double> > g[1000005];
void dfs(int p){
ins[p]=1; vis[p]=1;
for(int i=0;i<g[p].size()&&!fg;i++)
if(dis[g[p][i].first]<dis[p]+g[p][i].second){
dis[g[p][i].first]=dis[p]+g[p][i].second;
if(ins[g[p][i].first]==0)
dfs(g[p][i].first);
else {fg=1; return;}}
ins[p]=0;
}
bool solve() {
int n=1000; fg=0;
memset(ins,0,sizeof ins);
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++) dis[i]=0;
for(int i=1;i<=n;i++) {
if(vis[i]==0) {
dfs(i);
}
if(fg) return true;
}
return false;
}
}
int T,n;
inline int calc(char x,char y) {
return (x-'a')*30+(y-'a')+1;
}
int main() {
while(cin>>n && n) {
string str;
for(int i=1;i<=1000;i++)
g[i].clear();
for(int i=1;i<=n;i++) {
cin>>str;
if(str.length()>1) {
g[calc(str[0],str[1])].push_back(make_pair(calc(str[str.length()-2],str[str.length()-1]),str.length()));
}
}
double L=0,R=1e+5;
while(R-L>1e-6) {
double M=(L+R)/2;
for(int i=1;i<=1000;i++)
SPFA::g[i].clear();
for(int i=1;i<=1000;i++)
for(int j=0;j<g[i].size();j++)
SPFA::g[i].push_back(make_pair(g[i][j].first,g[i][j].second-M));
if(SPFA::solve()) L=M;
else R=M;
}
if(L==0) cout<<"No solution"<<endl;
else cout<<L<<endl;
}
}
10083. 「一本通 3.3 例 2」双调路径
没看出这题和负环有什么关系，分层图最短路即可
#include <bits/stdc++.h>
using namespace std;
const int N=1100005;
vector <pair<int,int> > g[N];
int d[N],v[N],n,m,s,e,p,r,c,t;
void make(int t1,int t2,int t3) {
g[t1].push_back(make_pair(t2,t3));
}
void solve(int v0) {
queue<int>q;
d[v0]=0; v[v0]=1;
q.push(v0);
while(q.size()) {
int p=q.front();
q.pop();
v[p]=0;
for(int i=0;i<g[p].size();i++) {
int x=g[p][i].first,y=g[p][i].second;
if(d[x]>d[p]+y) {
d[x]=d[p]+y;
if(!v[x]) q.push(x), v[x]=1;
}
}
}
}
inline int calc(int nd,int cs) {
return nd*10200+cs+1;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>s>>e;
for(int i=1;i<=m;i++) {
cin>>p>>r>>c>>t;
for(int j=0;j<=10000;j++) {
make(calc(p,j),calc(r,j+c),t),
make(calc(r,j),calc(p,j+c),t);
}
}
int cnt=0;
memset(d,0x3f,sizeof d);
solve(calc(s,0));
int mx=0x3f3f3f3f;
for(int i=0;i<=10000;i++)
cnt+=(d[calc(e,i)]<mx?1:0),
mx=min(mx,d[calc(e,i)]);
cout<<cnt<<endl;
return 0;
}
10084. 「一本通 3.3 练习 1」最小圈
一开始dis设infinity然后狂T不止
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int ins[N],vis[N],n,m,flag;
double dis[N],M;
vector <pair<int,double> > g[N];
void dfs(int p) {
ins[p]=vis[p]=1;
for(int i=0;i<g[p].size()&&!flag;i++) {
int q=g[p][i].first;
if(dis[q]>dis[p]+g[p][i].second-M) {
dis[q]=dis[p]+g[p][i].second-M;
if(ins[q]) {
flag=1;
return;
}
dfs(q);
}
if(flag) return;
}
ins[p]=0;
}
int main() {
ios::sync_with_stdio(false);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int t1,t2;double t3;
scanf("%d%d%lf",&t1,&t2,&t3);
g[t1].push_back(make_pair(t2,t3));
}
double L=-1e+7,R=1e+7;
while(R-L>1e-9) {
M=(L+R)/2;
memset(vis,0,sizeof vis);
memset(ins,0,sizeof ins);
memset(dis,0,sizeof dis);
flag=0;
for(int i=1;i<=n;i++) {
if(vis[i]==0) {
dfs(i);
}
if(flag) break;
}
if(flag) R=M;
else L=M;
}
cout<<setiosflags(ios::fixed)<<setprecision(8)<<L+1e-9<<endl;
}
10085. 「一本通 3.3 练习 2」虫洞 Wormholes
#include <bits/stdc++.h>
using namespace std;
int n,m,w,ins[1000005],vis[1000005],dis[1000005],fg=0,t1,t2,t3,T;
vector <pair<int,int> >g[1000005];
void dfs(int p) {
ins[p]=1; vis[p]=1;
for(int i=0;i<g[p].size()&&!fg; i++) {
if(dis[g[p][i].first]>dis[p]+g[p][i].second) {
dis[g[p][i].first]=dis[p]+g[p][i].second;
if(ins[g[p][i].first]==0) dfs(g[p][i].first);
else fg=1;
}
}
ins[p]=0;
}
int main() {
cin>>T;
while(T--) {
fg=0;
memset(ins,0,sizeof ins);
memset(vis,0,sizeof vis);
memset(dis,0,sizeof dis);
cin>>n>>m>>w;
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=m;i++) {
cin>>t1>>t2>>t3;
g[t1].push_back(make_pair(t2,t3));
g[t2].push_back(make_pair(t1,t3));
}
for(int i=1;i<=w;i++) {
cin>>t1>>t2>>t3;
g[t1].push_back(make_pair(t2,-t3));
}
for(int i=1;i<=n;i++) if(vis[i]==0) dis[i]=0, dfs(i);
if(fg==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
10086. 「一本通 3.3 练习 3」Easy SSSP
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int dis[N],vis[N],ins[N],n,m,t1,t2,t3,flag;
vector <pair<int,int> > g[N];
void dfs(int p) {
vis[p]=ins[p]=1;
for(int i=0;i<g[p].size();i++) {
int q=g[p][i].first;
if(dis[q]>dis[p]+g[p][i].second) {
dis[q]=dis[p]+g[p][i].second;
if(ins[q]) {
flag=1;
return;
}
else {
dfs(q);
}
}
}
ins[p]=0;
}
void spfa(int s) {
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
queue <int> q;
q.push(s); dis[s]=0; vis[s]=1;
while(!q.empty()) {
int p=q.front(); q.pop(); vis[p]=0;
for(int i=0;i<g[p].size();i++) {
int x=g[p][i].first, y=g[p][i].second;
if(dis[x] > dis[p]+y) {
dis[x] = dis[p]+y;
if(!vis[x]) {
q.push(x);
vis[x]=1;
}
}
}
}
for(int i=1;i<=n;i++) {
if(dis[i]>=0x3f3f3f3f) cout<<"NoPath"<<endl;
else cout<<dis[i]<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
int s;
cin>>s;
for(int i=1;i<=m;i++) {
cin>>t1>>t2>>t3;
g[t1].push_back(make_pair(t2,t3));
}
for(int i=1;i<=n;i++) {
if(vis[i]==0) {
dfs(i);
}
if(flag) break;
}
if(flag) {
cout<<"-1"<<endl;
}
else {
spfa(s);
}
return 0;
}