CF242D Dispute 题解

发布于 2020-08-18  688 次阅读


题意

有 $n$ 个计数器和 $m$ 条电线,每个计数器都对应着一个额定值 $a_i$ ,初始时所有计数器的值均为 $0$ ,现在你可以按若干个计数器上的按钮,每次按按钮可以使该计数器以及与该计数器通过电线相连的计数器的值都 $+1$ ,每个计数器最多只能按一次。当你进行这样的操作若干次后,若有一个计数器上的值与该计数器的额定值一样,你就失败了。需要输出任意一种方案使你可以获胜。若无法获胜,输出 $-1$。

解析

当你得知该题的解法之后会恍然大悟——原来这么朴素!

我们用一个数组 $b$ 存储计数器当前的值,只需要寻找当前存不存在 $b_i=a_i$ 的情况,若存在,按按钮 $i$ 即可。

而这显然可以由队列实现。

正确性证明:

初始时所有按钮都没有被按过,当出现 $b_i=a_i$ 的情况时,我们按下按钮 $i$ 后,按钮 $i$ 的 $b_i$ 就大于 $a_i$ 了,而由于后续的操作只能使 $b_i$ 增大,所以 $b_i$ 不可能再一次等于 $a_i$ ,因此我们保证了任何按钮最多只按下一次。也由此可知,一定有一种方案可以获胜,不必考虑 $-1$ 的情况(根本不存在无法获胜的情况)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N],head[N],cnt;
int ans[N],tot;
struct edge{
    int to,next;
}e[N<<1];
inline void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
queue<int> q;
inline void work(){
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ans[++tot]=u;
        b[u]++;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            b[v]++;
            if(b[v]==a[v]){
                q.push(v);
            }
        }
    }
}
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    } 
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!a[i]) q.push(i);
    }
    work();
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣