BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序贪心)

题意

Sol

非常妙的一道题。

首先不难想到拓扑排序，但是直接对原图按\(k\)从小到大拓扑排序是错的。因为当前的\(k\)大并不意味着后面的点\(k\)也大

但是在反图上按\(k\)从大到小拓扑排序就是对的。为什么呢？因为题目中给出的条件是下限，而在反图上拓扑排序就相当于卡着下限做，因此一定是最优的

对于第二问，同样在反图上搞。对每个点分开做，贪心的策略是：如果有其他的飞机可以起飞则让他们起飞，直到没有飞机可以起飞，这时的时间就是答案

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

using namespace std;

const int MAXN = 2e5 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, M, a[MAXN], inder[MAXN], tmp[MAXN], ans[MAXN];

vector<int> v[MAXN];

void Topsort() {

    priority_queue<Pair> q;

    for(int i = 1; i <= N; i++)

        if(!inder[i]) q.push(MP(a[i], i));

    int tot = 0;

    while(!q.empty()) {

        int p = q.top().se; q.pop(); ans[++tot] = p;

        for(int i = 0, to; i < v[p].size(); i++) {

            to = v[p][i];

            inder[to]--;

            if(!inder[to]) q.push(MP(a[to], to));

        }

    }

    for(int i = tot; i >= 1; i--) printf("%d ", ans[i]); puts("");

}

int solve(int x) {

    memcpy(inder, tmp, sizeof(tmp));

    priority_queue<Pair> q;

    inder[x] = N;

    for(int i = 1; i <= N; i++) if(!inder[i]) q.push(MP(a[i], i));

    int tim = N;

    for(int i = N; i; i--) {

    	if(q.empty() || (q.top().fi < i)) return i;

        int p = q.top().se; q.pop();

        for(int i = 0, to; i < v[p].size(); i++) {

            to = v[p][i];

            inder[to]--;

            if(!inder[to]) q.push(MP(a[to], to));

        }

    }

    return tim;

}

int main() {

    N = read(); M = read();

    for(int i = 1; i <= N; i++) a[i] = read();

    for(int i = 1; i <= M; i++) {

        int x = read(), y = read();

        v[y].push_back(x); inder[x]++; tmp[x]++;

    }

    Topsort();

    for(int i = 1; i <= N; i++) printf("%d ", solve(i));

    return 0;

}

/*

10 10

4 4 3 6 9 9 10 7 10 7

2 9

3 5

6 7

1 5

7 9

10 2

3 8

8 6

3 10

8 5

*/

巴特西

BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序贪心)

题意

Sol

最新文章

热门文章

巴特西

BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

题意

Sol

最新文章

热门文章

BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序贪心)