AtCoder Beginner Contest 267 E Erasing Vertices 2

Erasing Vertices 2

二分 || 贪心

二分的做法就二分答案，然后检查一下能否删除，像拓扑一下跑一下就行

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll val[maxn], num[maxn], tot[maxn];
vector<int>gra[maxn];

bool check(int n, ll x)
{
    queue<int>q;
    for(int i=1; i<=n; i++) val[i] = tot[i];
    for(int i=1; i<=n; i++)
    {
        if(val[i] <= x)
        {
            val[i] = -1;
            q.push(i);
        }
    }
    int cnt = 0;
    while(q.size())
    {
        int now = q.front();
        q.pop();
        cnt++;
        for(int nex : gra[now])
        {
            val[nex] -= num[now];
            if(val[nex] >= 0 && val[nex] <= x)
            {
                val[nex] = -1;
                q.push(nex);
            }
        }
    }
    return cnt == n;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> num[i];
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
        gra[b].push_back(a);
        tot[a] += num[b];
        tot[b] += num[a];
    }
    ll l = 0, r = 0;
    for(int i=1; i<=n; i++) r = max(tot[i], r);
    while(l < r)
    {
        ll mid = l + r >> 1;
        if(check(n, mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

优先队列的做法，就贪心地选取删除点所消耗代价最小的点，选择代价最小的点，并可以松弛其他点的代价

如果不选择最小的点，如果与最小的点相连，则肯定不是最优（当前的点可以被松弛）；如果不与最小的点相连，也不会使得答案变优秀，因为也可以选择代价最小的，然后再来选择这个点

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const ll inf = 0x3fffffffffffffff;
#define pii pair<ll, ll>
vector<int>gra[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<ll>num(n + 1), sum(n + 1, 0);
    for(int i=1; i<=n; i++) cin >> num[i];
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
        gra[b].push_back(a);
        sum[a] += num[b];
        sum[b] += num[a];
    }
    priority_queue<pii, vector<pii>, greater<pii> >q;
    for(int i=1; i<=n; i++) q.push({sum[i], i});
    vector<int>vis(n + 1, 0);
    ll ans = 0;
    while(q.size())
    {
        auto [val, now] = q.top();
        q.pop();
        if(vis[now]) continue;
        vis[now] = 1;
        ans = max(ans, val);
        for(int nex : gra[now])
        {
            sum[nex] -= num[now];
            if(vis[nex] == 0)
                q.push({sum[nex], nex});
        }
    }
    cout << ans << endl;
    return 0;
}