【IOI2016】过山车铁路 – 徐亦轲的博客

题意：给你\(n\)段铁轨，每段铁轨要求进入时速度不大于\(s_i\)，并且离开时速度恰好为\(t_i\)，你每次可以花费\(1\)的代价将某一铁轨的离开速度减少\(1\)，最后你要把铁轨按某一顺序连接在一起并且满足上面的约束，问花费的最小代价。

将速度离散化，强制每个铁轨的进入速度为\(s_i\)，那么每条铁轨就相当于从\(s_i\)到\(t_i\)连一条边，并且可以任意从\(i\)到\(i+1\)连边来加速，花费\(1\)的代价从\(i+1\)向\(i\)连边来减速。那么问题转化为在这张图中找出一条从最小速度（可任意加速到起点）到最大速度（可由终点任意加速达到）的欧拉路径。

将所有题目给定的边连接后，按速度从小到大判断每个点的入度和出度是否相等。如果入度大于出度，那么需要从该点向下一个点连\(入度-出度\)条边，否则从下一个点向这个点连\(出度-入度\)条边，并计算相应的代价。当然，最小速度和最大速度要特殊处理。那么这时图就满足了欧拉路径的度数要求，但可能存在若干个连通块。

这时在添加一些边使得它们连通即可。即求一棵最小生成树。

#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;
}

#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;

}

说点什么