ICPC Northwestern European Regional Programming Contest (NWERC 2018)

ICPC Northwestern European Regional Programming Contest (NWERC 2018)

九月 05, 2020

B - Brexit Negotiations

题意

有n<4e5个会议 每个会议需要开mint[i]分钟

开这个会议前需要指定几个其他的会议正在进行或已经结束

即想要取某个点需要先获得它的前继点

其次开始某个会议一分钟之后才能开始下一个会议

问开完所有会议最短需要多久

题解

参考题解

参考题解

根据依赖关系，建立DAG。首先想到拓扑排序，由于题目要开完所有会议时间最短

于是当有多个会议满足前驱条件 (它指定的几个会议正在进行或已经结束)

则选择时间最长的会议先进行

过一分钟之后在选择其他会议 直觉上这样贪心

但正向贪心存在漏洞:

比如 (数字表示时间)

5->1

2->9

选择5 过一分种后选 2 再过一分钟后选9 最后选1

则总时长为11;

但实际上最优选择是先选择2 过一分钟再选择9 过一分钟再选择5 过一分钟再选择1

所以正向贪心不一定正确

考虑反向建边(从后往前考虑) 进行拓扑排序将入度为0的点(最后开的会议)压入优先队列

优先队列以会议时间短的优先级高

于是对于上个样例

5->1

2->9

先拿出1放在最后 往前推1分钟 取出5 往前推1分钟 取出9 前推一分钟取出2

反向建图实际上是假设 上一级子问题已经取得最优解的状态下

讨论最后放时长最短的会议，对于上一级子问题以此类推

而正向建图 讨论当前状态下取出最优的点需要dfs到最后 判断选择哪个点

而不是直接根据贪心当前能取的点中时间最长的会议

所以正向建图贪心需要正向搜素反向回溯 于是干脆选择反向建边拓扑排序贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=4e5+5;
const double Pi=acos(-1);
/*
*/
ll mint[Max];
bool vis[Max];
int in[Max];
vector<int>mp[Max];

int main(){
    Turnoff;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>mint[i];
        int need;cin>>need;
        while(need--){
            int u,v=i;cin>>u;
            mp[v].push_back(u);
            in[u]++;
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    for(int i=1;i<=n;i++){
        if(in[i])continue;
        q.push({mint[i],i});
    }
    int cnt=n-1,maxn=0;
    ///对于最后1个会议前面n-1个会议不间断进行则需要n-1分钟
    while(!q.empty()){
        pair<int,int> now=q.top();q.pop();
        maxn=max(maxn,cnt+now.first);
        for(auto i:mp[now.second]){
            in[i]--;
            if(in[i])continue;
            q.push({mint[i],i});
        }
        cnt--;
        ///对于最后第k个会议 前面n-k个会议不间断进行则需要n-k分钟
        ///下次循环解决上一级子问题
    }
    cout<<maxn<<endl;
}