Bipartite Graph Maximum Matching

发表于   |   分类于   |  

In this morning, my roommate H’s female friend asked him for help.Through my analysis, the girl was taking an examination… .What terrible means the girl was using!The girl begged my roommate H to help her to pass the examination and show how important the examination is to her constantly.But my roommate H was not clever enough to solve the problem and ask for my aid.Out of humanitarian and pure friendship between H and me, I decided to help this poor and desperate girl.The girl sent the promble to me and told me that there were only ten minutes left… .I took a look at the problem and found that the problem is very easy.It model of the problem is just to find the maximum matching in a bipartite graph.The description of the promble is below:

Description

There are many black points B={b1,b2,……,bn} and white points W={w1,w2,……,wm} in plane.A black point bi=(xi,yi) match a white point wj=(xj,yj) if and only if xi<=xj and yi<=yj.Futhermore a point can only match to one point in opposite colour.The problem is to find out the maximum number of matching conforming to the rules above.

Input Format

The first line includes an integer T represents there are T cases;
In each case, the first line has two integers n, m represent the number of black points and white points;
Then there is n+m lines and each line has two integers represent the coordinate of black points or white points.

Code

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
//Title：Solution
//Author：Call偶围城
#include <stdio.h>
#define MAXP 10000
#define MAXN 100000
int nblack, nwhite;
int blackMwhite[MAXN];
int blacks[MAXN][2], whites[MAXN][2];
int bond[MAXP][MAXP];
int matching[MAXN];
int find(int x) {
	int i;
	for (i = 0;i < nblack;i++) {
		if (bond[i][x] == 1 && matching[i] == -1) {
			matching[i] = 1;
			if (blackMwhite[i] == -1 || find(blackMwhite[i]) == 1) {
				blackMwhite[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	int T;
	int cnt;
	int i, j, k;
	scanf("%d", &T);
	while (T--) {
		cnt = 0;
		scanf("%d%d", &nblack, &nwhite);
		for (i = 0;i < MAXP;i++)
			for (j = 0;j < MAXP;j++)
				bond[i][j] = -1;
		for (i = 0;i < MAXN;i++) 
			blackMwhite[i] = -1;
		for (i = 0;i < nblack;i++)
			scanf("%d%d", &blacks[i][0], &blacks[i][1]);
		for (i = 0;i < nwhite;i++) 
			scanf("%d%d", &whites[i][0], &whites[i][1]);
		for (i = 0;i < nblack;i++) {
			for (j = 0;j < nwhite;j++) {
				if (blacks[i][0] <= whites[j][0] 
				 && blacks[i][1] <= whites[j][1]) {
					bond[i][j] = 1;
				}
			}
		}
		for (i = 0;i < nwhite;i++) {
			for (j = 0;j < MAXN;j++)
				matching[j] = -1;
			if (find(i) == 1)
				cnt++;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Samples

Sample Input
2
2 2
1 0
0 1
1 1
0 0
1 1
1 1
0 0

Sample Output
1
0

Plot Followed

Unfortunately, I just right used ten minutes to solve the promble and my PC is run on Ubuntu system.So I sent the code file to my roommate H by E-mail and he used QQ to sent the code file to the poor girl.This process totally spent about eleven minutes.That means it was just one minute after the end of examination when the girl recieved the code file.
The girl said me that she felt said that she failed the important examination but thanks a lot for my great help.She said she had never thought there would be anyone help she without any rewards or aims.But I considered the girl was too young too naive.As the old saying, there isn’t any love and hate without any reason, so do my assistance.I helped you because





























I just thought the problem was a little interesting and wanna solve it, hhha (●°u°●)​ 」