负环，即负权环，指在图 \(G\) 中边权和为负数的一回路。
负环的判定一般有两种方式。
以下均以 \(n\) 点 \(m\) 边的图 \(G\) 为例。
- 法一：以边为研究对象。
注意到最短路边数一定不超过 \(n-1\) 边，因此维护 \(cnt_x\) 表示起点到 \(x\) 的边数，若某一时刻存在 \(cnt_x>n-1\) 则存在负环。
- 法二：以点为研究对象（不推荐）。
注意到一点 \(x\) 至多被 \(n-1\) 个不同的点松弛，因此维护 \(cnt_x\) 统计松弛次数即可。
不推荐是因为这玩意在有重边时用不了，且容易写错。
负环判定在实现时用 SPFA 就好了。
T1
板子。
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=1e4+5;
int t,n,m;
int dis[N],cnt[N];
bool vis[N];
struct Edge{
int v,w;
};
vector<Edge> G[M];
bool spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int> q;
q.push(s),dis[s]=0,vis[s]=1;
while(!q.empty()){
int now=q.front(); q.pop(),vis[now]=0;
for(auto i:G[now]){
if(dis[i.v]>dis[now]+i.w){
dis[i.v]=dis[now]+i.w;
cnt[i.v]=cnt[now]+1;
if(cnt[i.v]>n-1) return 1;
if(!vis[i.v]) q.push(i.v),vis[i.v]=1;
}
}
}
return 0;
}
string sol(){
cin>>n>>m;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
G[u].push_back({v,w});
if(w>=0) G[v].push_back({u,w});
}
return spfa(1)?"YES\n":"NO\n";
}
int main(){
cin>>t;
while(t--) cout<<sol();
return 0;
}
T2
首先有负环就是距离可以无限缩小。
然后跑两边 SPFA，起点分别为 \(1,n\)，取 \(\min(dis_1,dis_n)\) 即为答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,M=1e4+5;
int t,n,m;
int dis1[N],disn[N],cnt[N];
bool vis[N];
struct Edge{ int v,w; };
vector<Edge> G1[M];
bool spfa1(int s){
memset(dis1,0x3f,sizeof(dis1));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int> q;
q.push(s),dis1[s]=0,vis[s]=1;
while(!q.empty()){
int now=q.front(); q.pop(),vis[now]=0;
for(auto i:G1[now]){
if(dis1[i.v]>dis1[now]+i.w){
dis1[i.v]=dis1[now]+i.w;
cnt[i.v]=cnt[now]+1;
if(cnt[i.v]>=n) return 1;
if(!vis[i.v]) q.push(i.v),vis[i.v]=1;
}
}
}
return 0;
}
bool spfan(int s){
memset(disn,0x3f,sizeof(disn));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int> q;
q.push(s),disn[s]=0,vis[s]=1;
while(!q.empty()){
int now=q.front(); q.pop(),vis[now]=0;
for(auto i:G1[now]){
if(disn[i.v]>disn[now]+i.w){
disn[i.v]=disn[now]+i.w;
cnt[i.v]=cnt[now]+1;
if(cnt[i.v]>=n) return 1;
if(!vis[i.v]) q.push(i.v),vis[i.v]=1;
}
}
}
return 0;
}
void sol(){
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
G1[u].push_back({v,-w});
}
if(spfa1(1)||spfan(n)) cout<<"Forever love";
else cout<<min(disn[1],dis1[n]);
}
signed main(){
sol();
return 0;
}
T3
非常 amazing 的题。
因为判负环这种判定型算法常与二分结合，
所以考虑二分最小平均值 \(mid\)，令答案为 \(ans\)。
显然一个环的平均值为 \(\dfrac{\sum w_i}{cnt}\)（\(w_i\) 为边权，\(cnt\) 为边数），
则有
\[ans-\dfrac{\sum w_i}{cnt} \le 0 \]\[\dfrac{cnt \times ans}{cnt}-\dfrac{\sum w_i}{cnt} \le 0 \]\[\dfrac{\sum (ans-w_i)}{cnt} \le 0 \]\[\sum (ans-w_i) \le 0 \]\[\sum (mid-w_i) \ge 0 \]\[\sum (w_i-mid) \le 0 \]然后我们发现这玩意就是
边权为 \(w_i-mid\) 时的负环边权之和，
我们要尽量要将这玩意等于 \(ans\)，
于是实数二分 \(mid\)，
再重建图，边权为 \(w_i-mid\)，
然后 check 里套个 SPFA 判负环，
若有负环则猜小，否则猜大即可。
代码虽然不长但有点难写，注意细节部分。
#include<bits/stdc++.h>
using namespace std;
const int N=55,M=1e5+5;
int t,n,m,id;
struct Edge{ int v; double w; };
vector<Edge> G[M];
struct E{ int u,v; double w; }e[M];
double dis[N];
int cnt[N];
bool vis[N];
bool spfa(double x){
memset(cnt,0,sizeof(cnt));
queue<int> q;
for(int i=1;i<=n;i++)
dis[i]=0,q.push(i),vis[i]=1;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=m;i++)
G[e[i].u].push_back({e[i].v,e[i].w-x});
while(!q.empty()){
int now=q.front(); q.pop(),vis[now]=0;
for(auto i:G[now]){
if(dis[i.v]>dis[now]+i.w){
dis[i.v]=dis[now]+i.w;
cnt[i.v]=cnt[now]+1;
if(cnt[i.v]>n-1) return 1;
if(!vis[i.v]) q.push(i.v),vis[i.v]=1;
}
}
}
return 0;
}
void sol(){
cin>>n>>m,++id;
double l=1e9,r=-1e9,t;
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w,
l=min(l,(double)e[i].w),r=max(r,(double)e[i].w);
l--,r++,t=r;
while(l+1e-3<r){
double mid=(l+r)/2.0;
if(spfa(mid)) r=mid;
else l=mid;
}
if(t==r) cout<<"Case #"<<id<<": No cycle found.\n";
else cout<<"Case #"<<id<<": "<<setprecision(2)<<fixed<<r<<'\n';
}
int main(){
cin>>t;
while(t--) sol();
return 0;
}
T4
和上题一样的套路。这里仅展示推式子过程。
\[ans-\dfrac{\sum F_i}{\sum T_i} \le 0 \]\[\dfrac{\sum T_i \times ans}{\sum T_i}-\dfrac{\sum F_i}{\sum T_i} \le 0 \]\[\dfrac{\sum(T_i \times ans-F_i)}{\sum T_i} \le 0 \]\[\sum(T_i \times ans-F_i) \le 0 \]\[\sum(T_i \times mid-F_i) \ge 0 \]\[\sum(F_i-T_i \times mid) \le 0 \]然后接下来的大家都会了哈。
注意这里找到负环是猜大，没找到是猜小。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=5e3+5;
int t,n,m,id;
int v[N];
struct Edge{ int v; double w; };
vector<Edge> G[M];
struct E{ int u,v; double w; }e[M];
double dis[N];
int cnt[N];
bool vis[N];
bool spfa(double x){
memset(cnt,0,sizeof(cnt));
queue<int> q;
for(int i=1;i<=n;i++)
dis[i]=0,q.push(i),vis[i]=1;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=m;i++)
G[e[i].u].push_back({e[i].v,e[i].w*x-v[e[i].v]});
while(!q.empty()){
int now=q.front(); q.pop(),vis[now]=0;
for(auto i:G[now]){
if(dis[i.v]>dis[now]+i.w){
dis[i.v]=dis[now]+i.w;
cnt[i.v]=cnt[now]+1;
if(cnt[i.v]>n-1) return 1;
if(!vis[i.v]) q.push(i.v),vis[i.v]=1;
}
}
}
return 0;
}
void sol(){
cin>>n>>m,++id;
double l=1e9,r=-1e9,t;
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w,
l=min(l,(double)e[i].w),r=max(r,(double)e[i].w);
l--,r++,t=l;
while(l+1e-3<r){
double mid=(l+r)/2.0;
if(spfa(mid)) l=mid;
else r=mid;
}
cout<<setprecision(2)<<fixed<<l;
}
int main(){
sol();
return 0;
}