#P13078. [NOISG 2019] Rigged Roads
[NOISG 2019] Rigged Roads
题目背景
Silvermill 最近财政紧张,市长 Peanut 打算拆除部分道路以节省养护成本。
题目描述
Silvermill 可以看作一个城市,包含 个道路交汇点和 条道路,第 条道路连接交汇点 和 。交汇点编号为 到 ,道路编号为 到 。保证任意两个交汇点之间总可以直接或间接到达,且没有两条道路连接同一对交汇点。
为了方便决策,Peanut 请你帮忙评估各条道路的养护成本。你的任务是:
你需要给出一个长度为 的排列 ,表示第 条道路的养护成本为 ,其中 是 到 的一个排列。
Peanut 会根据你提供的养护成本,保留一组道路,满足:
- 所有交汇点仍然连通;
- 保留道路的养护成本之和最小。
即,Peanut 实际上会选择最小生成树,且由于所有成本互不相同,最小生成树唯一。
但你另有所图。你想让最终被保留的道路集合恰好是你指定的一组道路 ,且 恰好构成一棵生成树。通过合理选择 ,你可以让 恰好成为最小生成树。
请你计算,满足上述条件的字典序最小的排列 。
给定城市结构和你想保留的道路集合 ,请输出字典序最小的养护成本分配方案 ,使得 成为唯一的最小生成树。
注:若存在第 使得 ,且 ,则 的字典序小于 。
输入格式
第一行包含两个整数 和 。
接下来 行,每行两个整数 和 ,表示第 条道路连接的两个交汇点。
最后一行包含 个整数,表示你想保留的道路编号,构成的集合 。
输出格式
输出 个整数,表示字典序最小的排列 ,第 个数是第 条道路的养护成本。
4 5
3 4
1 2
2 3
1 3
1 4
2 4 5
3 4 5 1 2
4 4
1 2
1 4
2 3
3 4
1 3 4
1 4 2 3
提示
【数据范围】
- 仅使用 中的道路也能保证所有交汇点连通。
子任务编号 | 分值 | 额外限制 |
---|---|---|
,即 构成一棵星形树 | ||
,即 构成一条链 | ||
无额外限制 |