简述二分图
二分圖又稱作二部圖，是圖論中的一種特殊模型。 設(shè)G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集(i in A,j in B)，則稱圖G為一個(gè)二分圖。
簡(jiǎn)而言之，就是頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)互不相交的子集。
區(qū)別二分圖，關(guān)鍵是看點(diǎn)集是否能分成兩個(gè)獨(dú)立的點(diǎn)集。
上圖是一個(gè)二分圖。
上圖不是一個(gè)二分圖。
我們可以用染色法判斷一個(gè)無(wú)向圖是否是二分圖；
從其中一個(gè)頂點(diǎn)開(kāi)始，將跟它鄰接的點(diǎn)染成與其不同的顏色，如果鄰接的點(diǎn)有相同顏色的，則說(shuō)明不是二分圖，每次用bfs遍歷即可。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | bool BFS(int s,int n) { ????queue<int >p; ????p.push(s); ????col[s]=1; ????while(!p.empty()) { ????????int from=p.front(); ????????p.pop(); ????????for(int i=1; i<=n; i++) { ????????????if(g[from][i]&&col[i]==-1) { ????????????????p.push(i); ????????????????col[i]=!col[from]; ????????????} ????????????if(g[from][i]&&col[from]==col[i]) { ????????????????return false; ????????????} ????????} ????} ????return true; } |
匹配：
給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。
最大匹配：
給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配.
選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題（maximal matching problem)
如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配.
如圖所示，圖中的最大匹配是4。
求最大匹配最常用的算法之一是匈牙利算法。匈牙利算法的核心是尋找增廣路徑。
**增廣路徑：
若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬于M的邊和不屬于M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑（舉例來(lái)說(shuō)，有A、B集合，增廣路由A中一個(gè)點(diǎn)通向B中一個(gè)點(diǎn)，再由B中這個(gè)點(diǎn)通向A中一個(gè)點(diǎn)……交替進(jìn)行）。
**由增廣路的定義可以推出下述三個(gè)結(jié)論：
1－P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。
2－不斷尋找增廣路可以得到一個(gè)更大的匹配M’，直到找不到更多的增廣路。
3－M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。
匈牙利算法的思路是不停的找增廣軌，并增加匹配的個(gè)數(shù)，增廣軌顧名思義是指一條可以使匹配數(shù)變多的路徑，在匹配問(wèn)題中，增廣軌的表現(xiàn)形式是一條”交錯(cuò)軌”,也就是說(shuō)這條由圖的邊組成的路徑，它的第一條邊是目前還沒(méi)有參與匹配的，第二條邊參與了匹配，第三條邊沒(méi)有..最后一條邊沒(méi)有參與匹配，并且始點(diǎn)和終點(diǎn)還沒(méi)有被選擇過(guò).這樣交錯(cuò)進(jìn)行，顯然他有奇數(shù)條邊.那么對(duì)于這樣一條路徑，我們可以將第一條邊改為已匹配，第二條邊改為未匹配…以此類(lèi)推.也就是將所有的邊進(jìn)行”反色”,容易發(fā)現(xiàn)這樣修改以后，匹配仍然是合法的，但是匹配數(shù)增加了一對(duì).另外，單獨(dú)的一條連接兩個(gè)未匹配點(diǎn)的邊顯然也是交錯(cuò)軌.可以證明，當(dāng)不能再找到增廣軌時(shí)，就得到了一個(gè)最大匹配.
時(shí)間復(fù)雜度為：O（n*m）n是其中一個(gè)頂點(diǎn)集的個(gè)數(shù)，m是另一個(gè)的個(gè)數(shù)。
空間復(fù)雜度是O（n^2）。
代碼參見(jiàn)小康學(xué)長(zhǎng)模板的52頁(yè)。
注：Hopcroft-Karp算法是對(duì)匈牙利算法的改進(jìn)，時(shí)間復(fù)雜度為O(E*V^1/2);
算法實(shí)質(zhì)其實(shí)就是匈牙利算法求增廣路，改進(jìn)的地方是在深度搜索增廣路前，先通過(guò)廣度搜索，查找多條可以增廣的路線，從而不再讓dfs“一意孤行”。其中算法用到了分層標(biāo)記防止多條增廣路重疊。
另一種（我個(gè)人覺(jué)得比較難的）的求最大匹配的算法是最大流。
求網(wǎng)絡(luò)流的最大流算法是Ford-Fulkerson算法。首先定義一條邊的殘留容量是容量減去現(xiàn)有流，由殘留容量標(biāo)示的網(wǎng)絡(luò)稱為殘留網(wǎng)絡(luò)。再定義增廣路徑是殘留網(wǎng)絡(luò)中從源點(diǎn)s到匯點(diǎn)t的一條路徑。Ford-Fulkerson算法是一個(gè)迭代過(guò)程。每次在殘留網(wǎng)絡(luò)中查找一條增廣路徑，然后把這條增廣路徑中最小的一段殘留容量加到增廣路徑各條邊的流上，更新殘留網(wǎng)絡(luò)繼續(xù)迭代，直到找不到增廣路徑為止。此時(shí)退出迭代，現(xiàn)有流就是最大流。
二分圖有兩部分節(jié)點(diǎn)L和R，各部分內(nèi)部節(jié)點(diǎn)之間沒(méi)有邊，即每條邊的兩個(gè)節(jié)點(diǎn)都一定分屬這兩部分，二分圖的一個(gè)匹配是找到這樣一組邊，使得每個(gè)節(jié)點(diǎn)都只有至多一條邊與其相連。
二分圖的最大匹配問(wèn)題可以轉(zhuǎn)化為網(wǎng)絡(luò)最大流問(wèn)題。增加一個(gè)到所有L中頂點(diǎn)容量均為1的源點(diǎn)s和一個(gè)所有R中頂點(diǎn)到其容量均為1的匯點(diǎn)t，所有L到R中的邊容量也設(shè)置為1，現(xiàn)在查找此網(wǎng)絡(luò)流的最大流就等同于求此二分圖的最大匹配。
poj 2536
http://poj.org/problem?id=2536
| 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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | /*網(wǎng)絡(luò)流的做法*/ #include <iostream> #include <vector> #include <queue> #include <cmath> #include <cstring> using namespace std; #define N 205 #define MAX 1000000 int capacity[N][N] = {0}; int r_capcity[N][N] = {0}; int fluid[N][N] = {0}; int flag_for_bfs[N][N] = {0}; int s,t; int bfs_findP(vector<int>& p,int numV) { ????p.clear(); ????queue<int> q; ????int checked[N] = {0}; ????q.push(s); ????checked[s] = 1; ????int pre[N]; ????memset(pre,-1,sizeof(pre)/sizeof(int)); ????int cur; ????while (!q.empty()) { ????????cur = q.front(); ????????q.pop(); ????????if (cur == t) { ????????????break; ????????} ?? ????????for (int i = 0; i < numV; i++) { ????????????if (checked[i] == 0 && cur != i && r_capcity[cur][i] > 0) { ????????????????q.push(i); ????????????????checked[i] = 1; ????????????????pre[i] = cur; ????????????} ????????} ????} ????if (cur != t) { ????????return -1; ????} ????int i = pre[cur]; ????p.insert(p.begin(),cur); ????while (i != s) { ????????p.insert(p.begin(),i); ????????i = pre[i]; ????} ????return 0; } ?int max_fluid(int numV) { ????for (int i = 0; i < numV; i++) { ????????for (int j = 0; j < numV; j++) { ????????????fluid[i][j] = 0; ????????????r_capcity[i][j] = capacity[i][j] - fluid[i][j]; ????????} ????} ????vector<int> p; ????int r_cap = MAX; ????int key_i = -1,key_j = -1; ????while (bfs_findP(p,numV) != -1) { ????????r_cap = r_capcity[s][p[0]]; ????????for (int i = 0; i < p.size()-1; i++) { ????????????if (r_capcity[p[i]][p[i+1]] < r_cap) { ????????????????r_cap = r_capcity[p[i]][p[i+1]]; ????????????????key_i = p[i]; ????????????????key_j = p[i+1]; ????????????} ????????} ????????fluid[s][p[0]] += r_cap; ????????fluid[p[0]][s] = -fluid[s][p[0]]; ????????for (int i = 0; i < p.size()-1; i++) { ????????????fluid[p[i]][p[i+1]] = fluid[p[i]][p[i+1]] + r_cap; ????????????fluid[p[i+1]][p[i]] = -fluid[p[i]][p[i+1]]; ????????} ????????for (int i = 0; i < numV; i++) { ????????????for (int j = 0; j < numV; j++) { ????????????????r_capcity[i][j] = capacity[i][j] - fluid[i][j]; ????????????} ????????} ????} ????int ans = 0; ????for (int i = 0; i < numV; i++) { ????????if (s != i && fluid[s][i] > 0) { ????????????ans += fluid[s][i]; ????????} ????} ????return ans; } ?double distance(double x1,double y1,double x2,double y2) { ????return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)); } ?int main() { ????int n,m,S,V; ????double gophers[105][2],holes[105][2]; ?? ????while (cin>>n) { ????????cin>>m>>S>>V; ????????for (int i = 0; i < n; i++) { ????????????cin>>gophers[i][0]>>gophers[i][1]; ????????} ????????for (int i = 0; i < m; i++) { ????????????cin>>holes[i][0]>>holes[i][1]; ????????} ????????for (int i = 0; i < N; i++) { ????????????for (int j = 0; j < N; j++) { ????????????????capacity[i][j] = 0; ????????????} ????????} ????????int numV = m + n + 2; ????????s = 0; ????????t = m + n + 1; ????????for (int i = 1; i <= n; i++) { ????????????capacity[0][i] = 1; ????????} ????????for (int i = n+1; i <= n+m; i++) { ????????????capacity[i][t] = 1; ????????} ????????for (int i = 1; i <= n; i++) { ????????????for (int j = n+1; j <= n+m; j++) { ????????????????if (distance(gophers[i-1][0],gophers[i-1][1],holes[j-n-1][0],holes[j-n-1][1]) <= V*S) { ????????????????????capacity[i][j] = 1; ????????????????} ????????????} ????????} ????????cout<<n - max_fluid(numV)<<endl; ????} ????return 0; } |
下面再來(lái)講一下：最大匹配&最小邊覆蓋&最小路徑覆蓋&最小頂點(diǎn)覆蓋&最大獨(dú)立集&最大團(tuán)之間的關(guān)系。
【無(wú)向圖的最大獨(dú)立數(shù)】: 從V個(gè)頂點(diǎn)中選出k個(gè)頂，使得這k個(gè)頂互不相鄰。那么最大的k就是這個(gè)圖的最大獨(dú)立數(shù)。
【無(wú)向圖的最大團(tuán)】:? 從V個(gè)頂點(diǎn)選出k個(gè)頂，使得這k個(gè)頂構(gòu)成一個(gè)完全圖，即該子圖任意兩個(gè)頂都有直接的邊。
【最小路徑覆蓋(原圖不一定是二分圖，但必須是有向圖，拆點(diǎn)構(gòu)造二分圖)】：在圖中找一些路徑，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條路徑與之關(guān)聯(lián)。最小路徑覆蓋 = |V| – 最大匹配數(shù)
【最小邊覆蓋(原圖是二分圖)】：在圖中找一些邊，使之覆蓋了圖中所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一條邊與之關(guān)聯(lián)。最小邊覆蓋 = 最大獨(dú)立集 = |V| – 最大匹配數(shù)
【最小頂點(diǎn)覆蓋】：用最少的點(diǎn)（左右兩邊集合的點(diǎn)）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)。
性質(zhì)：
最大團(tuán) = 補(bǔ)圖的最大獨(dú)立集=|V|-|最大匹配數(shù)|（補(bǔ)圖）；
最小邊覆蓋 = 二分圖最大獨(dú)立集 = |V| – 最小頂點(diǎn)覆蓋=|V|-最大匹配數(shù)
最小路徑覆蓋 = |V| – 最大匹配數(shù)
最小頂點(diǎn)覆蓋 = 最大匹配數(shù)
最小頂點(diǎn)覆蓋 + 最大獨(dú)立數(shù) = |V|
最小割 = 最小點(diǎn)權(quán)覆蓋集 = 點(diǎn)權(quán)和 – 最大點(diǎn)權(quán)獨(dú)立集
求最大權(quán)匹配問(wèn)題要用到KM算法。（詳見(jiàn)小康學(xué)長(zhǎng)模板的53頁(yè)）.
以下是一些例題：
1、Poj_1274（求最大匹配）
Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Input
The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.
Output
For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
Sample Input
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
Sample Output
4
代碼：
| 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 | #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=300; int n1,n2; int _map[N][N]; bool vis[N]; int llink[N]; int find(int x) { ????int i; ????for(i=1; i<=n2; i++) { ????????if(_map[x][i]&&!vis[i]) { ????????????vis[i]=true; ????????????if(llink[i]==-1||find(llink[i])) { ????????????????llink[i]=x; ????????????????return true; ????????????} ????????} ????} ????return false; } int mach() { ????int ans=0; ????memset(llink,-1,sizeof(llink)); ????for(int i=1; i<=n1; i++) { ????????memset(vis,false,sizeof(vis)); ????????if(find(i)) { ????????????ans++; ????????} ????} ????return ans; } int main() { ????int n,m; ????int num; ????int b; ????while(~scanf("%d%d",&n,&m)) { ????????memset(_map,0,sizeof(_map)); ????????for(int i=1; i<=n; i++) { ????????????scanf("%d",&num); ????????????for(int j=0; j<num; j++) { ????????????????scanf("%d",&b); ????????????????_map[i][b]=1; ????????????} ????????} ????????n1=n; ????????n2=m; ????????printf("%d\n",mach()); ????} ????return 0; } |
2、poj_1325（最小頂點(diǎn)覆蓋，也就是最大匹配（開(kāi)始時(shí)機(jī)器是處于開(kāi)機(jī)狀態(tài)的，都是mode_0））
As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, …, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, … , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.
Input
The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.
The input will be terminated by a line containing a single zero.
Output
The output should be one integer per line, which means the minimal times of restarting machine.
Sample Input
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output
3
| 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 | #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=1006; int n1,n2; int _map[N][N]; bool vis[N]; int llink[N]; int find(int x) { ????int i; ????for(i=0; i<n2; i++) { ????????if(_map[x][i]&&!vis[i]) { ????????????vis[i]=true; ????????????if(llink[i]==-1||find(llink[i])) { ????????????????llink[i]=x; ????????????????return true; ????????????} ????????} ????} ????return false; } int mach() { ????int ans=0; ????memset(llink,-1,sizeof(llink)); ????for(int i=0; i<n1; i++) { ????????memset(vis,false,sizeof(vis)); ????????if(find(i)) { ????????????ans++; ????????} ????} ????return ans; } int main() { ????int n,m; ????int k; ????int job,x,y; ????while(~scanf("%d",&n)) { ????????if(n==0) { ????????????break; ????????} ????????scanf("%d%d",&m,&k); ????????memset(_map,0,sizeof(_map)); ?? ????????for(int i=1; i<=k; i++) { ????????????scanf("%d %d %d",&job,&x,&y); ????????????if(x!=0&&y!=0) { ????????????????_map[x][n+y]=1; ????????????} ????????} ????????n1=n; ????????n2=m+n; ????????int ans1=mach(); ????????printf("%d\n",ans1);; ????} ????return 0; } |
3、poj_1422（最大獨(dú)立集）
Air Raid
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 6721 Accepted: 4001
Description
Consider a town where all the streets are one-way and each street leads from one intersection to another. It is also known that starting from an intersection and walking through town’s streets you can never reach the same intersection i.e. the town’s streets form no cycles.
With these assumptions your task is to write a program that finds the minimum number of paratroopers that can descend on the town and visit all the intersections of this town in such a way that more than one paratrooper visits no intersection. Each paratrooper lands at an intersection and can visit other intersections following the town streets. There are no restrictions about the starting intersection for each paratrooper.
Input
Your program should read sets of data. The first line of the input file contains the number of the data sets. Each data set specifies the structure of a town and has the format:
no_of_intersections
no_of_streets
S1 E1
S2 E2
……
Sno_of_streets Eno_of_streets
The first line of each data set contains a positive integer no_of_intersections (greater than 0 and less or equal to 120), which is the number of intersections in the town. The second line contains a positive integer no_of_streets, which is the number of streets in the town. The next no_of_streets lines, one for each street in the town, are randomly ordered and represent the town’s streets. The line corresponding to street k (k <= no_of_streets) consists of two positive integers, separated by one blank: Sk (1 <= Sk <= no_of_intersections) – the number of the intersection that is the start of the street, and Ek (1 <= Ek <= no_of_intersections) – the number of the intersection that is the end of the street. Intersections are represented by integers from 1 to no_of_intersections.
There are no blank lines between consecutive sets of data. Input data are correct.
Output
The result of the program is on standard output. For each input data set the program prints on a single line, starting from the beginning of the line, one integer: the minimum number of paratroopers required to visit all the intersections in the town.
Sample Input
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
Sample Output
2
1
| 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 | #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; const int N=1060; int n1,n2; int _map[N][N]; bool vis[N]; int llink[N]; ?int find(int x) { ????int i; ????for(i=1; i<=n2; i++) { ????????if(_map[x][i]&&!vis[i]) { ????????????vis[i]=true; ????????????if(llink[i]==-1||find(llink[i])) { ????????????????llink[i]=x; ????????????????return true; ????????????} ????????} ????} ????return false; } int mach() { ????int ans=0; ????memset(llink,-1,sizeof(llink)); ????for(int i=1; i<=n1; i++) { ????????memset(vis,false,sizeof(vis)); ????????if(find(i)) { ????????????ans++; ????????} ????} ????return ans; } ?int main() { ????int n,k; ????int T; ????int x,y; ????scanf("%d",&T); ????while(T--) { ????????scanf("%d%d",&n,&k); ????????memset(_map,0,sizeof(_map)); ????????for(int i=1; i<=k; i++) { ????????????scanf("%d%d",&x,&y); ????????????_map[x][y]=1; ????????} ????????n1=n; ????????n2=n; ????????printf("%d\n",n-mach()); ????} ????return 0; } |
4、hdu_2255(最大權(quán)匹配的KM算法)可以直接用小康學(xué)長(zhǎng)的模板
傳說(shuō)在遙遠(yuǎn)的地方有一個(gè)非常富裕的村落,有一天,村長(zhǎng)決定進(jìn)行制度改革：重新分配房子。
這可是一件大事,關(guān)系到人民的住房問(wèn)題啊。村里共有n間房間,剛好有n家老百姓,考慮到每家都要有房住（如果有老百姓沒(méi)房子住的話，容易引起不安定因素），每家必須分配到一間房子且只能得到一間房子。
另一方面,村長(zhǎng)和另外的村領(lǐng)導(dǎo)希望得到最大的效益,這樣村里的機(jī)構(gòu)才會(huì)有錢(qián).由于老百姓都比較富裕,他們都能對(duì)每一間房子在他們的經(jīng)濟(jì)范圍內(nèi)出一定的價(jià)格,比如有3間房子,一家老百姓可以對(duì)第一間出10萬(wàn),對(duì)第2間出2萬(wàn),對(duì)第3間出20萬(wàn).(當(dāng)然是在他們的經(jīng)濟(jì)范圍內(nèi)).現(xiàn)在這個(gè)問(wèn)題就是村領(lǐng)導(dǎo)怎樣分配房子才能使收入最大.(村民即使有錢(qián)購(gòu)買(mǎi)一間房子但不一定能買(mǎi)到,要看村領(lǐng)導(dǎo)分配的).
Input
輸入數(shù)據(jù)包含多組測(cè)試用例，每組數(shù)據(jù)的第一行輸入n,表示房子的數(shù)量(也是老百姓家的數(shù)量)，接下來(lái)有n行,每行n個(gè)數(shù)表示第i個(gè)村名對(duì)第j間房出的價(jià)格(n<=300)。
Output
請(qǐng)對(duì)每組數(shù)據(jù)輸出最大的收入值，每組的輸出占一行。
Sample Input
2
100 10
15 23
Sample Output
123
| 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 | #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; typedef long long ll; #define inf (int)1e10 #define maxn 350 int edge[maxn][maxn];//鄰接矩陣 int du[maxn],dv[maxn];//可行頂標(biāo) int head[maxn];//匹配節(jié)點(diǎn)的父節(jié)點(diǎn) bool visu[maxn],visv[maxn];//判斷是否在交錯(cuò)樹(shù)上 int uN;//匹配點(diǎn)的個(gè)數(shù) int slack[maxn];//松弛數(shù)組 bool dfs(int u) { ????visu[u]=true; ????for(int v=0; v<uN; v++) ????????if(!visv[v]) { ????????????int t=du[u]+dv[v]-edge[u][v]; ????????????if(t==0) { ????????????????visv[v]=true; ????????????????if(head[v]==-1||dfs(head[v])) { ????????????????????head[v]=u; ????????????????????return true; ????????????????} ????????????} else slack[v]=min(slack[v],t); ????????} ????return false; } int KM() { ????memset(head,-1,sizeof(head)); ????memset(du,0,sizeof(du)); ????memset(dv,0,sizeof(dv)); ????for(int u=0; u<uN; u++) ????????for(int v=0; v<uN; v++) ????????????du[u]=max(du[u],edge[u][v]); ????for(int u=0; u<uN; u++) { ????????for(int i=0; i<uN; i++)slack[i]=inf; ????????while(true) { ????????????memset(visu,0,sizeof(visu)); ????????????memset(visv,0,sizeof(visv)); ????????????if(dfs(u))break; ????????????int ex=inf; ????????????for(int v=0; v<uN; v++)if(!visv[v]) ????????????????????ex=min(ex,slack[v]); ????????????for(int i=0; i<uN; i++) { ????????????????if(visu[i])du[i]-=ex; ????????????????if(visv[i])dv[i]+=ex; ????????????????else slack[i]-=ex; ????????????} ????????} ????} ????int ans=0; ????for(int u=0; u<uN; u++) ????????ans+=edge[head[u]][u]; ????return ans; } int main() { //read; ??? while(~scanf("%d",&uN)) { ????????int sum=0; ????????for(int i=0; i<uN; i++) ????????????for(int j=0; j<uN; j++) { ????????????????scanf("%d",&edge[i][j]); ????????????????sum+=edge[i][j]; ????????????} ????????printf("%d\n",KM()); ????} ????return 0; } |
5、hdu_2389 (用Hopcroft-Karp做，用匈牙利算法好像會(huì)TLE；)
http://acm.hdu.edu.cn/showproblem.php?pid=2389
You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour?
Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however.
Input
The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= si <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.
Output
For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.
Sample Input
2
1
2
1 0 3
3 0 3
2
4 0
6 0
1
2
1 1 2
3 3 2
2
2 2
4 4
Sample Output
Scenario #1:
2
Scenario #2:
2
| 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 | #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<vector> using namespace std; #define inf (int)1e10; const int N=50001; int headU[N],headV[N]; int du[N],dv[N]; int uN,vN; vector<int >vec[N]; bool bfs() { ????queue<int>q; ????int dis=inf; ????memset(du,0,sizeof(du)); ????memset(dv,0,sizeof(dv)); ????for(int i=1; i<=uN; i++) ????????if(headU[i]==-1)q.push(i); ????while(!q.empty()) { ????????int u=q.front(); ????????q.pop(); ????????if(du[u]>dis)break; ????????for(int i=0; i<vec[u].size(); i++) ????????????if(!dv[vec[u][i]]) { ????????????????dv[vec[u][i]]=du[u]+1; ????????????????if(headV[vec[u][i]]==-1)dis=dv[vec[u][i]]; ????????????????else { ????????????????????du[headV[vec[u][i]]]=dv[vec[u][i]]+1; ????????????????????q.push(headV[vec[u][i]]); ????????????????} ????????????} ????} ????return dis!=inf; } bool dfs(int u) { ????for(int i=0; i<vec[u].size(); i++) ????????if(dv[vec[u][i]]==du[u]+1) { ????????????dv[vec[u][i]]=0; ????????????if(headV[vec[u][i]]==-1||dfs(headV[vec[u][i]])) { ????????????????headU[u]=vec[u][i]; ????????????????headV[vec[u][i]]=u; ????????????????return 1; ????????????} ????????} ????return 0; } int Hopcroft() { ????memset(headU,-1,sizeof(headU)); ????memset(headV,-1,sizeof(headV)); ????int ans=0; ????while(bfs()) ????????for(int i=1; i<=uN; i++) ????????????if(headU[i]==-1&&dfs(i))ans++; ????return ans; } struct node { ????double x; ????double y; ????double speed; }; node guest[3001]; ?struct node1 { ????double x; ????double y; }; node1 umb[3001]; double dis(node a,node1 b) { ????return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } ?int main() { ????int T; ????int n,m; ????int x,y; ????double ttime; ????while(~scanf("%d",&T)) { ????????for(int t=1; t<=T; t++) { ????????????for(int i=0; i<N; i++)vec[i].clear(); ????????????scanf("%lf",&ttime); ????????????scanf("%d",&n); ????????????for(int i=1; i<=n; i++) { ????????????????scanf("%lf%lf%lf",&guest[i].x,&guest[i].y,&guest[i].speed); ????????????} ????????????scanf("%d",&m); ????????????for(int i=1; i<=m; i++) { ????????????????scanf("%lf%lf",&umb[i].x,&umb[i].y); ????????????} ????????????for(int i=1; i<=n; i++) { ????????????????for(int j=1; j<=m; j++) { ????????????????????if(dis(guest[i],umb[j])<=guest[i].speed*ttime) { ????????????????????????vec[i].push_back(j); ????????????????????} ????????????????} ????????????} ????????????printf("Scenario #%d:\n",t); ????????????uN=n; ????????????vN=m; ????????????printf("%d\n\n",Hopcroft()); ????????} ????} ????return 0; } |
6、poj_2226（最小頂點(diǎn)覆蓋，構(gòu)圖比較麻煩）
http://poj.org/problem?id=2226
7.hdu_2444(判斷二分圖+二分匹配)
http://acm.hdu.edu.cn/showproblem.php?pid=2444
8、hdu_2413(二分+二分匹配)
http://acm.hdu.edu.cn/showproblem.php?pid=2413
9、ACdream 1056(判斷是否是二分圖)
http://acdream.info/problem?pid=1056
10、hnu 12939（二分圖最小頂點(diǎn)覆蓋）
http://acm.hnu.cn/online/?action=problem&type=show&id=12939&courseid=279
總結(jié)
