还是二分图匹配,不过这次建图很麻烦,匹配的是行标号跟列标号。
建图(这儿说行的情况,列与之类似)的时候从{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;
}