OI题解 - 卡片占卜(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 卡片占卜(LOJ)

发表于 分类于 Valine：

区间反转问题转换成最短路我还是第一次见……

# 题面

> LOJ 2997

# 解析

我们的最终目标是要对两个区间进行反转。

png1

非常显然上面这些操作就是把蓝色区间给反转过来。

看起来像什么？一张图？

  1. 对于每个位置建点；
  2. 对于一个可反转的区间 $[l,r]$，在 $l$ 和 $r+1$ 之间连长度为 $r-l+1$ 的边；

这样建出图过后，如果要反转区间 $[L,R]$，则从 $L$ 到 $R+1$ 跑一个最短路就可以了。

假设我们要反转的区间是 $[L_1,R_1],[L_2,R_2]$（根据题意显然不相交，且假设 $R_1<L_2$）

那么怎样反转区间是可以的？

  1. 反转 $[L_1,R_1],[L_2,R_2]$；
  2. 反转 $[L_1,R_2],[R_1+1,L_2-1]$；
  3. 反转 $[L_1,L_2-1],[R_1+1,R_2]$；

三种情况分别计算花费取min 即可。

# 源代码

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll INF=(1ll<<59);
const int N=5e5+10,M=1e5+10;

int A,B,C,D,E,n;
ll dis[N];
int po[6];
bool fix[N];

struct GRAPH{
    int head[N],nxt[M<<1],to[M<<1],cst[M<<1],ncnt;
    void AddEdge(const int &u,const int &v,const int &c){
        int p=++ncnt,q=++ncnt;
        nxt[p]=head[u],to[p]=v,cst[p]=c,head[u]=p;
        nxt[q]=head[v],to[q]=u,cst[q]=c,head[v]=q;
    }
    int operator [](const int &id){return head[id];}
};
GRAPH Gr;

inline int Ri(){
    register int a=0,b=1,c=getchar();
    while(c<'0' || '9'<c) b=(c=='-'? -1:b),c=getchar();
    while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
    return a*b;
}
typedef pair<ll,int> DATA;
ll Dijkstra(int S,int T){
    for(int i=1;i<=po[5]+1;i++) dis[i]=INF,fix[i]=false;
    static priority_queue< DATA,vector<DATA>,greater<DATA> > que;
    que.push(make_pair(dis[S]=0,S));
    while(!que.empty()){
        int u=que.top().second;que.pop();
        if(fix[u]) continue;
        fix[u]=true;
        for(int it=Gr[u];it;it=Gr.nxt[it]){
            int v=Gr.to[it];
            if(fix[v] || dis[v]<=dis[u]+Gr.cst[it]) continue;
            dis[v]=dis[u]+Gr.cst[it];
            que.push(make_pair(dis[v],v));
        }
    }
    return dis[T];
}
int main(){
    for(int i=1;i<=5;i++) po[i]=po[i-1]+Ri();
    n=Ri();
    for(int i=1;i<=n;i++){
        int le=Ri(),ri=Ri()+1;
        Gr.AddEdge(le,ri,ri-le);
    }
    ll ans=INF;
    //A1-A2 B1-B2
    ans=min(ans,Dijkstra(po[1]+1,po[2]+1)+Dijkstra(po[3]+1,po[4]+1));
    //A1-B2 A2-B1
    ans=min(ans,Dijkstra(po[1]+1,po[4]+1)+Dijkstra(po[3]+1,po[2]+1));
    //A1-B1 A2-B2
    ans=min(ans,Dijkstra(po[1]+1,po[3]+1)+Dijkstra(po[2]+1,po[4]+1));
    if(ans==INF) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

THE END

Thanks for reading!