-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathflow2.cpp
More file actions
117 lines (103 loc) · 3.23 KB
/
flow2.cpp
File metadata and controls
117 lines (103 loc) · 3.23 KB
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
/**
* //////////////////
* // MAXIMUM FLOW //
* //////////////////
*
* This file is part of my library of algorithms found here:
* http://shygypsy.com/tools/
* LICENSE:
* http://shygypsy.com/tools/LICENSE.html
* Copyright (c) 2006
* Contact author:
* abednego at gmail.c0m
**/
/****************
* Maximum flow * (Dinic's on an adjacency list + matrix)
****************
* Takes a weighted directed graph of edge capacities as an adjacency
* matrix 'cap' and returns the maximum flow from s to t.
*
* PARAMETERS:
* - cap (global): adjacency matrix where cap[u][v] is the capacity
* of the edge u->v. cap[u][v] is 0 for non-existent edges.
* - n: the number of vertices ([0, n-1] are considered as vertices).
* - s: source vertex.
* - t: sink.
* RETURNS:
* - the flow
* - prev contains the minimum cut. If prev[v] == -1, then v is not
* reachable from s; otherwise, it is reachable.
* RUNNING TIME:
* - O(n^3)
* FIELD TESTING:
* - Valladolid 10330: Power Transmission (Gives WA, but it's probably my graph building that's wrong)
* - Valladolid 563: Crimewave
* - Valladolid 753: A Plug for UNIX
* - Valladolid 10511: Councilling
* - Valladolid 820: Internet Bandwidth
* - Valladolid 10779: Collector's Problem
* #include <string.h>
**/
#include <string.h>
#include <stdio.h>
// the maximum number of vertices
#define NN 1024
// adjacency matrix (fill this up)
// If you fill adj[][] yourself, make sure to include both u->v and v->u.
int cap[NN][NN], deg[NN], adj[NN][NN];
// BFS stuff
int q[NN], prev[NN];
int dinic( int n, int s, int t )
{
int flow = 0;
while( true )
{
// find an augmenting path
memset( prev, -1, sizeof( prev ) );
int qf = 0, qb = 0;
prev[q[qb++] = s] = -2;
while( qb > qf && prev[t] == -1 )
for( int u = q[qf++], i = 0, v; i < deg[u]; i++ )
if( prev[v = adj[u][i]] == -1 && cap[u][v] )
prev[q[qb++] = v] = u;
// see if we're done
if( prev[t] == -1 ) break;
// try finding more paths
for( int z = 0; z < n; z++ ) if( cap[z][t] && prev[z] != -1 )
{
int bot = cap[z][t];
for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
bot <?= cap[u][v];
if( !bot ) continue;
cap[z][t] -= bot;
cap[t][z] += bot;
for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
{
cap[u][v] -= bot;
cap[v][u] += bot;
}
flow += bot;
}
}
return flow;
}
//----------------- EXAMPLE USAGE -----------------
int main()
{
// read a graph into cap[][]
memset( cap, 0, sizeof( cap ) );
int n, s, t, m;
scanf( " %d %d %d %d", &n, &s, &t, &m );
while( m-- )
{
int u, v, c; scanf( " %d %d %d", &u, &v, &c );
cap[u][v] = c;
}
// init the adjacency list adj[][] from cap[][]
memset( deg, 0, sizeof( deg ) );
for( int u = 0; u < n; u++ )
for( int v = 0; v < n; v++ ) if( cap[u][v] || cap[v][u] )
adj[u][deg[u]++] = v;
printf( "%d\n", dinic( n, s, t ) );
return 0;
}