Residual network: (credit: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow)
- if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity),
- if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y.
Augmenting path: a path from the source to the sink in the residual network, whose purpose is to increase the flow in the original one.
Ford-Fulkerson method: start with no flow everywhere and increase the total flow in the network while there is an augmenting path from the source to the sink with no full forward edges or empty backward edges - a path in the residual network.
A cut in a flow network is simply a partition of the vertices in two sets, let's call them A and B, in such a way that the source vertex is in A and the sink is in B.
The capacity of a cut is the sum of the capacities of the edges that go from a vertex in A to a vertex in B.
The flow of the cut is the difference of the flows that go from A to B (the sum of the flows along the edges that have the starting point in A and the ending point in B), respectively from B to A, which is exactly the value of the flow in the network, due to the entering flow equals leaving flow - property, which is true for every vertex other than the source and the sink.
The flow of the cut is less or equal to the capacity of the cut due to the constraint of the flow being less or equal to the capacity of every edge.
This implies that the maximum flow is less or equal to every cut of the network. This is where the max-flow min-cut theorem comes in and states that the value of the maximum flow through the network is exactly the value of the minimum cut of the network.
Maximum Bipartite Matching
http://shygypsy.com/tools/bpm.cpp (a bpm code)
UVa Problems:
- 10080: Gopher (II) (跟670几乎一样，先确定graph[][]即可,用scanf("%lf", ..) 和eps比较double型)
- 10092: The Problem with the Problem Setter (L: the number of problems that should be included; R: the total number of problems in the pool)
- 259: Software Allocation (每台机子只能run一个application, 又是典型的0-1 assignment)
- 670: The dog task
其实就是先填一个graph[][]即可，在每两个master点之间，确定dog能到达哪些interesting places. 然后就是一个0-1 assignment问题而已。另注意double型比较用了eps = 1e-18(开始用1e-15 WA: )
special case:
2 1
0 0 2 2
3 3
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define MAX 101
#define eps 1e-18
typedef pair<int,int> ii;
bool graph[MAX][MAX];
bool seen[MAX];
int matchL[MAX], matchR[MAX];
// n: dim of L; m: dim of R
int n, m;
bool bpm( int u ) {
for( int v = 0; v < m; 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;
}
double dist(ii a, ii b) {
return sqrt((a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second) + 0.0);
}
int main() {
int ndata;
scanf("%d ", &ndata);
while(ndata--) {
scanf("%d %d ", &n, &m);
vector<ii> master(n);
vector<ii> place(m);
for(int i = 0; i < n; ++i)
scanf("%d %d ", &master[i].first, &master[i].second);
for(int i = 0; i < m; ++i)
scanf("%d %d ", &place[i].first, &place[i].second);
memset(graph, false, sizeof(graph));
memset( matchL, -1, sizeof( matchL ) );
memset( matchR, -1, sizeof( matchR ) );
for(int i = 0; i < n-1; ++i) {
// master's walking distance doubled
double d2 = dist(master[i], master[i+1]) * 2;
for(int j = 0; j < m; ++j) {
// dog's walking distance
double dogdist = dist(master[i], place[j]) + dist(place[j], master[i+1]);
// as long as dog's walking distance is no more than 2xmaster's, the dog can visit this place
if(d2 - dogdist>= eps)
graph[i][j] = true;
}
}
int cnt = 0;
for( int i = 0; i < n; ++ i){
memset(seen, 0, sizeof( seen ) );
if(bpm(i)) cnt++;
}
printf("%d\n", n+cnt);
printf("%d %d", master[0].first, master[0].second);
for(int i = 0; i < n; ++i) {
if(i) printf(" %d %d", master[i].first, master[i].second);
if(matchL[i] != -1) {
int p = matchL[i];
printf(" %d %d", place[p].first, place[p].second);
}
}
printf("\n");
if(ndata) printf("\n");
}
}
- 663: Sorting Slides (use point in rectangle to get graph[][])
这题难点在于要输出unique的matching, 我是run max bipartite matching 算法 |E|次(the number of edges), 每次检查uniqueness
#include <iostream>
#include <vector>
using namespace std;
struct Rect {
int xmin;
int xmax;
int ymin;
int ymax;
};
#define MAX 27 // the number of alphabet
bool graph[MAX][MAX];
bool seen[MAX];
int matchL[MAX], matchR[MAX];
int n;
Rect slides[MAX];
bool exist; // if solution already exists
int savedR[MAX]; // save previous solution
// if a points is inside a rectangle
inline bool ptInRect(int x, int y, Rect r) {
//No number will lie on a slide boundary.
if (x > r.xmin && x < r.xmax && y > r.ymin && y < r.ymax) return true;
return false;
}
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() {
int ndata = 0;
while(scanf("%d ", &n) && n) {
printf("Heap %d\n", ++ndata);
for(int i = 0; i < n; ++i) {
scanf("%d %d %d %d ", &slides[i].xmin,
&slides[i].xmax,
&slides[i].ymin,
&slides[i].ymax);
}
memset(graph, false, sizeof(graph));
memset(savedR, -1, sizeof(savedR));
exist = false;
int x, y;
for(int i = 0; i < n; ++i) {
scanf("%d %d ", &x, &y);
for(int j = 0; j < n; ++j)
if(ptInRect(x, y, slides[j]))
graph[i][j] = true;
}
int cnt = 0;
for(int u = 0; u < n; ++u) {
for(int v = 0; v < n; ++v) {
// each time, put one edge into the match
// and try to construct the max bipartite match based on that
if(!graph[u][v])
continue;
memset( matchL, -1, sizeof( matchL ) );
memset( matchR, -1, sizeof( matchR ) );
matchL[u] = v;
matchR[v] = u;
int cnt = 1;
for( int i = 0; i < n; ++ i){
if (i == u) continue;
memset(seen, 0, sizeof( seen ));
if(bpm(i)) cnt++;
}
if(exist) {
for(int k = 0; k < n; ++k)
//check uniqueness
if (matchR[k] != savedR[k])
savedR[k] = -1; // not unique, reset to -1
} else {
memcpy(savedR, matchR, sizeof(int)*n); // save the first solution
exist = true;
}
}
}
int cardinal = 0;
int i;
for(i = 0; i < n; ++i) {
if(savedR[i] != -1) {
++cardinal;
printf("(%c,%d)", i + 'A', savedR[i] + 1);
break;
}
}
for(++i; i < n; ++i) {
if(savedR[i] != -1) {
++cardinal;
printf(" (%c,%d)", i + 'A', savedR[i] + 1);
}
}
if(cardinal == 0)
printf("none");
printf("\n\n");
}
}
