當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

二分图最大匹配总结

發(fā)布時間：2025/7/14 编程问答 9 豆豆

生活随笔收集整理的這篇文章主要介紹了二分图最大匹配总结小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

hdoj1528

二分匹配模版；

代碼：

1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 #include<math.h> 6 using namespace std; 7 #define N 220 8 9 int n, maps[N][N], vis[N], used[N]; 10 11 struct node 12 { 13 int v,s;///v是紙牌的價值，s類型1:梅花 2:方塊 3:黑桃 4:紅桃；;;;; 14 } a[N], b[N]; 15 16 void change(char s[], node &a)///傳入地址才能改變它的值； 17 { 18 if(s[0]<='9'&&s[0]>='2')a.v=s[0]-'0'; 19 if(s[0]=='A')a.v=14;///A是最大的牌；；；；； 20 if(s[0]=='T')a.v=10; 21 if(s[0]=='J')a.v=11; 22 if(s[0]=='Q')a.v=12; 23 if(s[0]=='K')a.v=13; 24 25 if(s[1]=='H')a.s=4; 26 if(s[1]=='S')a.s=3; 27 if(s[1]=='D')a.s=2; 28 if(s[1]=='C')a.s=1; 29 } 30 bool Find(int u) 31 { 32 for(int i=1; i<=n; i++) 33 { 34 if(!vis[i] && maps[u][i]) 35 { 36 vis[i]=1; 37 if(!used[i] || Find(used[i])) 38 { 39 used[i]=u; 40 return true; 41 } 42 } 43 } 44 return false; 45 } 46 int main() 47 { 48 int T; 49 char s[11]; 50 scanf("%d", &T); 51 while(T--) 52 { 53 memset(a, 0, sizeof(a)); 54 memset(b, 0, sizeof(b)); 55 memset(maps, 0, sizeof(maps)); 56 memset(used, 0, sizeof(used)); 57 scanf("%d", &n); 58 for(int i=1; i<=n; i++) 59 { 60 scanf("%s", s); 61 change(s, a[i]); 62 } 63 for(int i=1; i<=n; i++) 64 { 65 scanf("%s", s); 66 change(s, b[i]); 67 for(int j=1; j<=n; j++)///建立b和a的關系，當為1時說明第二個人的那張牌大一第一個人的那張牌； 68 { 69 if(b[i].v>a[j].v) 70 maps[i][j] = 1; 71 if(b[i].v==a[j].v && b[i].s>a[j].s) 72 maps[i][j] = 1; 73 } 74 } 75 for(int i=1;i<=n;i++) 76 for(int j=1;j<=n;j++) 77 if(maps[i][j])printf("maps[%d][%d]=1\n",i,j); 78 int ans=0; 79 for(int i=1; i<=n; i++) 80 { 81 memset(vis, 0, sizeof(vis)); 82 if(Find(i)) 83 ans++;; 84 for(int t=1;t<=n;t++)printf("%d ",used[t]);puts(""); 85 } 86 printf("%d\n", ans); 87 } 88 return 0; 89 } 90 /*********/ 91 3 92 5 93 2H 3H 4H 5H 6H 94 2H 3H 4H 5H 6H 95 5 96 2H 3H 4H 5H 6H 97 6H 5H 4H 3H 2H 98 /*********/

二分圖匹配（匈牙利算法）

1。一個二分圖中的最大匹配數(shù)等于這個圖中的最小點覆蓋數(shù)

K?nig定理是一個二分圖中很重要的定理，它的意思是，一個二分圖中的最大匹配數(shù)等于這個圖中的最小點覆蓋數(shù)。如果你還不知道什么是最小點覆蓋，我也在這里說一下：假如選了一個點就相當于覆蓋了以它為端點的所有邊，你需要選擇最少的點來覆蓋所有的邊。

2。最小路徑覆蓋=最小路徑覆蓋＝｜G｜－最大匹配數(shù)

?在一個N*N的有向圖中，路徑覆蓋就是在圖中找一些路經(jīng)，使之覆蓋了圖中的所有頂點，
?且任何一個頂點有且只有一條路徑與之關聯(lián)；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，
?那么恰好可以經(jīng)過圖中的每個頂點一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個弱連通子集．

由上面可以得出：

?1.一個單獨的頂點是一條路徑；
?2.如果存在一路徑p1,p2,......pk，其中p1 為起點，pk為終點，那么在覆蓋圖中，頂點p1,p2,......pk不再與其它的
?? 頂點之間存在有向邊．

最小路徑覆蓋就是找出最小的路徑條數(shù)，使之成為G的一個路徑覆蓋．

?路徑覆蓋與二分圖匹配的關系：最小路徑覆蓋＝｜G｜－最大匹配數(shù)；

3。二分圖最大獨立集=頂點數(shù)-二分圖最大匹配

獨立集：圖中任意兩個頂點都不相連的頂點集合。

二分圖模板：

模板一：匈牙利算法

/* ************************************************************************** //二分圖匹配（匈牙利算法的DFS實現(xiàn)） //初始化：g[][]兩邊頂點的劃分情況 //建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配 //g沒有邊相連則初始化為0 //uN是匹配左邊的頂點數(shù)，vN是匹配右邊的頂點數(shù) //調(diào)用：res=hungary();輸出最大匹配數(shù) //優(yōu)點：適用于稠密圖，DFS找增廣路，實現(xiàn)簡潔易于理解 //時間復雜度:O(VE) //***************************************************************************/ //頂點編號從0開始的 const int MAXN=510; int uN,vN;//u,v數(shù)目 int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u)//從左邊開始找增廣路徑 { ??? int v; ??? for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改 ????? if(g[u][v]&&!used[v]) ????? { ????????? used[v]=true; ????????? if(linker[v]==-1||dfs(linker[v])) ????????? {//找增廣路，反向 ????????????? linker[v]=u; ??? ??????????return true; ????????? } ????? } ??? return false;//這個不要忘了，經(jīng)常忘記這句 } int hungary() { ??? int res=0; ??? int u; ??? memset(linker,-1,sizeof(linker)); ??? for(u=0;u<uN;u++) ??? { ??????? memset(used,0,sizeof(used)); ??????? if(dfs(u)) res++; ??? } ???return res; } //******************************************************************************/

模板二： Hopcroft-Carp算法

這個算法比匈牙利算法的時間復雜度要小，大數(shù)據(jù)可以采用這個算法

/* ********************************************* 二分圖匹配（Hopcroft-Carp的算法）。初始化：g[][]鄰接矩陣調(diào)用：res=MaxMatch();? Nx,Ny要初始化！！！時間復雜大為 O(V^0.5 E) ? 適用于數(shù)據(jù)較大的二分匹配需要ｑｕｅｕｅ頭文件 ********************************************** */ const int MAXN=3000; const int INF=1<<28; int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny; int dx[MAXN],dy[MAXN],dis; bool vst[MAXN]; bool searchP() { ???queue<int>Q; ??? dis=INF; ??? memset(dx,-1,sizeof(dx)); ??? memset(dy,-1,sizeof(dy)); ??? for(int i=0;i<Nx;i++) ??????? if(Mx[i]==-1) ??????? { ??????????? Q.push(i); ??????????? dx[i]=0; ??????? } ??? while(!Q.empty()) ??? { ??????? int u=Q.front(); ? ??????Q.pop(); ??????? if(dx[u]>dis)? break; ??????? for(int v=0;v<Ny;v++) ??????????? if(g[u][v]&&dy[v]==-1) ??????????? { ??????????????? dy[v]=dx[u]+1; ??????????????? if(My[v]==-1)? dis=dy[v]; ??????????????? else ??????????????? { ??????????????????? dx[My[v]]=dy[v]+1; ??????????????????? Q.push(My[v]); ??????????????? } ??????????? } ??? } ??? return dis!=INF; } bool DFS(int u) { ??? for(int v=0;v<Ny;v++) ?????? if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1) ?????? { ?????????? vst[v]=1; ?????????? if(My[v]!=-1&&dy[v]==dis) continue; ?????????? if(My[v]==-1||DFS(My[v])) ?????????? { ?????????????? My[v]=u; ?????????????? Mx[u]=v; ?????????????? return 1; ?????????? } ?????? } ??? return 0; } int MaxMatch() { ??? int res=0; ??? memset(Mx,-1,sizeof(Mx)); ??? memset(My,-1,sizeof(My)); ??? while(searchP()) ??? { ??????? memset(vst,0,sizeof(vst)); ??????? for(int i=0;i<Nx;i++) ????????? if(Mx[i]==-1&&DFS(i))? res++; ??? } ??? return res; } //**************************************************************************/

下面的程序效率很高。是用vector實現(xiàn)鄰接表的匈牙利算法。

處理點比較多的效率很高。1500的點都沒有問題

HDU 1054

用STL中的vector建立鄰接表實現(xiàn)匈牙利算法

效率比較高

?G++? 578ms? 580K

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<vector>

using namespace std;

//************************************************

const int MAXN=1505;//這個值要超過兩邊個數(shù)的較大者，因為有l(wèi)inker

int linker[MAXN];

bool used[MAXN];

vector<int>map[MAXN];

int uN;

bool dfs(int u)

{

??? for(int i=0;i<map[u].size();i++)

??? {

??????? if(!used[map[u][i]])

??????? {

??????????? used[map[u][i]]=true;

??????????? if(linker[map[u][i]]==-1||dfs(linker[map[u][i]]))

??????????? {

??????????????? linker[map[u][i]]=u;

??????????????? return true;

??????????? }

??????? }

??? }

??? return false;

}

inthungary()

{

??? int u;

??? int res=0;

? ??memset(linker,-1,sizeof(linker));

??? for(u=0;u<uN;u++)

??? {

??????? memset(used,false,sizeof(used));

??????? if(dfs(u)) res++;

??? }

??? return res;

}

//*****************************************************

int main()

{

??? int u,k,v;

??? int n;

??? while(scanf("%d",&n)!=EOF)

??? {

??????? for(int i=0;i<MAXN;i++)

?????????? map[i].clear();

??????? for(int i=0;i<n;i++)

??????? {

??????????? scanf("%d:(%d)",&u,&k);

??????????? while(k--)

??????????? {

??????????????? scanf("%d",&v);

??????????????? map[u].push_back(v);

??????????????? map[v].push_back(u);

??????????? }

??????? }

??????? uN=n;

??????? printf("%d\n",hungary()/2);

??? }

??? return 0;

}

例題：

POJ 3020? Antenna Placement

Time Limit: 1000MS	?	Memory Limit: 65536K
Total Submissions: 4739	?	Accepted: 2359

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

7 9

ooo**oooo

**oo*ooo*

o*oo**o**

ooooooooo

*******oo

o*o*oo*oo

*******oo

10 1

Sample Output

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<iostream>

using namespace std;

/* **************************************************************************

//二分圖匹配（匈牙利算法的DFS實現(xiàn)）

//初始化：g[][]兩邊頂點的劃分情況

//建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配

//g沒有邊相連則初始化為0

//uN是匹配左邊的頂點數(shù)，vN是匹配右邊的頂點數(shù)

//調(diào)用：res=hungary();輸出最大匹配數(shù)

//優(yōu)點：適用于稠密圖，DFS找增廣路，實現(xiàn)簡潔易于理解

//時間復雜度:O(VE)

//***************************************************************************/

//頂點編號從0開始的

const int MAXN=510;

int uN,vN;//u,v數(shù)目

int g[MAXN][MAXN];

int linker[MAXN];

bool used[MAXN];

bool dfs(int u)//從左邊開始找增廣路徑

{

??? int v;

??? for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改

????? if(g[u][v]&&!used[v])

????? {

????????? used[v]=true;

????????? if(linker[v]==-1||dfs(linker[v]))

????????? {//找增廣路，反向

????????????? linker[v]=u;

????????????? return true;

????????? }

????? }

??? return false;//這個不要忘了，經(jīng)常忘記這句

}

int hungary()

{

??? int res=0;

??? int u;

??? memset(linker,-1,sizeof(linker));

??? for(u=0;u<uN;u++)

??? {

??????? memset(used,0,sizeof(used));

??????? if(dfs(u)) res++;

??? }

??? return res;

}

//******************************************************************************/

char map[50][50];

int hash[50][50];

int main()

{

??? int T;

??? int h,w;

??? scanf("%d",&T);

??? int tol;

??? while(T--)

??? {

??????? scanf("%d%d",&h,&w);

??????? tol=0;

??????? for(int i=0;i<h;i++)

??????? {

??????????? scanf("%s",&map[i]);

??????????? for(int j=0;j<w;j++)

???????????? if(map[i][j]=='*')

? ?????????????hash[i][j]=tol++;

??????? }

??????? memset(g,0,sizeof(g));

??????? for(int i=0;i<h;i++)

????????? for(int j=0;j<w;j++)

??????????? if(map[i][j]=='*')

??????????? {

??????????????? if(i>0&&map[i-1][j]=='*')g[hash[i][j]][hash[i-1][j]]=1;

?????? ?????????if(i<h-1&&map[i+1][j]=='*') g[hash[i][j]][hash[i+1][j]]=1;

??????????????? if(j>0&&map[i][j-1]=='*')? g[hash[i][j]][hash[i][j-1]]=1;

??????????????? if(j<w-1&&map[i][j+1]=='*')? g[hash[i][j]][hash[i][j+1]]=1;

??????????? }

??????? uN=vN=tol;

???? ???printf("%d\n",tol-hungary()/2);

??? }

??? return 0;

}

Treasure Exploration

Time Limit: 6000MS	?	Memory Limit: 65536K
Total Submissions: 5480	?	Accepted: 2154

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

此題跟普通的路徑覆蓋有點不同。

You should notice that the roads of two different robots may contain some same point.

也就是不同的路徑可以有重復點。

先用floyed求閉包，就是把間接相連的點也連起來。

POJ 2594

求最大獨立集=頂點數(shù)-最大匹配數(shù)

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

using namespace std;

/* **************************************************************************

//二分圖匹配（匈牙利算法的DFS實現(xiàn)）

//初始化：g[][]兩邊頂點的劃分情況

//建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配

//g沒有邊相連則初始化為0

//uN是匹配左邊的頂點數(shù)，vN是匹配右邊的頂點數(shù)

//調(diào)用：res=hungary();輸出最大匹配數(shù)

//優(yōu)點：適用于稠密圖，DFS找增廣路，實現(xiàn)簡潔易于理解

//時間復雜度:O(VE)

//***************************************************************************/

//頂點編號從0開始的

const int MAXN=510;

int uN,vN;//u,v數(shù)目

int g[MAXN][MAXN];

int linker[MAXN];

bool used[MAXN];

bool dfs(int u)//從左邊開始找增廣路徑

{

??? int v;

??? for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改

????? if(g[u][v]&&!used[v])

????? {

????????? used[v]=true;

????????? if(linker[v]==-1||dfs(linker[v]))

????????? {//找增廣路，反向

????????????? linker[v]=u;

????????????? return true;

????????? }

????? }

??? return false;//這個不要忘了，經(jīng)常忘記這句

}

int hungary()

{

??? int res=0;

??? int u;

??? memset(linker,-1,sizeof(linker));

??? for(u=0;u<uN;u++)

??? {

??????? memset(used,0,sizeof(used));

??????? if(dfs(u)) res++;

??? }

??? return res;

}

//******************************************************************************/

void floyed(int n)//求傳遞閉包

{

??? for(int i=0;i<n;i++)

????? for(int j=0;j<n;j++)

????? {

????????? if(g[i][j]==0)

????????? {

????????????? for(int k=0;k<n;k++)

????????????? {

????????????????? if(g[i][k]==1&&g[k][j]==1)

????????????????? {

????????????????????? g[i][j]=1;

????????????????????? break;

????????????????? }

????????????? }

????????? }

????? }

}

int main()

{

??? int n,m;

??? int u,v;

??? while(scanf("%d%d",&n,&m))

??? {

??????? if(n==0&&m==0)break;

??????? uN=vN=n;

??????? memset(g,0,sizeof(g));

??????? while(m--)

??????? {

??????????? scanf("%d%d",&u,&v);

??????????? u--;v--;

??????????? g[u][v]=1;

??????? }

??????? floyed(n);

??????? printf("%d\n",n-hungary());

??? }

??? return 0;

}

總結

以上是生活随笔為你收集整理的二分图最大匹配总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： FineUI（开源版）v4.2.2发布（
下一篇：【转】使用Core Graphics绘画