为什么我对数组中的所有值都得到零输出？

Question

我得到了这个实现最大限度地匹配网络，并试图通过主类给它的输入。但是我对比赛中的所有地方都是零。我究竟做错了什么？

#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; 
     } 
     } 
} 

Answer 1

您可以设置在两个位置的match要素：build_pre_matching()和edmonds()。在这两种情况下，如果match[x]对于某些索引x不是-1将不会发生变化。 match唯一其他地方的元素得到一个值是在初始化值为零的静态初始化过程中。由于初始值为零，并且只有在其中至少有一个值为-1时才更改这些值，所以我认为这些值保留值0。

您可能需要在战略位置，因为你似乎假定值最初-1使用类似

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

。当然，你也应该考虑使用全局变量的而不是的想法，因为这不能在多线程程序中扩展和工作得非常糟糕。