问题描述:

I got this implementation for maximum matching off the net and is trying to give its input through main class. But I am getting zero for all the places in match. What am I doing wrong?

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <queue>

using namespace std;

void add_edge(int u, int v);

void edmonds();

struct edge {

int v, nx;

};

const int MAXN = 1000, MAXE = 2000;

edge graph[MAXE];

int last[MAXN], match[MAXN], px[MAXN], base[MAXN], N, M, edges;

bool used[MAXN], blossom[MAXN], lused[MAXN];

int main ()

{

// return 0;

add_edge(1,4);

add_edge(1,5);

add_edge(1,6);

add_edge(2,5);

add_edge(2,7);

add_edge(3,4);

add_edge(4,1);

add_edge(4,3);

add_edge(5,1);

add_edge(5,2);

add_edge(6,1);

add_edge(7,2);

edmonds();

cout << match[0];

cout << match[1];

cout << match[2];

cout << match[3];

cout << match[4];

cout << match[5];

cout << match[6];

}

inline void add_edge(int u, int v) {

graph[edges] = (edge) {v, last[u]};

last[u] = edges++;

graph[edges] = (edge) {u, last[v]};

last[v] = edges++;

}

void mark_path(int v, int b, int children) {

while (base[v] != b) {

blossom[base[v]] = blossom[base[match[v]]] = true;

px[v] = children;

children = match[v];

v = px[match[v]];

}

}

int lca(int a, int b) {

memset(lused, 0, N);

while (1) {

lused[a = base[a]] = true;

if (match[a] == -1)

break;

a = px[match[a]];

}

while (1) {

b = base[b];

if (lused[b])

return b;

b = px[match[b]];

}

}

int find_path(int root) {

memset(used, 0, N);

memset(px, -1, sizeof(int) * N);

for (int i = 0; i < N; ++i)

base[i] = i;

used[root] = true;

queue<int> q;

q.push(root);

register int v, e, to, i;

while (!q.empty()) {

v = q.front(); q.pop();

for (e = last[v]; e >= 0; e = graph[e].nx) {

to = graph[e].v;

if (base[v] == base[to] || match[v] == to)

continue;

if (to == root || (match[to] != -1 && px[match[to]] != -1)) {

int curbase = lca(v, to);

memset(blossom, 0, N);

mark_path(v, curbase, to);

mark_path(to, curbase, v);

for (i = 0; i < N; ++i)

if (blossom[base[i]]) {

base[i] = curbase;

if (!used[i]) {

used[i] = true;

q.push(i);

}

}

} else if (px[to] == -1) {

px[to] = v;

if (match[to] == -1)

return to;

to = match[to];

used[to] = true;

q.push(to);

}

}

}

return -1;

}

void build_pre_matching() {

register int u, e, v;

for (u = 0; u < N; ++u)

if (match[u] == -1)

for (e = last[u]; e >= 0; e = graph[e].nx) {

v = graph[e].v;

if (match[v] == -1) {

match[u] = v;

match[v] = u;

break;

}

}

}

void edmonds() {

memset(match, 0xff, sizeof(int) * N);

build_pre_matching();

register int i, v, pv, ppv;

for (i = 0; i < N; ++i)

if (match[i] == -1) {

v = find_path(i);

while (v != -1) {

pv = px[v], ppv = match[pv];

match[v] = pv, match[pv] = v;

v = ppv;

}

}

}

网友答案:

You set elements of match in two locations: In build_pre_matching() and in edmonds(). In both of these cases, no change will happen if match[x] for some index x isn't -1. The only other place elements of match get a value is during static initialization where the values get zero initialized. Since the initial value is zero and the values are only ever changed if at least one of them happens to be -1, I would expect that the values retain the value 0.

You might want to use something like

std::fill(std::begin(match), std::end(match), -1);

at a strategic location since you seem to assume that the values are initially -1. Of course, you also should consider the idea of not using global variables because this doesn't scale and works really badly in a multi-threaded program.

相关阅读:
Top