首页 > 代码库 > 二分图的最大匹配

二分图的最大匹配

2024-07-07 02:57:54   232人阅读

zoj 1364

直接套模板 + 建图方式。。。。至少会套模板了。。。。把最小生成树的弄完再 。。。 回来证明。。。。

 

//

Poj 1325 Machine Schedule（求二分图的最小覆盖数）

题意：有A，B两台机器，和K个需要运行的任务；A，B分别有N，M中模式；

每个任务都既可以在A中以x模式，也可以在B中以y模式完成；

每台机器可以按照任意顺序执行，但是每台机器每转化一次模式就需重启一次；

安排一种顺序，使机器重启次数最少；（开始时A，B都处于模式0）；

算法：二分图的建立，匈牙利算法，

主要是建模；本题建模需要一点技巧；

 

如图，因为我们需要最少的模式数，将所有的任务覆盖；应该把每个任务看成一

条边，把A机器的每个模式看成一个X结点，B机器的每个模式看成一个Y结点；

这样就建立了二分图；我们要求的是用最少的点将所有的边覆盖；

有以下结论，这个覆盖数等于最大匹配数M；

下面是LRJ的证明，很好很强大；

①M个是足够的，只需要让他们覆盖最大的匹配的M条边，则其他边一定被覆盖

（如果有边e不被覆盖，把e加入后得到一个更大的匹配）

②M个是必需的，仅考虑形成最大匹配的M条边，由于两两无公共点，因此至少

需要M个点才能把它们覆盖；

最后，对于输入中可以在模式0下完成的直接不用存储；

//

 1 //Accepted    1364    C++    0    260
 2 #include <stdio.h>
 3 #include <string.h>
 4 const int N = 151;
 5 int mapp[N][N], chk[N], match[N];
 6 int m, n, k, res;
 7 int dfs(int p)
 8 {
 9     int i, t;
10     for (int i = 1; i <= m; i++)
11     if (mapp[i][p] && !chk[i]) {
12         chk[i] = 1;
13         t = match[i];
14         match[i] = p;
15         if (t == -1 || dfs(t))
16             return 1;
17         match[i] = t;
18     }
19     return 0;
20 }
21 
22 void pro()
23 {
24     for (int i = 1; i <= n; i++) {
25         memset(chk, 0, sizeof(chk));
26         res += dfs(i);
27     }
28 }
29 
30 int main()
31 {
32     while (scanf("%d", &n) && n)
33     {
34         res = 0;
35         memset(mapp, 0, sizeof(mapp));
36         memset(match, -1, sizeof(match));
37         scanf("%d%d", &m, &k);
38         for (int i = 0; i < k; i++)
39         {
40             int u, v, num;
41             scanf("%d%d%d", &num, &u, &v);
42             if (!u||!v) continue;
43             mapp[u][v] = 1;
44         }
45         pro();
46         printf("%d\n", res);
47     }
48     return 0;
49 }
View Code


联系
我们