题目大意
有$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;
}
|
