文章

5

粉丝

176

获赞

6

访问

25.6k

头像
简单排序
P1451 中国科学技术大学机试题
发布于2022年9月28日 10:48
阅读数 7.7k

初看以为是拓扑排序,仔细读题后发现是个排序题

入度为0的结点一定是第一个执行的任务,每次会释放出要出的点所连的边

因此可以考虑用一个小根堆维护将要执行的任务,将堆顶弹出并将所连的边入堆

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define x first
#define y second
#define all(x) x.begin(),x.end();

using namespace std;

typedef pair<int,int> PII;

inline int read(){
    char ch = getchar();
    int x = 0;
    int f = 1;
    while(ch > '9' || ch < '0'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void w...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发