[SDOI2009]Elaxia的路线

发表于 | 更新于 | 分类于 | 阅读次数：

看着大佬纠结于题目实现的各种细节，本蒟蒻还在想这题应该怎么实现…

有些知识没有做过类似的题目，你就是真的不知道，顶着头皮硬磕真不一定能在一定时间弄出来。我会将整个题目的思路详细地分析一波，把一些关键的操作举出来。_(:з」∠)_

整个题描述巨短，说白了就是要求无向图中，两对点间最短路的最长公共路径。

首先连初学图论的萌新都知道，一个图中的最短路径不止一条。

  • 所以，“要想找出所有在最短路径上的边”便成为首要的问题。

这个其实想一想还是可以搞出来的，假设两个节点分别为$u,v$且u靠近s，则一条边在最短路径上，一定满足起始$s,t$点分别到$u,v$的距离加上这条边权，等于最小路径长度。即$ds[u]+w+dt[v]=ds[t]$
其中$ds[i]$数组和$dt[i]$数组分别为$s,t$到各个点的路径，这个不难理解（但就是想不到）。

于是乎我们可以先用4个$SPFA$（当然8012年了还是打$dij$更好）算出4个顶点到各个点的最短路，枚举每一条边即可。

  • 但是求出来所有边又要怎么处理呢？？

既然我们要求最短路的最长公共路径，那这条路径由以上求出的边组成的，跟其他边半毛钱关系没有。

为了方便处理，我们可以把这些边重新建个图，或者通过打标记的方法将这些边独立出来，这样在接下来的操作里就会方便许多。

有些细节放在代码里讲：

1
2
3
4
5
6
7
8
9
10
11
   for (int i=1;i<=n;i++)
   for (int j=fir[i];j;j=e[j].next) //枚举每条边
   {
       int v=e[j].v,w=e[j].w;
       if (d1[i]+w+d3[v]==d1[y1])  //判断第一对
       {
      //判断第二对的时候由于枚举的是单向边，所以作双向处理。 
       	if (d2[i]+w+d4[v]==d2[y2]) add2(i,v,w);
       	if (d2[v]+w+d4[i]==d2[y2]) add2(v,i,w);
	}
}

  • 建完图了，怎么求最长路径呢？

既然我们建了一个是一个有向图，不具有后效性，所以可以跑有向图DP了！

设$dp[i]$是第i节点的最长路径，易得到式子$dp[i]=dp[u]+w$其中u是i的前驱节点，对于入度为0的点答案为0，为了方便理解我采用记忆化的方法求解。

由于所有边可能不会全连通，所以枚举每一个没有标记的点均跑一边，最后求出最大的$dp[i]$即是答案。

1
2
3
4
5
6
7
8
9
10
11
int dfs(int u)
{
    if (dp[u]) return dp[u];
    for (int i=fir2[u];i;i=e2[i].next) 
    {
        
        int v=e2[i].v,w=e2[i].w;
        dp[u]=max(dp[u],dfs(v)+w);  //核心，深搜算u前驱的答案。
    }
    return dp[u];
}

于是三个重要操作就没了，其余的细节其他题解也有就不多赘述，具体可看丑陋的代码：

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
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <queue>
#include <climits>
using namespace std;
struct ed{
    int v,next,w;
}e[5000000],e2[5000000];
int st,d1[50000],d2[5000],d3[5000],d4[5000];
int fir[10000],fir1[10000],fir2[20000],dp[10000],maxx;
int n,m,u,v,l,x1,x2,y1,y2,rd[10000];
bool vis[40000]; queue<int> q;

void add(int u,int v,int l)
{
    e[++st].v=v; e[st].next=fir[u]; e[st].w=l; fir[u]=st;
}

void add2(int u,int v,int l)
{
    e2[++st].v=v; e2[st].next=fir2[u];  e2[st].w=l; fir2[u]=st; rd[u]=rd[v]=1;
}

void spfa(int b,int *d)
{
    for (int i=1;i<=n;i++) d[i]=INT_MAX/2; d[b]=0;
    while (!q.empty()) q.pop(); q.push(b);
    memset(vis,0,sizeof(vis)); vis[b]=1;
    while (!q.empty())
    {
        int k=q.front(); q.pop(); vis[k]=0;
        for (int i=fir[k];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w; 
            if (d[v]>d[k]+w) {
                d[v]=d[k]+w; if (!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
}

int dfs(int u)
{
    if (dp[u]) return dp[u];
    for (int i=fir2[u];i;i=e2[i].next) 
    {
        
        int v=e2[i].v,w=e2[i].w;
        dp[u]=max(dp[u],dfs(v)+w);	
    }
    return dp[u];
}

int main()
{
    cin>>n>>m;
    cin>>x1>>y1>>x2>>y2;
    for (int i=1;i<=m;i++) cin>>u>>v>>l,add(u,v,l),add(v,u,l);
    spfa(x1,d1); spfa(x2,d2); spfa(y1,d3); spfa(y2,d4); st=0;//求4个顶点到各个点的最短路 
//~~~~~~~~ 
    for (int i=1;i<=n;i++)
    for (int j=fir[i];j;j=e[j].next)
    {
        int v=e[j].v,w=e[j].w;
        if (d1[i]+w+d3[v]==d1[y1])
        {
        	if (d2[i]+w+d4[v]==d2[y2]) add2(i,v,w);
        	if (d2[v]+w+d4[i]==d2[y2]) add2(v,i,w);
		}
		
        //有向图会漏判 
    }
    memset(dp,0,sizeof(dp)); 
    for (int i=1;i<=n;i++) if (rd[i]&&!dp[i]) dfs(i);//枚举每一个边进行记忆化 
    for (int i=1;i<=n;i++) maxx=max(maxx,dp[i]); 
    cout<<maxx<<endl;
}

几个hack数据都能过，要是有错请指出_(:з」∠)_