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