锐客网

  1. 首页 > it技术 > >

二分图最大匹配例题

做了一些关于二分图最大匹配的题目，再次进行一些总结。在做题过程中也学到了不少的方法技巧。
首先要谈一谈关于二分图的构建问题，二分图匹配类问题的求解是简单的，我认为比较难的部分在于如何想到二分图最大匹配，则需要对该类问题的特点有一定的认识，其次，如何构建二分图对原问题进行抽象非常关键。
这里推荐几个讲解二分图比较详细的博客：
http://dsqiu.iteye.com/blog/1689505
http://blog.csdn.net/xuguangsoft/article/details/7861988
http://www.cnblogs.com/penseur/
在百度文库里发现了关于二分图建图的一些注意点的文章，写的很不错。掌握一定的二分图建图技巧可以让我们事半功倍。
该文章叫《二分图最大匹配及常用建图方法》，文中介绍了几种常见的二分图建图方法，第一种行列匹配法，则在下面的例题中也出现了，由于我先看的这篇文章，所以能够较容易的想到用行列匹配法。第二种是黑白染色法，这个也很常见。第三种是反建图法（与集合求补集的思想相同，主要定理支撑是：二分图点集大小=二分图最大独立集大小+二分图最大匹配数）。第四种是拆点法，将一个点拆成两个点或多个点，这是一种假想的拆分，目的是满足二分图的条件。第五种是增行增列法。在题目中比较常见的是前四种。
下面通过一些例题进行小结。


例题1：HDU 1083&&POJ 1469

Courses Time Limit: 20000/10000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4034Accepted Submission(s): 1928


Problem Description Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions:

. every student in the committee represents a different course (a student can represent a course if he/she visits that course)

. each course has a representative in the committee

Your program should read sets of data from a text file. The first line of the input file contains the number of the data sets. Each data set is presented in the following format:

P N
Count1 Student1 1 Student1 2 ... Student1 Count1
Count2 Student2 1 Student2 2 ... Student2 Count2
......
CountP StudentP 1 StudentP 2 ... StudentP CountP

The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses . from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you'll find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N.

There are no blank lines between consecutive sets of data. Input data are correct.

The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.

An example of program input and output:
Sample Input


2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Sample Output

YES NO
Source Southeastern Europe 2000
Recommend We have carefully selected several similar problems for you:10682444206311501281这道题是比较典型的二分图匹配，而且建图也比较好建。这道题直接给出了课程和学生这两个集合，而且这两个集合内部相互独立。学生选课构成一种关系。因此我们在学生与课程这两个集合的对应点之间进行连边操作。边代表的含义是学生选课。在建图的时候一定要清楚图的点集和边集分别代表的含义。这一点很重要。而本题比较常规，因此该重要性体现不明显。还有一点需要注意的是建图的时候要明确自己构建的二分图是有向图还是无向图，因为是否有向将会影响到最终二分图的匹配数。因此需要格外注意。还需要判断能否构建无向图，是否必须构建无向图等。 这道题由于学生与课程之间的关系存在选与被选的关系，这个关系是相互的。因此是可以构建无向图的。当然我们也可以构建有向图。 下面是二分图最大匹配的代码：
#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int a[310],b[310],vis[310],match[310],p,n; vectorG[505]; bool dfs(int u) { for(int i=0; i




例题2 POJ 3020(最小路径覆盖)

Antenna Placement
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6966 Accepted: 3457

Description
The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.
二分图最大匹配例题
文章图片

Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?

【二分图最大匹配例题】Input
On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1 <= h <= 40 and 0 < w <= 10. Thereafter is a matrix presented, describing the points of interest in Sweden in the form of h lines, each containing w characters from the set ['*','o']. A '*'-character symbolises a point of interest, whereas a 'o'-character represents open space.

Output
For each scenario, output the minimum number of antennas necessary to cover all '*'-entries in the scenario's matrix, on a row of its own. Sample Input
2 7 9 ooo**oooo **oo*ooo* o*oo**o** ooooooooo *******oo o*o*oo*oo *******oo 10 1 * * * o * * * * * *

Sample Output
17 5

Source
Svenskt M?sterskap i Programmering/Norgesmesterskapet 2001
这道题是一道比较经典的最小路径覆盖问题。在说这道题之前，我们首先需要了解最小路径覆盖与最小顶点覆盖之间的区别。这些细微的差别必须搞清楚，否则会导致完全偏离题意。最小路径覆盖是用最少的边来覆盖所有的点，而最小顶点覆盖是用最少的顶点来保证所有的边都与这些顶点相连，即用最少的顶点来覆盖所有的边。这是两个完全不同的方向。而本题中，设立一个基站后，则这个基站可以与它周围相邻的四个点的任意一个点形成一个覆盖区域。而这种覆盖的关系就相当于是在这两个点之间进行连边。而我们需要关注的是要覆盖所有的‘*’。因此只需要考虑‘*’符号之间的关系即可。即该集合内所有点之间的关系，是否具有覆盖关系。而我们最终目的是用边来覆盖所有点，即用最少的边覆盖所有的点。这就顺理成章的与最小路径覆盖问题吻合。其中比较难想的是把这种覆盖四周相邻一点的特点理解为边。从而在‘*’点之间连边。
而本题最有疑问的是为何它是二分图最大匹配？首先我们需要清楚这个图是不是二分图，回答是。而本题使用的二分图建图方法就是拆点法。比如i点与j点间有一条边，而实质上是i与j拆出来的一个j'点相连。这样就出现了两个集合。而这实际上是一种构想。这一点也是非常巧妙的地方。把同一个集合拆分出两个集合进行二分图的最大匹配。最终由定理：最小路径覆盖数=顶点数-最大匹配数（如果是无向图，要除以2）。
参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; char a[50][20]; int b[50][20]; bool vis[500]; vector G[500]; int match[500]; int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; int n,m; bool dfs(int u) { for(int i=0; i=1&&x1<=n&&y1>=1&&y1<=m) { if(a[x1][y1]=='*') { G[b[i][j]].pb(b[x1][y1]); G[b[x1][y1]].pb(b[i][j]); } } } } } } __CLR(match); int ans=0; for(int i=1; i<=num; i++) { CLR(vis); if(dfs(i)) ans++; } printf("%d\n",num-ans/2); for(int i=0; i<500; i++) G[i].clear(); } }




例题3 POJ 2594



Treasure Exploration
Time Limit: 6000MS Memory Limit: 65536K
Total Submissions: 6978 Accepted: 2833

Description
Have you ever read any book about treasure exploration? Have you ever see any film about treasure exploration? Have you ever explored treasure? If you never have such experiences, you would never know what fun treasure exploring brings to you.
Recently, a company named EUC (Exploring the Unknown Company) plan to explore an unknown place on Mars, which is considered full of treasure. For fast development of technology and bad environment for human beings, EUC sends some robots to explore the treasure.
To make it easy, we use a graph, which is formed by N points (these N points are numbered from 1 to N), to represent the places to be explored. And some points are connected by one-way road, which means that, through the road, a robot can only move from one end to the other end, but cannot move back. For some unknown reasons, there is no circle in this graph. The robots can be sent to any point from Earth by rockets. After landing, the robot can visit some points through the roads, and it can choose some points, which are on its roads, to explore. You should notice that the roads of two different robots may contain some same point.
For financial reason, EUC wants to use minimal number of robots to explore all the points on Mars.
As an ICPCer, who has excellent programming skill, can your help EUC? Input
The input will consist of several test cases. For each test case, two integers N (1 <= N <= 500) and M (0 <= M <= 5000) are given in the first line, indicating the number of points and the number of one-way roads in the graph respectively. Each of the following M lines contains two different integers A and B, indicating there is a one-way from A to B (0 < A, B <= N). The input is terminated by a single line with two zeros. Output
For each test of the input, print a line containing the least robots needed. Sample Input
1 0 2 1 1 2 2 0 0 0

Sample Output
1 1 2

Source
POJ Monthly--2005.08.28,Li Haoyuan
这道题是比较奇怪的一道题，与普通的二分图最小路径覆盖不同。首先需要强调的是一般无向图的最小路径覆盖是要保证边覆盖点时，每个点只被覆盖一次，即不能够一个点重复很多次，没有重(chong)点。而本题是有向图的可重点的最小路径覆盖。这就要深入理解关系的定义。这需要一定离散数学的基础。由于这道题给出的就是点之间的路径，我们关注的是一个点能否到达另一个点。而不是去关注这个点到达另一个点需要经过多少个其他的点。关注点的改变让我们重新思考起如何把重(chong)点变成不重(chong)点。直接考虑两个点之间是否连通，是否可以到达，这实质上是把A点途经B点过程中经过的C,D……其特点拆分出来，变成不同的点。这样从A到B经过的点就是不重复的点。那么就可以利用不重点的最小路径覆盖了。但我们最终只关心的是A点能不能到达B点，而中间具体需要经过那些点不需考虑。所以需要求解关系集合的传递闭包，从而明确两点之间是否具有可到达性。有些解题报告中说假定A可以到达B,中途经过的点可以忽略，可以假设直接从上空飞过去。这暗含的实质是拆点的思想方法。
而求解关系矩阵的传递闭包需要用到floyd算法。运用的还是floyd算法的动态规划的特性。关于floyd算法求传递闭包的具体细节及证明在此略掉。
求完了传递闭包，然后就是普通的最小路径覆盖了。
参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x))using namespace std; int n,m; int g[610][610],match[610]; bool vis[610]; void floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(g[i][j]==0) if(g[i][k]==1&&g[k][j]==1) g[i][j]=1; }bool dfs(int u) { for(int i=1; i<=n; i++) { if(g[u][i]&&!vis[i]) { vis[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return true; } } } return false; }int main() {while(~scanf("%d%d",&n,&m)&&n+m) { CLR(g); for(int i=0; i




例题4HDU 1704

Rank Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1179Accepted Submission(s): 439


Problem Description there are N ACMers in HDU team.
ZJPCPC Sunny Cup 2007 is coming, and lcy want to select some excellent ACMers to attend the contest. There have been M matches since the last few days(No two ACMers will meet each other at two matches, means between two ACMers there will be at most one match). lcy also asks"Who is the winner between A and B?" But sometimes you can't answer lcy's query, for example, there are 3 people, named A, B, C.and 1 match was held between A and B, in the match A is the winner, then if lcy asks "Who is the winner between A and B", of course you can answer "A", but if lcy ask "Who is the winner between A and C", you can't tell him the answer.
As lcy's assistant, you want to know how many queries at most you can't tell lcy(ask A B, and ask B A is the same; and lcy won't ask the same question twice).
Input The input contains multiple test cases.
The first line has one integer,represent the number of test cases.
Each case first contains two integers N and M(N , M <= 500), N is the number of ACMers in HDU team, and M is the number of matchs have been held.The following M lines, each line means a match and it contains two integers A and B, means A wins the match between A and B.And we define that if A wins B, and B wins C, then A wins C.
Output For each test case, output a integer which represent the max possible number of queries that you can't tell lcy.
Sample Input

3 3 3 1 2 1 3 2 3 3 2 1 2 2 3 4 2 1 2 3 4
Sample Output

0 0 4 Hint in the case3, if lcy ask (1 3 or 3 1) (1 4 or 4 1) (2 3 or 3 2) (2 4 or 4 2), then you can't tell him who is the winner.
Source 2007省赛集训队练习赛（1）
Recommend lcy|We have carefully selected several similar problems for you:17031700170117061702

这道题是为了练习floyd算法求传递闭包。只需注意一些小细节即可。
参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int t,n,m; int g[605][605]; void floyd() { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(g[j][i]) { for(int k=1; k<=n; k++) { if(g[i][k]) g[j][k]=1; } } } } }int main() {scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); CLR(g); while(m--) { int u,v; scanf("%d%d",&u,&v); g[u][v]=1; } floyd(); int cnt=n*(n-1); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i!=j&&g[i][j]) cnt-=2; } } printf("%d\n",cnt/2); } }










例题5 POJ 3660

Cow Contest
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7320 Accepted: 4051

Description
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
Output
* Line 1: A single integer representing the number of cows whose ranks can be determined

Sample Input
5 5 4 3 4 2 3 2 1 2 2 5

Sample Output
2

Source
USACO 2008 January Silver
这道题还是属于floyd算法求传递闭包的练习。
参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int n,m; int g[110][110]; void floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) if(g[i][k]) { for(int j=1; j<=n; j++) { if(g[k][j]) g[i][j]=1; } }}int main() {while(~scanf("%d%d",&n,&m)) { CLR(g); for(int i=0; i







例题6 HDU 1150&&POJ 1325

Machine Schedule Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6314Accepted Submission(s): 3162


Problem Description 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
Source Asia 2002, Beijing (Mainland China)
Recommend Ignatius.L|We have carefully selected several similar problems for you:10681151128115071528
这道题是比较经典的最小顶点覆盖问题。但是建图比较难想。在本题中需要转换思维。最开始我是把任务当成一个集合，A机器的模式与B机器的模式分别与任务集合进行连边。但是这样操作发现是不对的。原因是A,B机器的模式与任务对应时是或的关系，即从两个机器的两个模式中任选一个。而一旦该模式与任务连了边，那么说明该任务就对应该机器的该模式。这样就无法体现是从A,B两台机器中任选一台机器的模式。而是将A,B之间的关系变成了且，而不是或。
所以要转换思路。由于A,B之间具有独立关系，而且A和B中每次只能选取一个。所以我们可以把A和B集合看成二分图的两个部分，将任务看成它们的边。这样要选取最少的点覆盖所有的边，即覆盖所有的任务。所以属于最小顶点覆盖。
由定理可知，最小顶点覆盖数=二分图最大匹配数
下面是参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; vectorG[210]; int match[1010]; bool vis[210]; bool dfs(int u) { for(int i=0; i




例题7 HDU 1151



Air Raid Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3606Accepted Submission(s): 2368


Problem 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
Source Asia 2002, Dhaka (Bengal)
Recommend Ignatius.L|We have carefully selected several similar problems for you:10681281150715281498

最小路径覆盖问题，用最少的路径访问所有的点。



#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int t,n,m; vectorG[200]; bool vis[200]; int match[200]; bool dfs(int u) { for(int i=0; i






例题8 POJ 2446

Chessboard
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 14263 Accepted: 4436

Description
Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below).
二分图最大匹配例题
文章图片

We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below:
1. Any normal grid should be covered with exactly one card.
2. One card should cover exactly 2 normal adjacent grids.

Some examples are given in the figures below:
二分图最大匹配例题
文章图片

A VALID solution.
二分图最大匹配例题
文章图片

An invalid solution, because the hole of red color is covered with a card.
二分图最大匹配例题
文章图片

An invalid solution, because there exists a grid, which is not covered.
Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above. Input
There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column. Output
If the board can be covered, output "YES". Otherwise, output "NO". Sample Input
4 3 2 2 1 3 3

Sample Output
YES

Hint
二分图最大匹配例题
文章图片

A possible solution for the sample input. Source
POJ Monthly,charlescpp
这道题与之前的POJ 3020题比较类似，方法几乎是相同的。下面是参考代码。
#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int n,m,k; int g[40][40],match[1500]; vectorG[1500]; bool vis[1500]; int dx[]= {0,0,1,-1}; int dy[]= {1,-1,0,0}; bool dfs(int u) { for(int i=0; i=1&&x<=n&&y>=1&&y<=m&&g[x][y]!=-1) { G[g[i][j]].pb(g[x][y]); G[g[x][y]].pb(g[i][j]); } } } } } __CLR(match); int num=0; for(int i=1; i<=cnt; i++) { CLR(vis); if(dfs(i)) num++; } if(num==cnt) printf("YES\n"); else printf("NO\n"); } for(int i=0; i<1500; i++) G[i].clear(); } }





例题 9HDU 2819

Swap Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1710Accepted Submission(s): 572
Special Judge

Problem Description Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?
Input There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.
Output For each test case, the first line contain the number of swaps M. Then M lines follow, whose format is “R a b” or “C a b”, indicating swapping the row a and row b, or swapping the column a and column b. (1 <= a, b <= N). Any correct answer will be accepted, but M should be more than 1000.

If it is impossible to make all the diagonal entries equal to 1, output only one one containing “-1”.

Sample Input

2 0 1 1 0 2 1 0 1 0
Sample Output

1 R 1 2 -1
Source 2009 Multi-University Training Contest 1 - Host by TJU
Recommend gaojie|We have carefully selected several similar problems for you:28182821281728252824

这道题最终是要保证主对角线上的数都为1。我们可以想到通过行列匹配的建图方法进行构建。保证一个行只有一个列为1。进行匹配以后要对match数组进行排序，通过选择排序从而打印出移动的步骤。
本题较难。

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int n; int a[110][110]; int match[110]; bool vis[110]; vectorG[110]; int p1[110],p2[110]; bool dfs(int u) { for(int i=0; i







例题10POJ 1274

The Perfect Stall
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19454 Accepted: 8803

Description
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

Source
USACO 40
标准的二分图最大匹配问题。

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int n,m; int match[210]; bool vis[210]; vectorG[210]; bool dfs(int u) { for(int i=0; i




例题11HDU 1281

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2651Accepted Submission(s): 1547


Problem Description 小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
二分图最大匹配例题
文章图片

Input 输入包含多组数据，
第一行有三个数N、M、K(1
Output 对输入的每组数据，按照如下格式输出：
Board T have C important blanks for L chessmen.

Sample Input

3 3 4 1 2 1 3 2 1 2 2 3 3 4 1 2 1 3 2 1 3 2
Sample Output

Board 1 have 0 important blanks for 2 chessmen. Board 2 have 3 important blanks for 3 chessmen.
Author Gardon
Source 杭电ACM集训队训练赛（VI）
Recommend lcy|We have carefully selected several similar problems for you:15071528149820632444

这道题比较坑，也比较难。题目中的重点边的定义也不甚清晰，可能让人难以理解出题人的意思。
下面引用别人对本题的解读，我觉得本题还是属于比较难的题目。
这题可以看成行与列的二分匹配问题，因为每行每列至多只能放一个棋子。第i行与j列匹配代表棋盘第ｉ行ｊ列这个位置放棋子。那么，棋盘上的点就是二分图的边；“车”的个数就是二分图的最大匹配数。题目的关键是求重要点。现假设最大匹配数为ans，且已经求出某一种匹配策略。
1 ：枚举所有可以放的点，去掉某一点后（这里的点指棋盘上的点，也就是二分图的边），就得到一个新的二分图了
if(新二分图的最大匹配数　=＝　ans）
then这个点不是重要点
else // 即新的二分图达不到ans这个匹配数，那么这个点就是必须放的，否则达不到ans。-->重要边
then计数+1
2 :但是这样枚举效率太低。实际上，删边只需考虑求出的匹配边（因为删除非匹配边得到的匹配数不变）。这样，只需删除ans条边，复杂度就降低了。
再进一步分析，删除一条边以后，没有必要重新求删边后新的二分图的最大匹配，只需检查删边后的匹配中--->可不可以再找到新的增广链就可以了。这样，时间复杂度就进一步降到了。
3 : 这样的优化是不可取的：
在判断是否存在增广路得时候，不能只以删除的匹配边的顶点作起点来找增广路
正确的方法是：以删边后新的二分图的所有未匹配顶点出发做增广，都找不到增广路，匹配不能再增加


总结本题，需要对二分图最大匹配有深刻的认识。二分图最大匹配必须要重点注意的是：如果不存在增广路，即为最大匹配。删掉一条边以后，如果还能找到增广路，那么就能够达到原有的匹配数。因为找到增广路以后对增广路取反以后，边数加1。如果从剩下未匹配的边开始无法找到增广路，那么就说明删边操作后，新的二分图无法达到原有的匹配数。这是二分图最大匹配最实质性的东西。必须深入思考后才能够理解该删边操作寻找增广路做法的合理性。


下面是参考代码：

#include #include #include #include #include #define pb push_back #define CLR(x) memset(x,0,sizeof(x)) #define __CLR(x) memset(x,-1,sizeof(x)) using namespace std; int n,m,k; int mx[110],my[110]; bool vis[110]; int g[110][110]; bool dfs(int u,bool &flag)//引入flag是为了保证在进行删边操作时不改变匹配的对应值 { for(int i=1; i<=m; i++) { if(g[u][i]&&!vis[i]) { vis[i]=1; if(my[i]==-1||dfs(my[i],flag)) { if(flag) { my[i]=u; mx[u]=i; } return true; } } } return false; }int main() { int cas=1; while(~scanf("%d%d%d",&n,&m,&k)) { CLR(g); for(int i=1; i<=k; i++) { int x,y; scanf("%d%d",&x,&y); g[x][y]=1; } __CLR(mx); __CLR(my); int num=0; for(int i=1; i<=n; i++) { if(mx[i]==-1) { CLR(vis); bool f=true; if(dfs(i,f)) num++; }} int ans=0; for(int i=1; i<=n; i++) { if(mx[i]!=-1)//删除匹配边 { int t=mx[i]; mx[i]=-1,my[t]=-1; g[i][t]=0; bool flag=0; for(int j=1; j<=n; j++) { if(mx[j]==-1)//对未匹配点进行搜索 { CLR(vis); bool f=false; if(dfs(j,f)) { flag=1; break; } } } if(!flag) ans++; mx[i]=t; //对匹配边进行恢复 my[t]=i; g[i][t]=1; } } printf("Board %d have %d important blanks for %d chessmen.\n",cas++,ans,num); } }



    推荐阅读


    上一篇：字符集和字符编码

    下一篇：Flink|Flink 框架下scala与java混合编程问题