题解：P15628 [ICPC 2022 Jakarta R] Game Show

linmoxy · 2026-03-05 23:22:45 · 题解

可以将本题中的这个环抽象成一个图，如下图。

然后发现，如果最短路走了同一条边两次及以上，那么路径一定形成了一个环，而且既然走这个环比不走这个环更短，那说明这个环是一个负环，并且由于这张图强连通，所以无论起点和终点如何变动，都可以一直重复走这个负环使这个值无限小，因此先判断否有负环，如果有的话每次询问都输出 flawed 就可以了。

如果没有负环，那么只有正着走（走红色的路）和反着走（走蓝色的路）两种可能，用前缀和处理即可。

我开始考虑用 SPFA 判断负环，但第十四个点会超时。

发现图中只有可能有两种环，一种是绕一个方向转一整圈（如左下图），另一种是先绕一个方向走一段距离，再绕另一个方向走回来（如右下图）。

对于第一种情况，只需要求出所有正方向的边长和和所有反方向的边长和即可。

对于第二种情况，假设是从点 l 顺时针绕到点 r，再从点 r 绕回来，那不难发现这段路程的路程和为 a[l]+b[l]+a[l+1]+b[l+1]+...+a[r-1]+b[r-1] 如果这个值为负数，那么对于从 l 到 r-1 的这些数字，必定会有一个数字（假设是 i）满足 a[i]+b[i]<0，同时如果有一个 i 满足 a[i]+b[i]<0，那么绕这两段路也能凑成一个负环，因此特判这两种情况即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],b[N],vis[N],cnt[N],qzha[N],qzhb[N];
vector<int>v[N],c[N];
int n,T,flag;
signed main(){
    cin>>n>>T;
    int cnta=0,cntb=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnta+=a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(a[i]+b[i]<0)flag=1;
        cntb+=b[i];
    }
    if(cnta<0||cntb<0)flag=1;
    for(int i=1;i<=n;i++){
        qzha[i]=qzha[i-1]+a[i];
    }
    for(int i=n;i>=1;i--){
        qzhb[i]=qzhb[i+1]+b[i];
    }
    while(T--){
        int l,r;
        cin>>l>>r;
        if(flag){
            cout<<"flawed"<<endl;
        }
        else if(l==r){
            cout<<0<<endl;
        }
        else if(l<r){
            cout<<min(qzha[r-1]-qzha[l-1],qzhb[r]+qzhb[1]-qzhb[l])<<endl;
        }
        else{
            cout<<min(qzhb[r]-qzhb[l],qzha[r-1]+qzha[n]-qzha[l-1])<<endl;
        }
    }
}