二分图的最佳匹配怎么写
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/31 17:48:19
二分图的最佳匹配怎么写
二分图的最佳匹配怎么写
二分图的最佳匹配怎么写
1 #include
2 #include
3 #include // 使用其中的 min 函数
4 using namespace std;
5
6 const int MAX = 1024;
7
8 int n; // X 的大小
9 int weight [MAX] [MAX]; // X 到 Y 的映射(权重)
10 int lx [MAX], ly [MAX]; // 标号
11 bool sx [MAX], sy [MAX]; // 是否被搜索过
12 int match [MAX]; // Y(i) 与 X(match [i]) 匹配
13
14 // 初始化权重
15 void init (int size);
16 // 从 X(u) 寻找增广道路,找到则返回 true
17 bool path (int u);
18 // 参数 maxsum 为 true ,返回最大权匹配,否则最小权匹配
19 int bestmatch (bool maxsum = true);
20
21 void init (int size)
22 {
23 // 根据实际情况,添加代码以初始化
24 n = size;
25 for (int i = 0; i < n; i ++)
26 for (int j = 0; j < n; j ++)
27 scanf (