题意：给你\(n\)段铁轨，每段铁轨要求进入时速度不大于\(s_i\)，并且离开时速度恰好为\(t_i\)，你每次可以花费\(1\)的代价将某一铁轨的离开速度减少\(1\)，最后你要把铁轨按某一顺序连接在一起并且满足上面的约束，问花费的最小代价。
将速度离散化，强制每个铁轨的进入速度为\(s_i\)，那么每条铁轨就相当于从\(s_i\)到\(t_i\)连一条边，并且可以任意从\(i\)到\(i+1\)连边来加速，花费\(1\)的代价从\(i+1\)向\(i\)连边来减速。那么问题转化为在这张图中找出一条从最小速度（可任意加速到起点）到最大速度（可由终点任意加速达到）的欧拉路径。
将所有题目给定的边连接后，按速度从小到大判断每个点的入度和出度是否相等。如果入度大于出度，那么需要从该点向下一个点连\(入度-出度\)条边，否则从下一个点向这个点连\(出度-入度\)条边，并计算相应的代价。当然，最小速度和最大速度要特殊处理。那么这时图就满足了欧拉路径的度数要求，但可能存在若干个连通块。
这时在添加一些边使得它们连通即可。即求一棵最小生成树。
|
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 |
#include "railroad.h" #include <bits/stdc++.h> using namespace std; typedef long long lol; const int MAXN=400010; const int INF=1e9; int ut,u[MAXN],f[MAXN],d[MAXN]; int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];} struct edge{ int u,v,w; bool operator <(const edge b) const{return w<b.w;} }e[MAXN]; lol plan_roller_coaster(vector<int> s,vector<int> t){ int n=s.size(); for(int i=0;i<n;i++)u[ut++]=s[i],u[ut++]=t[i]; sort(u,u+ut); ut=unique(u,u+ut)-u; for(int i=0;i<ut;i++)f[i]=i; for(int i=0;i<n;i++){ s[i]=lower_bound(u,u+ut,s[i])-u; t[i]=lower_bound(u,u+ut,t[i])-u; d[s[i]]--;d[t[i]]++; int fa=gf(s[i]),fb=gf(t[i]); if(fa!=fb)f[fa]=fb; } int m=0;d[0]++; lol ans=0; for(int i=0;i<ut-1;i++) if(!d[i])e[m++]=(edge){i,i+1,u[i+1]-u[i]}; else{ int fa=gf(i),fb=gf(i+1); if(fa!=fb)f[fa]=fb; if(d[i]<0)ans+=1ll*(u[i+1]-u[i])*-d[i]; d[i+1]+=d[i]; } sort(e,e+m); for(int i=0;i<m;i++){ int fa=gf(e[i].u),fb=gf(e[i].v); if(fa==fb)continue; f[fa]=fb; ans+=e[i].w; } return ans; } |