可以看网站的浏览器,做暖视频网站免费,河北网站制作公司电话,网站建设适合手机二分图的最少边匹配#xff0c;即找出最少的边可以覆盖所有的点。用匈牙利算法找出最大匹配#xff0c;则最终结果为#xff1a;ans 图的顶点数 - 最大匹配。 代码如下#xff1a; 1 #includeiostream2 #includevector 3 using namespace std;4 #include即找出最少的边可以覆盖所有的点。用匈牙利算法找出最大匹配则最终结果为ans 图的顶点数 - 最大匹配。 代码如下 1 #includeiostream2 #includevector 3 using namespace std;4 #includecstdio5 #includecstring6 7 #define MAXN 1258 9 int match[MAXN];
10 int map[MAXN][MAXN];
11 int vis[MAXN];
12 int n,m;
13
14 int find(int x)
15 {
16 for(int i1;in;i)
17 {
18 if(map[x][i]!vis[i])
19 {
20 vis[i] 1;
21 if(!match[i] || find(match[i]))
22 {
23 match[i] x;
24 return 1;
25 }
26 }
27 }
28 return 0;
29 }
30
31 int main()
32 {
33 int T;
34 scanf(%d,T);
35 while(T--)
36 {
37 memset(map,0,sizeof(map));
38 memset(match,0,sizeof(match));
39 int a,b;
40 scanf(%d%d,n,m);
41 for(int i0;im;i)
42 {
43 scanf(%d%d,a,b);
44 map[a][b]1;
45 }
46
47 int ans0;
48 for(int i1;in;i)
49 {
50 memset(vis,0,sizeof(vis));
51 ansfind(i);
52 }
53 printf(%d\n,n-ans);
54 }
55 return 0;
56 } 转载于:https://www.cnblogs.com/myacm/archive/2012/08/13/2637215.html
