給定一個二分圖，其中左半部包含n1n1個點（編號1~n1n1），右半部包含n2n2個點（編號1~n2n2），二分圖共包含m條邊，
資料保證任意一條邊的兩個端點都不可能在同一部分中，
請你求出二分圖的最大匹配數，
二分圖的匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配，
二分圖的最大匹配：所有匹配中包含邊數最多的一組匹配被稱為二分圖的最大匹配，其邊數即為最大匹配數，
輸入格式
第一行包含三個整數 n1n1、 n2n2 和 mm，
接下來m行，每行包含兩個整數u和v，表示左半部點集中的點u和右半部點集中的點v之間存在一條邊，
輸出格式
輸出一個整數，表示二分圖的最大匹配數，
資料范圍
1≤n1,n2≤5001≤n1,n2≤500,
1≤u≤n11≤u≤n1,
1≤v≤n21≤v≤n2,
1≤m≤1051≤m≤105
輸入樣例：
2 2 4
1 1
1 2
2 1
2 2
輸出樣例：
2時間復雜度O（mn） 實際運行時間一般遠小于O（mn）
代碼：
//匈牙利演算法 //思路：一個二分圖，從左邊子圖最多能找到右邊子圖一一匹配的最大數量 //對于左邊子圖的某點，找右邊子圖的某點；如果右邊連通的某點沒有被匹配，那么可以選擇該點作為匹配點； //否則，右邊該點已經被匹配，則看看與右邊的這個點匹配的左邊的點能否還能找到另一個匹配的右邊的點， //如果能，則把右邊這個點讓給當前待匹配的左邊的點 import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=505,M=100005; static int h[]=new int[N]; static int e[]=new int[M]; static int ne[]=new int[M]; static int n1,n2,m,idx; static int match[]=new int[N]; static boolean vis[]=new boolean[N]; static void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } static boolean find(int u){ for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!vis[j]){ vis[j]=true; if(match[j]==0 || find(match[j])){//右邊的該點沒有被匹配或者j對應的左邊的點能找到另一個能匹配的右邊的點 match[j]=u; return true; } } } return false; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); Arrays.fill(h, -1); n1=scan.nextInt(); n2=scan.nextInt(); m=scan.nextInt(); while(m-->0){ int a=scan.nextInt(); int b=scan.nextInt(); add(a,b);//我們只從左邊向右邊查找 } int res=0; for(int i=1;i<=n1;i++){ Arrays.fill(vis, false);//初始化，對于每一個左邊的點，一開始它都沒有匹配右邊的點 if(find(i)) res++; } System.out.println(res); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95245.html
標籤：其他