У меня есть 2D-массив, где каждый элемент равен O или Non Zero, я должен собрать все элементы 1. Для этого я нанять рабочихМаксимальное соответствие в графе
`0` - dead coconut tree
`Non Zero` - living tree
Работник начинает уборку в живом дереве и продолжает уборку вдоль прямой линии деревьев в одном из четырех кардинальных направлений (например, север, юг, восток или запад). Работник прекращает сбор кокосов при выполнении одного из следующих условий:
- Рабочий сталкивается с мертвым кокосовым деревом.
- Рабочий попадает на край плантации (т. Е. В этом направлении больше нет ).
Для примера массив выглядеть следующим образом:
Так Минимум 4 рабочих требуется 
Вопрос:
Я был в шоке, когда я узнал, что это Maximum Matching Problem, я понятия не имел, как это так. Ниже код обозначающий Горизонтальные и вертикальные полоски с индексом
m=1;
for (int i=0; i<r; i++) {
int j = 0;
while (j < c && a[i][j] < m) j++;
while (j < c) {
while (j < c && a[i][j] >= m) {
h[i][j] = hcnt;
j++;
}
hcnt++;
while (j < c && a[i][j] < m) j++;
}
}
int vcnt = 0;
for (int j=0; j<c; j++) {
int i = 0;
while (i < r && a[i][j] < m) i++;
while (i < r) {
while (i < r && a[i][j] >= m) {
v[i][j] = vcnt;
i++;
}
vcnt++;
while (i < r && a[i][j] < m) i++;
}
}
Так что мой вопрос заключается в том, чтобы добавить края и почему это максимальная проблема согласования и может кто-то объяснить интуицию за этим, почему максимальное согласование работ по этой проблеме ,
Original Question
Следующий код Добавить края. Я не мастерил ни малейшего представления о том, как мы добавляем края и почему она работает
int s = 0, t = hcnt + vcnt + 1;
for (int i=0; i<hcnt; i++) addEdge(s, i+1, 1);
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) if(a[i][j] >= m) {
addEdge(1 + h[i][j], 1 + hcnt + v[i][j], 1);
}
}
for (int i=0; i<vcnt; i++) addEdge(1 + hcnt + i, t, 1);