题解 CF1373F 【Network Coverage】

Froggy · 2020-06-27 12:05:21 · 题解

赛后一分钟做出来有点崩溃，好在它重测的时候 FST 了。（雾

容易发现，只要确定了 b_1 分给 a_1 多少，那么之后的就可以贪心来搞，\mathcal{O}(n) 即可判断是否可行。

做法 1：

二分这个 “b_1 分给 a_1” 的值，

这里主要讲的不是这个，具体做法就直接推神仙 wyy 的题解了：here。

时间复杂度：\mathcal{O}(n\log a_1)。

做法 2：

网络流。具体做法不再展开。

Q：10^6 拿头过啊？

A：我不清楚但是我同学过了，可能因为图比较特殊吧。（提交记录）

有兴趣可以研究一下。

做法 3：

我具体要讲的做法，并且是线性做法。

换一个思路：

设 b_1 给 a_2 了 x_1，b_2 给 a_3 了 x_2，\cdots，b_n 给 a_1 了 x_n。

这样就可以得到一堆不等式：

\forall i\in [1,n], \begin{cases} x_i\geq 0 \\ x_i\leq b_i \\ x_i+b_{(i\bmod n)+1}-x_{(i\bmod n)+1}\geq a_{(i\bmod n)+1} \end{cases}

愉快地差分约束一波然后建图。

![](https://cdn.luogu.com.cn/upload/image_hosting/bbbg7le7.png) 如果有正环就说明 NO（无解），否则就 YES（有解）。直接跑 SPFA 是 $\mathcal{O}(n^2)$，如果把判定负环所需的入队次数改小（[比如我改成了 $8$](https://codeforces.com/contest/1373/submission/85083539])），然后光荣地 FST 了。（WA on 51，是 hack 数据。）不过应该会发现这个长的像轮胎的图比较特殊，可以 “手动” 判正环。首先判掉外边一圈是正的情况，剩下可能的正环都长这个样子： $S\rightarrow x\rightarrow x\bmod n+1\rightarrow\cdots\rightarrow y\rightarrow S

所以可以维护 a_i-b_i 的前缀和 sum，同时维护 sum+b_i 的最小值 mn。

如果某个位置满足 mn<sum 就说明有正环。

注意由于这是个环，所以要把环拆开然后复制一遍。

时间复杂度：\mathcal{O}(n)。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
#define N 1000010
int n,T,a[N],b[N];
bool Solve(){
    n=read();
    ll sum=0;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=read();
    for(int i=1;i<=n;++i)sum+=a[i]-b[i];
    if(sum>0)return false;
    sum=0;
    ll mn=b[1];
    for(int i=1;i<=(n<<1)+1;++i){
        sum+=a[i%n+1]-b[i%n+1];
        mn=min(mn,b[i%n+1]+sum);
        if(mn<sum)return false;
    }
    return true;
}
int main(){
    T=read();
    while(T--){
        printf(Solve()?"YES\n":"NO\n");
    }
    return 0;
}

Froggy's blog

题解 CF1373F 【Network Coverage】

做法 1：

做法 2：

做法 3：

呱!!