Thallium54

题解 Codeforces 1369E - DeadLee

BFS 贪心 题解

贪就完事了

题解 #

首先先算出sis_i：喜欢食物ii的人的个数。对于食物ii，如果si≤wis_i\leq w_i，我们可以看出这些人无论你以什么顺序叫他们都有食物吃。所以我们尽可能的晚叫他们。

整个过程有点像拓扑排序或者说是 BFS：从所有满足si≤wis_i\leq w_i的点开始，当访问新的点 u 时，sus_u减 1，如果su≤wus_u\leq w_u的话，就把 u 加进队列并把 u 加到叫人的名单里。最后反转名单就得到答案了。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define pb push_back
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int> a(n),deg(n);
    for(auto& i:a) cin>>i;
    vector<vector<pii>> G(n);
    forn(i,m){
        int x,y;
        cin>>x>>y;
        x--,y--;
        deg[x]++,deg[y]++;
        G[x].pb({y,i});
        G[y].pb({x,i});
    }
    vector<int> ans;
    vector<int> vis(m);
    queue<int> q;
    forn(i,n){
        if(deg[i]<=a[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto [to,i]:G[u]){
            if(!vis[i]){
                ans.pb(i+1);
                vis[i]=1;
                deg[to]--;
                if(deg[to]<=a[to]) q.push(to);
            }
        }
    }
    if(sz(ans)!=m) return cout<<"DEAD",0;
    reverse(all(ans));
    cout<<"ALIVE\n";
    for(auto it:ans) cout<<it<<' ';
    return 0;
}