CF1369E DeadLee

发表于 | 阅读数

对于一个朋友

  • $a_i,b_i$都有，都吃
  • $a_i,b_i$只有一个，吃一个
  • $a_i,b_i$没有，吃XX

安排顺序使得存活。

显然正向很难推出来。
首先我们需要找到够吃，然后倒推回去，如果够吃，那么另一个就可以不吃，为$need[dui[i]]—$

如果$need[x]=w[x]$，说明这个也够吃，然后套娃即可。

显然如果所有元素进了队列，表示存活，反之，无法存活。

代码 
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
vector<pii> g[N];
int w[N], x[N], y[N];
int p[N], d[N], v[N], vis[N];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
        w[i] = read();
    for (int i = 1; i <= m; i++)
    {
        x[i] = read(), y[i] = read();
        d[x[i]]++;
        d[y[i]]++;
        g[x[i]].push_back(mk(y[i], i));
        g[y[i]].push_back(mk(x[i], i));
    }
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (d[i] <= w[i])
            q.push(i), d[i]--;
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (pii now : g[u])
        {
            if (vis[now.second] == 1)
                continue;
            d[now.first]--;
            ans.push_back(now.second);
            vis[now.second] = 1;
            if (d[now.first] == w[now.first])
                q.push(now.first);
        }
    }

    if (ans.size() != m)
        puts("DEAD"), exit(0);
    puts("ALIVE");
    reverse(ans.begin(), ans.end());
    for (int k : ans)
        printf("%d ", k);
}