Likecoding > 道路与航线题解

道路与航线题解

2020-05-30

C++, 题解

老久没有发布新的题解了，这次就我挑选几道把题解发上来吧。

原题目链接：

  1. BZOJ2200
  2. 洛谷P3008
  3. AcWing342

题目难度：

  1. 洛谷评分$\color{blue}\text{蓝色}$
  2. AcWing评分$\color{yellow}\text{中等}$
  3. 我认为 码量较大 思路比较难想（第一次碰到这种题目，你都不会想到这么去做） 阅读者：我要我认为，不要你认为

正解稍难，要想。用SPF优化简单，但碰到以后的题目可能会被卡。

题目大意

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 $T$ 个城镇，编号为 $1~T$。

这些城镇之间通过 $R$ 条道路 (编号为 $1$ 到 $R$ ) 和 $P$ 条航线 (编号为 $1$ 到 $P$ ) 连接。

每条道路 $i$ 或者航线 $i$ 连接城镇$A_i$到$B_i$，花费为$C_i$。

对于道路，$0 \le C_i \le 10,000$;然而航线的花费很神奇，花费$C_i$可能是负数($-10,000 \le C_i \le 10,000$)。

道路是双向的，可以从$A_i$到$B_i$，也可以从$B_i$到$A_i$，花费都是$C_i$。

然而航线与之不同，只可以从$A_i$到$B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从$A_i$到$B_i$，那么保证不可能通过一些道路和航线从$B_i$回到$A_i$。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇S把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数 $T$ , $R$ , $P$ ,$S$。

接下来R行，每行包含三个整数（表示一个道路）$A_i,B_i,C_i$。

接下来P行，每行包含三个整数（表示一条航线）$A_i,B_i,C_i$。

输出格式

第1..T行：第i行输出从S到达城镇i的最小花费，如果不存在，则输出“NO PATH”。

数据范围

$1 \le T \le 25000$,
$1 \le R,P \le 50000$,
$1 \le A_i,B_i,S \le T$,

输入样例：

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

输出样例：

NO PATH
NO PATH
5
0
-95
-100

题解

这道题目分为两种，第一种是航线，第二种是道路。其中很明显的是航线是有向边，而道路是无向边。
由于航路中的 $c_i$ 可以是负数，所以直接的跑 $\text{dijkskra}$ 肯定是不行的。然而，数据通过特殊构造，成功的将SPFA也卡掉了（其中SPF优化没有卡掉，这里暂时不写SPF优化的算法，因为在现在的正式比赛中，SPF优化也会被卡掉）。
这是我们发现，道路中的 $c_i$ 是证书，只要航路的 $c_i$ 才有可能是负数。因此，我们利用这个特性就可以解决这道题目了。

第一步，我们把这些道路形成连通块当中，将每个连通块看做是一个点。缩点操作可以查看下方代码：

1
2
3
4
5
6
7
void dfs(int x,int l) {
    lt[l].push_back(x);v[x]=1;ll[x]=l; //lt用于保存每个连通块 v表示是否被访问过 ll标记这个点属于哪个连通块
    for(int i=head1[x];i;i=Next1[i])
        if(!v[ver1[i]]) dfs(ver1[i],l);
}
for(int i=1;i<=t;i++)
    if(!v[i]) dfs(i,++lts); //没有访问过那么就是下一个连通块

第二步，将航线的点添加进去，保存到另一个数组当中。 

1
2
3
4
5
for(int i=1;i<=p;i++) {
    scanf("%d%d%d",&a,&b,&c);
    add2(a,b,c);
    degree[ll[b]]++;
}

第三步，使用拓扑序，依次遍历。说到这里，为什么要使用拓扑序呢？

我们需要一个顺序，从起点s跑到终点t。而拓扑排序正好符合要求。

然后你可能会习惯性的就将第一个点添加进去。但是，这是拓扑排序欸！

一开始我只添加了起点的连通块进去。然后获得了24分的好成绩。为什么不能只能添加一个连通块进去呢？ ——jyeric

因为入度尽管为0，但是出度不一定是0啊。那么我们需要把前往这些点的边给全部跑掉。否则某些点就跑不到了。


就像这张歪七扭八的拓扑排序图片一样 有“8”这个点在，不去访问，你就到不了3。这是一个拓扑排序的问题。所以遇到拓扑排序基本上都是：将入度为0的边加入到queue当中，而不是将首个加入到队列。这是一个习惯性的写法 易错

然后其他的就没有什么特殊的。就是一个连通块通过航线连接到另一个连通块的过程。看代码应该能看懂。

代码：

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
#include<bits/stdc++.h>
#define pii pair<int,int>
#define N 25010
#define M 50010
using namespace std;
int t,r,p,s;
int edge1[2*M],Next1[2*M],head1[N],ver1[2*M],tot1=0;
int edge2[2*M],Next2[2*M],head2[N],ver2[2*M],tot2=0;
int degree[N],d[N],len[N],sv[N];
bool v[N],vis[N];
vector<int> lt[N];int lts=0,ll[N];
queue<int> q;
priority_queue<pii> pq;
void dfs(int x,int l) {
    lt[l].push_back(x);v[x]=1;ll[x]=l;
    for(int i=head1[x];i;i=Next1[i])
        if(!v[ver1[i]]) dfs(ver1[i],l);
}
void add1(int a,int b,int c) {
    ver1[++tot1]=b;edge1[tot1]=c;Next1[tot1]=head1[a];head1[a]=tot1;
    ver1[++tot1]=a;edge1[tot1]=c;Next1[tot1]=head1[b];head1[b]=tot1;
} 
void add2(int a,int b,int c) {
    ver2[++tot2]=b;edge2[tot2]=c;Next2[tot2]=head2[a];head2[a]=tot2;
}
int main() {
    memset(d,0x3f,sizeof(d));
    scanf("%d%d%d%d",&t,&r,&p,&s);
    int a,b,c;
    for(int i=1;i<=r;i++) {
        scanf("%d%d%d",&a,&b,&c);
        add1(a,b,c);
    }
    for(int i=1;i<=t;i++)
        if(!v[i]) dfs(i,++lts);
    for(int i=1;i<=p;i++) {
        scanf("%d%d%d",&a,&b,&c);
        add2(a,b,c);
        degree[ll[b]]++;
    }
    d[s]=0;
    for(int i=1;i<=lts;i++)
        if(degree[i]==0) q.push(i);
    while(!q.empty()) {
        int x=q.front();q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=0;i<lt[x].size();i++)
            if(d[lt[x][i]]!=0x3f3f3f3f)
                pq.push(make_pair(-d[lt[x][i]],lt[x][i]));
        memset(v,0,sizeof(v));
        while(!pq.empty()) { //在连通块内部跑一遍dijkstra
            int xx=pq.top().second;pq.pop();
            if(v[xx]) continue;
            v[xx]=1;
            for(int i=head1[xx];i;i=Next1[i]) {
                if(edge1[i]+d[xx]<d[ver1[i]]) {
                    d[ver1[i]]=d[xx]+edge1[i];
                    pq.push(make_pair(-d[ver1[i]],ver1[i]));
                }
            }
            for(int i=head2[xx];i;i=Next2[i])
                d[ver2[i]]=min(d[ver2[i]],edge2[i]+d[xx]);
        }
        for(int i=0;i<lt[x].size();i++) { //拓扑排序 每个出度-1的过程
            for(int j=head2[lt[x][i]];j;j=Next2[j]) {
                degree[ll[ver2[j]]]--;
                if(!degree[ll[ver2[j]]]) q.push(ll[ver2[j]]);
            }
        }
    }
    for(int i=1;i<=t;i++)
        if(d[i]==0x3f3f3f3f) printf("NO PATH\n");
        else printf("%d\n",d[i]);
    return 0;
}

感谢阅读~