题解：CF1369E DeadLee

endswitch · 2025-04-05 11:05:52 · 题解

考察要点：

• 图论建模。
• 无向图拓扑排序。

首先分析得到，一个菜品无论怎么选的个数都不会低于 0，那么喜欢这个菜品的人一定可以选这个菜使得策略最优。

于是我们将这个菜品和这些人删去，迭代解决这个问题即可。

一个人有且仅有两个喜欢的菜品，那么我们将菜品看作点，将人看作边，对于上述过程，用拓扑排序刻画即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int N = 2e5 + 5;
int n, m, u[N], v[N], deg[N];
bool is[N], vis[N];
queue<int> q;
stack<int> ans;
vector<pair<int, int> > g[N];

inline void toposort() {
    for(int i = 1 ; i <= n ; ++ i)
        if(deg[i] >= 0) q.push(i);

    while(! q.empty()) {
        int u = q.front();

        q.pop();

        for(auto [v, i] : g[u])
            if(! vis[i]) {
                ans.push(i);
                vis[i] = true;
                ++ deg[v];

                if(deg[v] == 0) q.push(v);
            }

    }
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++ i)
        cin >> deg[i];
    for(int i = 1 ; i <= m ; ++ i) {
        cin >> u[i] >> v[i];

        g[u[i]].pb({v[i], i}), g[v[i]].pb({u[i], i});

        -- deg[u[i]], -- deg[v[i]];
    }

    toposort();

    cerr << ans.size() << '\n';

    if((int)ans.size() < m) cout << "DEAD";
    else {
        cout << "ALIVE\n";

        while(! ans.empty()) {
            cout << ans.top() << ' ';

            ans.pop();
        }
    }

    return 0;
}