「Codeforces 242D」Dispute

发表于 | | 阅读次数:
字数统计: 514 字

Description

题目链接：Codeforces 242D

Valera 有 $n$ 个计数器标号为 $1$ 到 $n$。他们之间通过 $m$ 条电路连接。每个计数器都有一个按钮。

起初，每个计数器的值都是 $0$。当你按下某个计数器上的按钮后，这个计数器和与他相连的计数器的值都会增加 $1$。

Valera 和 Ignat 之间在玩一个游戏，Ignat 想了一个长度为 $n$ 的序列 $a_i$。Valera 需要选择一些不同的计数器并按下他们的按钮刚好各 $1$ 次（其他的按钮不能按）。如果整个操作之后，存在一个 $i$ 使得计数器 $i$ 上的值等于 $a_i$，那么 Valera 将会输掉游戏，否则他会获胜。

请你帮助 Valera 选择一些计数器使得他能够获胜，如果无法获胜则输出 $-1$。

数据范围：$1\le n,m\le 10^5$，$0\le a_i\le 10^5$

Solution

我们记录每个点当前按下的次数 $b_i$。每次操作时，找到满足 $a_i=b_i$ 的 $i$ 并按下，显然这样可以使得 $b_i\neq a_i$。这个过程可以使用 $\text{BFS}$ 来实现，具体过程详见代码。

通过这个算法，对于任何的序列 $a_i$ 显然都是有解的，因此不可能输出 $-1$。

时间复杂度：$O(n+m)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <cstdio>
#include <queue>

const int N=1e5+5,M=2e5+5;
int n,m,tot,a[N],b[N],lnk[N],ter[M],nxt[M],ans[N];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
int main() {
    scanf("%d%d",&n,&m);
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    std::queue<int> q;
    for(int i=1;i<=n;++i) if(!a[i]) q.push(i);
    int tot=0;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        ++b[u],ans[++tot]=u;
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(++b[v]==a[v]) q.push(v);
        }
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i) printf("%d%c",ans[i]," \n"[i==tot]);
    return 0;
}
0%