图算法和图模型(七)

这篇文章继续对最短路问题做相关阐述
主要讲一下负权边的处理
以及状态图建图的技巧和方法

多阶段 Dijkstra

UVALive3561

看一下这个例子的建图过程
LA3561

$\textbf{algorithm}$
$\textbf{i) } \text{build graph}$
$\quad \textbf{ for } \forall \text{trip} \in [1, \text{NI}]$
$\quad \quad \text{ get trip List} \rightarrow ([\textbf{toList}], len)$
$\quad \quad \text{ chooseTicket}([\textbf{toList}, len])$

$\quad \text{ chooseTicket}(\textbf{toList}, len):$
$\quad \quad \textbf{ for } \forall i \in [0, \text{NT}), \textbf{ for } \forall k \in [1, tot]$
$\quad \quad \quad \textbf{ st}=(k,\text{tickets[i,0]})$
$\quad \quad \quad \textbf{ for } \forall j \in [1, \text{tickets}(i).\text{size)}$
$\quad \quad \quad \quad \textbf{ if } \textbf{ toList}[k]=\text{tickets}[i,j], \textbf{Edge}(\textbf{st}, (k+1, \text{tickets[i, j]}), \text{cost})$
$\quad \quad \quad \quad \textbf{ else } \textbf{Edge}(\textbf{st}, (k, \text{tickets}[i, j], \text{cost})$
$\quad \quad \quad \quad \text{ cost}:=(\text{price}[ith\text{-Tickets}], \text{ticketID})$

$\textbf{ii) } \text{run } Dijkstra()$

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

const int maxN = 4000 + 10;
const int inf = 0x3f3f3f3f;
int nCities = 0;
const int maxn = 100;
vector<int> tickets[maxn];
int cost[maxn];
int NT, NI;

// == Graph ==
vector<int> G[maxN];

class Edge {
public:
int from, to, weight, val;
Edge() {}
Edge(int u, int v, int w, int val) : from(u), to(v), weight(w), val(val) {}
};

class Node {
public:
int u, dist;
Node() {}
Node(int u, int dist) : u(u), dist(dist) {}
bool operator< (const Node& rhs) const {
return dist > rhs.dist;
}
};

vector<Edge> edges;

void initG() {
_for(i, 0, maxN) G[i].clear();
edges.clear();
}

void addEdge(int u, int v, int w, int val) {
edges.push_back(Edge(u, v, w, val));
G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];
int pid[maxN];

void initDij(int st) {
_for(i, 0, maxN) D[i] = inf;
D[st] = 0;

Set(vis, 0);
Set(pid, 0);
}

void dijsktra(int st) {
initDij(st);
priority_queue<Node> que;
que.push(Node(st, 0));

while (!que.empty()) {
int x = que.top().u;
que.pop();
if(vis[x]) continue;
vis[x] = 1;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;
if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
pid[y] = G[x][i];
que.push(Node(y, D[y]));
}
}
}
}

vector<int> getPath(int ed, const int st) {
vector<int> path;
while (ed != st) {
path.push_back(edges[pid[ed]].val);
ed = edges[pid[ed]].from;
}
reverse(path.begin(), path.end());
return path;
}
// == dijkstra finsihed ==

// == get all tickets ==
map<int, int> cityID;

inline int ID(int x) {
if(cityID.count(x)) return cityID[x];
cityID[x] = ++nCities;
return nCities;
}

inline int ID(int i, int j) {
return (i - 1) * nCities + j;
}

void getTickets(const int NT) {
_for(i, 0, NT) {
tickets[i].clear();
int len;
scanf("%d%d", &cost[i], &len);
while (len--) {
int x;
scanf("%d", &x);
tickets[i].push_back(ID(x));
}
}
}
// == get tickets finished ==

// == get trip data ==
vector<int> toList;
int getTrip(const int trip) {
toList.clear();
int tot = 0;
scanf("%d", &tot);

_for(i, 0, tot) {
int x;
scanf("%d", &x);
toList.push_back(ID(x));
}

return tot;
}
// == trip finished ==

// == chooseTicket for trip ==
void chooseTicket(const vector<int>& toList, const int tot) {
_for(i, 0, NT) _rep(k, 1, tot) {
int cur = tickets[i][0];
int k2 = k;

_for(j, 1, tickets[i].size()) {
int A = tickets[i][j];
if(A == toList[k2]) k2++;
if(k2 > tot) break;

addEdge(ID(k, cur), ID(k2, A), cost[i], i + 1);
if(k2 == tot) break;
}
}
}
// == chooseTicket finished ==

void init() {
nCities = 0;
cityID.clear();
_for(i, 0, maxn) tickets[i].clear();
Set(cost, 0);
}

int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while (scanf("%d", &NT) == 1 && NT) {
init();

// get tickets
getTickets(NT);
scanf("%d", &NI);
kase++;

_rep(trip, 1, NI) {
int tot = getTrip(trip);
assert(toList.size() != 0);

initG();
chooseTicket(toList, tot);
int src = ID(1, toList[0]), ed = ID(tot, toList[tot-1]);
dijsktra(src);

printf("Case %d, Trip %d: Cost = %d\n", kase, trip, D[ed]);
printf(" Tickets used:");

vector<int> res = getPath(ed, src);
_for(i, 0, res.size()) printf(" %d", res[i]);
printf("\n");
}
}
}

状态建图

UVALive3661
LA3661

$\textbf{algorithm}$
$\textbf{build graph}$
$\textbf{i) } \text{get vector}$

$\textbf{ii) } u=\textbf{ID(edges)}=\textbf{ID}(\textbf{top}(i,j,dir), \cdots)$
$\quad \ \ v=\textbf{ID}(\textbf{edges}) = \textbf{ID}(\textbf{slash}(i, j, dir))$
$\quad \ \ add(u, v, cost(\textbf{slash}(i, j, dir)))$

$\textbf{dijkstra}$
$\textbf{i) st} = 0, \ add(\textbf{0}, \textbf{leftBorder})$
$\quad add(\textbf{0, bottomBorder})$

$\quad \textbf{ed right}= $
$\quad \quad \textbf{for } \forall i \in [0, n)$
$\quad \quad \quad \textbf{ID}(i, m-1, dir=1)$

$\quad \textbf{ed top}=$
$\quad \quad \textbf{for } \forall i \in [0, m)$
$\quad \quad \quad \textbf{ID}(0, i, dir = 0)$

$\textbf{ii) } \text{run } dijkstra()$
$\quad \textbf{ ans} = \min (\textbf{D[ed right], D[ed top]})$

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
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
const int maxN = 4000000;
int cost[maxn][maxn][3];
int n, m;

// == Graph definition ==
vector<int> G[maxN];
class Edge {
public:
int to, weight;
Edge() {}
Edge(int to, int w) : to(to), weight(w) {}
};

class Node {
public:
int u, dist;
Node() {}
Node(int u, int d) : u(u), dist(d) {}
bool operator< (const Node& rhs) const {
return dist > rhs.dist;
}
};
vector<Edge> edges;

void initG() {
_for(i, 0, maxN) G[i].clear();
edges.clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == dijkstra ==
int D[maxN], vis[maxN];

void initDij(int st) {
Set(D, inf);
D[st] = 0;

Set(vis, 0);
}

void dijkstra(int st) {
initDij(st);
priority_queue<Node> que;
que.push(Node(st, 0));

while (!que.empty()) {
int x = que.top().u;
que.pop();
if(vis[x]) continue;
vis[x] = 1;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;
if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
que.push(Node(y, D[y]));
}
}
}
}
// == dijkstra finsihed ==

inline int ID(int i, int j, int dir) {
return i*m+j+1 + dir*n*m;
}

inline int read() {
int x;
scanf("%d", &x);
return x;
}

// == build graph ==
void getEdge(int *e1, int *e2, int *e3) {
int *edges[3] = {e1, e2, e3};
// edges[i]:= (i, j, dir)
_for(i, 0, 3) _for(j, 0, 3) if(i != j) {
int u = ID(edges[i][0], edges[i][1], edges[i][2]);
int v = ID(edges[j][0], edges[j][1], edges[j][2]);
int w = cost[edges[j][0]][edges[j][1]][edges[j][2]];

addEdge(u, v, w);
}
}

void build() {
_for(i, 0, n - 1) _for(j, 0, m - 1) {
int top[] = {i, j, 0};
int bottom[] = {i + 1, j, 0};
int left[] = {i, j, 1};
int right[] = {i, j + 1, 1};
int slash[] = {i, j, 2};

getEdge(top, right, slash);
getEdge(bottom, left, slash);
}

_for(i, 0, n - 1) {
int u = ID(i, 0, 1);
int w = cost[i][0][1];
addEdge(0, u, w);
}
_for(i, 0, m - 1) {
int u = ID(n - 1, i, 0);
int w = cost[n - 1][i][0];
addEdge(0, u, w);
}
}
// == build finsiehd ==

void init() {
Set(cost, 0);
}

int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while (scanf("%d%d", &n, &m) == 2 && n) {
init();
initG();

// get data
_for(i, 0, n) _for(j, 0, m-1) cost[i][j][0] = read();
_for(i, 0, n - 1) _for(j, 0, m) cost[i][j][1] = read();
_for(i, 0, n - 1) _for(j, 0, m - 1) cost[i][j][2] = read();

// build graph
build();

// dijkstra
dijkstra(0);

// get ans
int ans = inf;
_for(i, 0, n - 1) ans = min(ans, D[ID(i, m - 1, 1)]);
_for(i, 0, m - 1) ans = min(ans, D[ID(0, i, 0)]);

//debug(ans);

printf("Case %d: Minimum = %d\n", ++kase, ans);
}
}

最短路和dp

ZOJ1232

$\textbf{i) run } floyd()$
$\quad f(i,j) \leftarrow f(i, k) + f(k, j)$
$\quad \quad \textbf{if } k \in [1,A], D[i,j] \leqslant L$
$\quad \quad \quad (\text{st} \rightarrow k) \text{ can use magic boot} \textbf{, valid}(i, j) = 1$

$\textbf{ii) }$

$\textbf{st:=}$
$\quad \textbf{for } \forall i \in V, dp(i, 0) = D(st, i)$
$\quad \textbf{for } \forall k \in [0, K], dp(st, k) = 0$
$\textbf{ed:=}$
$\quad dp(ed, K)$

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
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
int D[maxn][maxn];
int valid[maxn][maxn];
int a, b, m, L, K;

void init() {
Set(D, inf);
_for(i, 0, maxn) D[i][i] = 0;

Set(valid, 0);
}

void build() {
_for(i, 0, m) {
int u, v, L;
scanf("%d%d%d", &u, &v, &L);
D[u][v] = D[v][u] = min(D[v][u], L);
}
}

void floyd() {
_rep(k, 1, a+b) _rep(i, 1, a+b) _rep(j, 1, a+b) {
if(D[i][j] > D[i][k] + D[k][j]) {
D[i][j] = D[i][k] + D[k][j];
}
if(k <= a && D[i][j] <= L) valid[i][j] = 1;
}
}

// == dp ==
const int st = 1;
int dp[maxn][maxn];

void initDP() {
Set(dp, inf);
_rep(i, 1, a+b) dp[i][0] = D[st][i];
_rep(k, 0, K) dp[st][k] = 0;
}

void solve() {
_rep(i, 1, a+b) _rep(k, 1, K) {
_for(j, 1, i) {
if(valid[i][j] == 1)
dp[i][k] = min(dp[i][k], dp[j][k - 1]);
dp[i][k] = min(dp[i][k], dp[j][k] + D[j][i]);
}
}
}
// == dp finished ==

int main() {
freopen("input.txt", "r", stdin);
int kase;
scanf("%d", &kase);

while (kase--) {
init();
scanf("%d%d%d%d%d", &a, &b, &m, &L, &K);

// build
build();

// floyd
floyd();

// dp
initDP();
solve();

printf("%d\n", dp[a+b][K]);
}
}

最短路和dp(二)

$\text{这里的状态转移比较特殊}$
$\text{在每一个节点 } u, \text{加油,必须一升一升加}$

$\textbf{algorithm}$
$\text{run } dijkstra()$
$\quad \quad \textbf{vis}(u, gas) = 1\text{ , mark node complete}$

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
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;
int n, m;
int P[maxn];

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
int from, to, weight;
Edge() {}
Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
_for(i, 0, maxn) G[i].clear();
edges.clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
int u, gas, cost;
bool operator< (const State& rhs) const {
return cost > rhs.cost;
}

State() {}
State(int u, int g, int c) : u(u), gas(g), cost(c) {}
};

int vis[maxn][maxn];
int ans = inf;

void initDij(int st, const int C) {
Set(vis, 0);
ans = inf;
}

bool dijkstra(int st, int ed, const int C) {
initDij(st, C);
priority_queue<State> que;
que.push(State(st, 0, 0));

while (!que.empty()) {
State x = que.top();
que.pop();

if(x.u == ed) {
ans = x.cost;
return true;
}

if(vis[x.u][x.gas]) continue;
vis[x.u][x.gas] = 1;

if(x.gas + 1 <= C) {
State nxt(x.u, x.gas + 1, x.cost + P[x.u]);
que.push(nxt);
}
_for(i, 0, G[x.u].size()) {
const Edge& e = edges[G[x.u][i]];
int y = e.to;

if(x.gas >= e.weight) {
State nxt(y, x.gas - e.weight, x.cost);
que.push(nxt);
}
}
}
return false;
}
// == Dijkstra finsihed ==

void init() {
Set(P, 0);
}

void solve() {
int q;
scanf("%d", &q);
while (q--) {
int st, ed, C;
scanf("%d%d%d", &C, &st, &ed);
if(dijkstra(st, ed, C)) printf("%d\n", ans);
else printf("impossible\n");
}
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

initG();
init();
// get data
_for(i, 0, n) scanf("%d", &P[i]);
_for(i, 0, m) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}

// each query, dijkstra
solve();
}

最短路拓展

UVA11280

$\textbf{algorithm: } Dijkstra(st)$

$\textbf{for } \forall e(x, y)$
$\quad D(y, k+1) \leftarrow D(x, k) + w(x, y)$

$st\rightarrow ed, \text{ query}(S)$
$\textbf{start:=} (st, 0)$
$\textbf{end:=} \textbf{ for } \forall k \in [1, S]$
$\quad \quad \quad \textbf{ans = } \min(D(ed, k))$

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
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int tot = 0;
map<string, int> id;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
int from, to, weight;
Edge() {}
Edge(int u, int v, int w) : from(u), to(v), weight(w) {}
};

vector<Edge> edges;

void initG() {
_for(i, 0, maxn) G[i].clear();
edges.clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finished ==

// == Dijkstra ==
class State {
public:
int u, k, dist;
State() {}
State(int u, int k, int dist) : u(u), k(k), dist(dist) {}

bool operator< (const State& rhs) const {
return dist > rhs.dist;
}
};


int vis[maxn][maxn];
int D[maxn][maxn];

void initDij(const int st) {
Set(vis, 0);
Set(D, inf);
D[st][0] = 0;
}

void dijkstra(const int st) {
initDij(st);
priority_queue<State> que;
que.push(State(st, 0, 0));

while (!que.empty()) {
State x = que.top();
que.pop();
if(vis[x.u][x.k]) continue;
vis[x.u][x.k] = 1;

_for(i, 0, G[x.u].size()) {
const Edge& e = edges[G[x.u][i]];
int y = e.to;

if(D[y][x.k+1] > D[x.u][x.k] + e.weight) {
D[y][x.k+1] = D[x.u][x.k] + e.weight;
que.push(State(y, x.k+1, D[y][x.k+1]));
}
}
}
}
// == Dijkstra finished ==

inline void getID(const string& str) {
if(id.count(str)) return;
else {
id[str] = ++tot;
return;
}
}

void solve() {
int q;
scanf("%d", &q);
while (q--) {
int S;
scanf("%d", &S);

int ans = inf;
_rep(k, 1, S + 1) ans = min(ans, D[n][k]);

//debug(ans);
if(ans != inf) printf("Total cost of flight(s) is $%d\n", ans);
else printf("No satisfactory flights\n");
}
}

void init() {
tot = 0;
id.clear();
}

int main() {
freopen("input.txt", "r", stdin);
int T = 0;
scanf("%d", &T);

_rep(kase, 1, T) {
printf("Scenario #%d\n", kase);
init();
initG();

// get city data
scanf("%d", &n);
_for(i, 0, n) {
string str;
cin >> str;
getID(str);
}
// get flights data
scanf("%d", &m);
_for(i, 0, m) {
string from, to;
int w;
cin >> from >> to >> w;
int u = id[from], v = id[to];
//debug(u), debug(v), debug(w), puts("");

addEdge(u, v, w);
}
// get query
dijkstra(1);
solve();
if(kase != T) cout << endl;
}
}