forked from jpcsousa/codejam
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbpm.cpp
More file actions
executable file
·95 lines (85 loc) · 2.68 KB
/
bpm.cpp
File metadata and controls
executable file
·95 lines (85 loc) · 2.68 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
/**
* ////////////////////////
* // BIPARTITE MATCHING //
* ////////////////////////
*
* This file is part of my library of algorithms found here:
* http://www.palmcommander.com:8081/tools/
* LICENSE:
* http://www.palmcommander.com:8081/tools/LICENSE.html
* Copyright (c) 2003
* Contact author:
* igor at cs.ubc.ca
**/
/**********************
* Bipartite matching * O(m*n^2))
**********************
* Given a bipartite graph represented as an m-by-n matrix, where graph[i][j]
* is true iff there is an edge from pigeon i to hole j, computes the maximum
* number of pigeons that can find a hole (one per pigeon) and an optimal
* assignment.
* Formally, this is a stripped down version of Ford-Fulkerson with
* DFS used to find an augmenting path. DFS does the job quickly because
* capacities can only be 0 or 1.
*
* PARAMETERS:
* - graph: adjacency matrix as above.
* RETURNS:
* - an integer corresponding to the number of assignments
* - matchL[m]: for each pigeon, a hole or -1
* - matchR[n]: for each hole, a pigeon or -1
* DETAILS:
* - graph[m][n], matchL[n], matchR[m] and seen[m] are global arrays
* - main() initializes matchL[] and matchR[] to all -1.
* - main() does a loop over all pigeons i and in each iteration
* - clears seen[] to all 0
* - calls bpm(i) and increments the maxflow counter
* - bpm(i) returns true iff pigeon i can be assigned a hole
* ACKNOWLEDGEMENTS:
* - Thanks to tjq from TopCoder for a reference implementation.
* FIELD TESTING:
* - Valladolid 10080: Gopher (II)
* - Valladolid 10092: The Problem with the Problem Setter
* - Valladolid 670: The dog task
* - Valladolid 259: Software Allocation
* #include <string.h>
**/
#include <string.h>
#define M 128
#define N 128
bool graph[M][N];
bool seen[N];
int matchL[M], matchR[N];
int n, m;
bool bpm( int u )
{
for( int v = 0; v < n; v++ ) if( graph[u][v] )
{
if( seen[v] ) continue;
seen[v] = true;
if( matchR[v] < 0 || bpm( matchR[v] ) )
{
matchL[u] = v;
matchR[v] = u;
return true;
}
}
return false;
}
int main()
{
// Read input and populate graph[][]
// Set m, n
memset( matchL, -1, sizeof( matchL ) );
memset( matchR, -1, sizeof( matchR ) );
int cnt = 0;
for( int i = 0; i < m; i++ )
{
memset( seen, 0, sizeof( seen ) );
if( bpm( i ) ) cnt++;
}
// cnt contains the number of happy pigeons
// matchL[i] contains the hole of pigeon i or -1 if pigeon i is unhappy
// matchR[j] contains the pigeon in hole j or -1 if hole j is empty
return 0;
}