专业集团门户网站建设公司,网站建设有哪些方面,梦织和wordpress特点,泰安市人才市场嗯 想不通就是二分之后的点#xff0c;寻找左边的点和右边的点的保证两条边的顶点不相同的最大边数
匈牙利算法 O(mn) 左边寻找和右边相邻的边#xff0c;如果右边还没有和左边进行连线#xff0c;那么匹配成功。如果右边已经进行连线#xff0c;那么考虑左边是否能更改连…嗯 想不通就是二分之后的点寻找左边的点和右边的点的保证两条边的顶点不相同的最大边数
匈牙利算法 O(mn) 左边寻找和右边相邻的边如果右边还没有和左边进行连线那么匹配成功。如果右边已经进行连线那么考虑左边是否能更改连线换一个右边。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class Main {private static int N 510;private static int M 100010;private static int[] h new int[M];private static int[] e new int[M];private static int[] ne new int[M];private static int n1,n2,m;private static int[] match new int[N];private static boolean[] vis new boolean[N];private static int idx;private static int res;public static void add(int a,int b){e[idx] b;ne[idx] h[a];h[a] idx;}//能否找到他的妻子public static boolean find(int x){for(int i h[x]; i ! -1; i ne[i] ){int j e[i];if(!vis[j]){ // 需要标记一下右边因为需要考虑当前男生已经选择了这个女生需要改变别的男生时别的男生就不能考虑这个女生vis[j] true;if(match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;}public static void main(String[] args) throws IOException {BufferedReader reader new BufferedReader(new InputStreamReader(System.in));String[] s reader.readLine().split( );n1 Integer.parseInt(s[0]);n2 Integer.parseInt(s[1]);m Integer.parseInt(s[2]);Arrays.fill(h,-1);for(int i 0; i m; i){String[] s1 reader.readLine().split( );int u Integer.parseInt(s1[0]);int v Integer.parseInt(s1[1]);add(u,v);}for(int i 1; i n1; i){Arrays.fill(vis,false);if(find(i)){res;}}System.out.println(res);}
}
