隐藏
「bsoj5046」怎样打好隔膜 - 欧拉图+后悔类贪心 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj5046」怎样打好隔膜 - 欧拉图+后悔类贪心

题目大意

有$n$个星球排成一列,第$i$个星球和第$i$+$1$个星球存在一条耗时为$1$的航线。同时还存在$m$扇传送门,一扇由$i$到$j$的传送门可以瞬间将抖儿从第$i$个星球传送到第$j$个星球或从第$j$个星球传送到第$i$个星球,但是传送完毕后传送门会消失。此外,抖儿目前的资源可以额外建造不多于$p$扇传送门。
抖儿可以从任意一个星球出发,经过所有的航线(可经过多次)和传送门,然后在任意一个星球结束。抖儿自然希望能在尽量短的时间内完成任务,请你帮忙计算答案。


题目吐槽

暴力膜蛤不可取,膜蛤不当必被续。


题目分析

我们发现这道题要求经过所有的边,除了每条边可以多次经过外这个问题完全等价于欧拉通路的长度
因为这道题每条边可以多次经过,因此我们需要进行转化。
显然不能将边拆成多条,肯定会超时。

题目$n\le10^9$,而$m\le10^5$,因此我们应该对$m$条边,或对这些边连接的点进行处理。
判定是否是一个无向图存在欧拉通路的方法是图中存在$0$个或$2$个奇数结点的点。

因为这个图非常特殊,是在一条单链上添加一些边,因此不难想到除了必须经过的边 相当于在给一些点添加度数。

那么题目就变成了给定一个图,给奇点增加度数,给一对奇点增加度数的代价为它们的距离,求使图存在欧拉通路的最小代价。
在原图中,$1$和$n$原先是奇点,其余的点为偶点。一个传送门会使连接的点性质发生变化,即奇点变偶点,偶点变奇点。

因为这是一条单链,故删除一堆奇点$(i,j)$的代价是$j-i$,如果一对一对地删除奇点,显然删除相邻的两个奇点是最优的。

当然我们不能将一个奇点删除两遍,也就是说在删除奇点$(i,j)$的所有二元组中,每个奇点不会出现两遍。

那么问题转化为了:
给出$n$个数,每个数权值为$a[i]$,要求选出$k$个数两两不相邻使得代价和最小。

其中的$n$是二元组的个数,即奇点个数$cnt-1$,$a[i]$为二元组的删除代价,$k$为$\frac{cnt-2}{2}-p$,即需要删除的二元组个数减去题目给的免费删除次数。

我们可以使用动态规划来解决这个问题,但显然是会超时的。
我们可以使用bzoj 2151 种树的一种贪心思想来解决这个题。(实际上此时与种树已经基本一样了,只是最大变成了最小)

于是这道题就解决了。


题目总结

该题目转化非常巧妙,但是突破口是想到判定欧拉通路。
而判定欧拉通路的思路来源就是:抖儿可以从任意一个星球出发,经过所有的航线(可经过多次)和传送门,然后在任意一个星球结束。


代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,m,p,P[2*maxn],v[2*maxn],Left[2*maxn],Right[2*maxn],Del[2*maxn],cnt=0;
long long ans=0;
map<int,int>Degree;
struct QueNode {
int pos,v;
bool operator < (const QueNode& b) const {
return v>b.v;
}
};
priority_queue<QueNode>Q;
int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
Degree[x]^=1;
Degree[y]^=1;
}
Degree[1]^=1;
Degree[n]^=1;
for(auto& x:Degree)
if(x.second)P[++cnt]=x.first;
for(int i=1; i<cnt; i++) {
v[i]=P[i+1]-P[i];
Q.push((QueNode) {
i,v[i]
});
Left[i]=i-1;
Right[i]=i+1;
}
Left[1]=Right[cnt-1]=0;
v[0]=0x7fffffff/2;
for(int i=1; i<=cnt/2-p-1; i++) {
QueNode Now;
while(!Q.empty()) {
Now=Q.top();
if(!Del[Now.pos])break;
Q.pop();
}
int l=Left[Now.pos],r=Right[Now.pos];
ans+=Now.v;
Q.pop();
v[Now.pos]=v[l]+v[r]-Now.v;
Q.push((QueNode) {
Now.pos,v[Now.pos]
});
Del[l]=Del[r]=1;
Left[Now.pos]=Left[l];
Right[Now.pos]=Right[r];
if(Right[Now.pos])Left[Right[Now.pos]]=Now.pos;
if(Left[Now.pos])Right[Left[Now.pos]]=Now.pos;
}
printf("%lld\n",ans+n-1);
return 0;
}
姥爷们赏瓶冰阔落吧~