20221114_T4B_拓扑排序贪心

题意

L国正在举行各种会议，但是可怜的是L国只有一个主持人，每场会议的开始主持人都必须去主持会议，使会议得以开始，在会议开始后主持人可以离开。 主持人不会分身，他在一个时刻只能主持一场会议，但是可以忽略主持人在各个会场间移动的时间。每个会议都有一个自己的持续时间，会议之间也有一些形如B必须在A之前的约束关系。但是大家都想早点溜了，他们找到了你，让你安排一种会议举办的方式，使得最晚结束的会议最早。

题解

赛时得分 0/100/100。

这题有点思维。没有代码难度。

首先，我们就是要 t 最大的字典序最小，这样的话肯定更优。所以我们应该能想到贪心的选取 t 大的，那么怎么保证拓扑序呢？

我们建反图，0 向所有点建图，这样的话只有把跟该节点有关的边全部走完我才可以走其他的点。

这正好满足了拓扑序。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 1e5 + 10, inf = 0x3f3f3f3f;

priority_queue<pair<int, int> >Q[N];
vector<int>G[N];
int n, d[N], t[N], T = -1;
bool vis[N];

void dfs(int u) {
    t[u] = ++T;
    vis[u] = 1;
    while(!Q[u].empty()) {
        int v = Q[u].top().second; Q[u].pop();
        // cout << u << ' ' << v << endl;
        if(vis[v]) continue;
        dfs(v);
    }
    // cout << T << endl;
    cout << u << ' ' << t[u] << endl;
}

int main() {
    read(n);
    for(int i = 1; i <= n; ++i) {
        read(d[i]);
        int ti; read(ti);
        if(!ti) Q[0].push(make_pair(d[i], 0));
        // if(!ti) Q[i].push(make_pair(0, 0));
        while(ti--) {
            int p;
            read(p);
            G[i].push_back(p);
        }
    }
    // for(int i = 1; i <= n; ++i) G[0].push_back(i);
    for(int i = 0; i <= n; ++i) 
        for(int v : G[i]) Q[i].push(make_pair(d[v], v));
    dfs(0);
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans = max(ans, d[i] + t[i]);
    cout << ans << endl;
    return 0;
}