POJ 2226 Muddy Fields_专业打酱油_百度空间
还是二分图匹配,不过这次建图很麻烦,匹配的是行标号跟列标号。

建图(这儿说行的情况,列与之类似)的时候从{dy}行开始从左往右扫,一旦出现“.”就把行标号加一,这样就把每个点对应的新的行标号算出来了,同理算出列标号,然后连边。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iterator>
#include <functional>
#include <string>

using namespace std;

struct edge_t {
struct vectex_t *dest;
edge_t *next;
};

struct vectex_t {
edge_t *edges;
vectex_t *node_matched;
bool visited;
};

edge_t edges[2500];
edge_t *end_of_edges(edges);
vectex_t vectices[2601];
char data_matrix[51][51];
int nr_rows, nr_columns;

int vectices_end1;
int vectices_end2;

inline
void
add_edge(int src, int dest)
{
end_of_edges->next = vectices[src].edges;
end_of_edges->dest = &vectices[dest];
vectices[src].edges = end_of_edges++;

return;
}

bool
find_augmentation(vectex_t *vec)
{
for (edge_t *iter = vec->edges; iter; iter = iter->next) {
if (!iter->dest->visited) {
iter->dest->visited = true;
if (!iter->dest->node_matched || find_augmentation(iter->dest->node_matched)) {
iter->dest->node_matched = vec;
return true;
}
}
}

return false;
}

int
max_match(void)
{
int result(0);

for (vectex_t *iter = vectices; iter != vectices + vectices_end1; ++iter) {
for (vectex_t *iter2 = vectices; iter2 != vectices + vectices_end2; ++iter2) {
iter2->visited = false;
}
result += find_augmentation(iter);
}

return result;
}

bool
scan_data(void)
{
if (!(cin >> nr_rows >> nr_columns)) {
return false;
}
for (int i = 1; i != nr_rows + 1; ++i) {
cin >> data_matrix[i] + 1;
}

return true;
}

void
build_map(void)
{
int current_offset;
int offset1[51][51] = {0}, offset2[51][51] = {0};

current_offset = 0;
for (int i = 1; i != nr_rows + 1; ++i) {
for (int j = 1; j != nr_columns + 1; ++j) {
if (data_matrix[i][j] == '*') {
offset1[i][j] = (current_offset += (data_matrix[i][j - 1] != '*'));
}
}
}

current_offset = 0;
for (int j = 1; j != nr_columns + 1; ++j) {
for (int i = 1; i != nr_rows + 1; ++i) {
if (data_matrix[i][j] == '*') {
offset2[i][j] = (current_offset += (data_matrix[i - 1][j] != '*'));
add_edge(offset1[i][j], offset2[i][j]);
vectices_end1 = max(offset1[i][j], vectices_end1);
vectices_end2 = max(offset2[i][j], vectices_end2);
}
}
}

++vectices_end1;
++vectices_end2;

return;
}

void
global_init(void)
{
end_of_edges = edges;
memset(vectices, 0, sizeof(vectices));
memset(data_matrix, 0, sizeof(data_matrix));
vectices_end1 = 0;
vectices_end2 = 0;

return;
}

int
main()
{
freopen("test.txt", "r", stdin);

for (;;) {
global_init();
if (!scan_data()) {
break;
}
build_map();
cout << max_match() << endl;
}

return 0;
}


郑重声明:资讯 【POJ 2226 Muddy Fields_专业打酱油_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——