水题笔记_ Noip2009T3 最优贸易 [BFS]

没有什么是一遍搜索解决不了的, 如果有, 那就正反两遍

啧啧啧…

懵逼的 题目

传送至 Luogu

扯淡的 题解

正反两遍bfs就好惹…
从终点bfs, 求出[终点到每个点 路途中的最大价格]
从起点bfs, 求出[起点到每个点 路途中的最小价值]
注意两点:

  • 最小值最大值的初始化, 因为可能有[起点可以到达但不能到达终点的点] || [可以到达终点但不能从起点达到的点]
  • 边的条数, 题目中的m不是边的条数而是输入的行数, 边还是应该开m << 1垃圾题目

沙茶的 代码

话说有什么好的[反向建图, 从终点bfs]的写法嘛…感觉好丑TUT

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// noip2009T3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
int from;
int to;
int next;
}b[MAXM << 1], bf[MAXN << 1];
int cntb = 0;
int cntbf = 0;
int g[MAXN];
int gf[MAXN];

struct node
{
int minc;
int maxc;
}a[MAXN];

struct qnode
{
int bh;
int zhi;
qnode(int b, int z): bh(b), zhi(z) {}
};
int n;
int m;
int ans;
int val[MAXN];
void bfs0(int);
void bfs1(int);
void adn(int, int);
void adnf(int, int);
void solve();
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> val[i];
a[i].maxc = 0;
a[i].minc = INF;
}
int srx, sry, srz;
for (int i = 1; i <= m; i++)
{
cin >> srx >> sry >> srz;
if (srz == 1)
{
adn(srx, sry);
adnf(sry, srx);
}
else
{
adn(srx, sry);
adn(sry, srx);
adnf(srx, sry);
adnf(sry, srx);
}
}
solve();
cout << ans;
return 0;
}
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void adnf(int from, int to)
{
bf[++cntbf].next = gf[from];
bf[cntbf].from = from;
bf[cntbf].to = to;
gf[from] = cntbf;
}
void solve()
{
bfs0(1);
bfs1(n);
for (int i = 1; i <= n; i++)
{
ans = max(ans, a[i].maxc - a[i].minc);
}
}
void bfs0(int startDash)
{
int v[MAXN];
memset(v, 0, sizeof(v));
queue<qnode> q;
q.push(qnode(startDash, val[startDash]));
v[startDash] = 1;
while (!q.empty())
{
qnode dq = q.front(); q.pop();
a[dq.bh].minc = min(a[dq.bh].minc, dq.zhi);
if (v[dq.bh] >= 2)
continue;
v[dq.bh]++;
for (int i = g[dq.bh]; i; i = b[i].next)
{
if (v[b[i].to] < 2)
{
q.push(qnode(b[i].to, min(val[b[i].to], dq.zhi)));
}
}
}
}
void bfs1(int startDash)
{
int v[MAXN];
memset(v, 0, sizeof(v));
queue<qnode> q;
q.push(qnode(startDash, val[startDash]));
v[startDash] = 1;
while (!q.empty())
{
qnode dq = q.front(); q.pop();
a[dq.bh].maxc = max(a[dq.bh].maxc, dq.zhi);
if (v[dq.bh] >= 2)
continue;
v[dq.bh]++;
for (int i = gf[dq.bh]; i; i = bf[i].next)
{
if (v[bf[i].to] < 2)
{
q.push(qnode(bf[i].to, max(val[bf[i].to], dq.zhi)));
}
}
}
}

/*
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
*/

By 被D飞的 Cansult