Competitive Programming 3 by Unknown

Author:Unknown
Language: eng
Format: epub

CHAPTER 4. GRAPH

c

Steven & Felix

Exercise 4.5.1.1: This is because we will add AdjMat[i][k] + AdjMat[k][j] which will

overflow if both AdjMat[i][k] and AdjMat[k][j] are near the MAX INT range, thus giving

wrong answer.

Exercise 4.5.1.2: Floyd Warshall’s works in graph with negative weight edges. For graph

with negative cycle, see Section 4.5.3 about ‘finding negative cycle’.

Exercise 4.5.3.1: Running Warshall’s algorithm directly on a graph with V ≤ 1000 will

result in TLE. Since the number of queries is low, we can afford to run O( V + E) DFS per

query to check if vertex u and v are connected by a path. If the input graph is directed, we

can find the SCCs of the directed graphs first in O( V + E). If u and v belong to the same SCC, then u will surely reach v. This can be tested with no additional cost. If SCC that

contains u has a directed edge to SCC that contains v, then u will also reach v. But the

connectivity check between different SCCs is much harder to check and we may as well just

use a normal DFS to get the answer.

Exercise 4.5.3.3: In Floyd Warshall’s, replace addition with multiplication and set the

main diagonal to 1 . 0. After we run Floyd Warshall’s, we check if the main diagonal > 1 . 0.

Exercise 4.6.3.1: A. 150; B = 125; C = 60.

Exercise 4.6.3.2: In the updated code below, we use both Adjacency List (for fast enu-

meration of neighbors; do not forget to include backward edges due to backward flow) and

Adjacency Matrix (for fast access to residual capacity) of the same flow graph, i.e. we con-

centrate on improving this line: for (int v = 0; v < MAX_V; v++). We also replace vi

dist(MAX V, INF); to bitset < MAX V > visited to speed up the code a little bit more.

// inside int main(), assume that we have both res (AdjMatrix) and AdjList

mf = 0;

while (1) {

// now a true O(VE^2) Edmonds Karp’s algorithm

f = 0;

bitset<MAX_V> vis; vis[s] = true;

// we change vi dist to bitset!

queue<int> q; q.push(s);

p.assign(MAX_V, -1);

while (!q.empty()) {

int u = q.front(); q.pop();

if (u == t) break;

for (int j = 0; j < (int)AdjList[u].size(); j++) {

// AdjList here!

int v = AdjList[u][j];

// we use vector<vi> AdjList

if (res[u][v] > 0 && !vis[v])

vis[v] = true, q.push(v), p[v] = u;

}

}

augment(t, INF);

if (f == 0) break;

mf += f;

}

Exercise 4.6.4.1: We use ∞ for the capacity of the ‘middle directed edges’ between the

left and the right sets of the bipartite graph for the overall correctness of this flow graph

modeling. If the capacities from the right set to sink t is not 1 as in UVa 259, we will get

wrong Max Flow value if we set the capacity of these ‘middle directed edges’ to 1.

189

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.