输入误差在C++和分段错误

Question

我的代码 gom.cpp

#include "another.cpp" 
#include <iostream> 
#include <vector> 
#include <assert.h> 

using namespace std; 

typedef pair<int, int> ii; 
typedef vector<int> vi; 
typedef vector<ii> vii; 
typedef vector<vi> vvi; 
bool same[MAXV]; 
int s; 
const int INF = 0; 
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i) 


template <class T> 
void assert_equal(T expected, T actual, bool kill = false) { 
    if (!(expected == actual)) { 
     cout << "Assertion failed:" << endl; 
     cout << "Expected: " << expected << endl; 
     cout << " Actual: " << actual << endl; 
     if (kill) assert(false); 
    } 
} 


pair<vii, vvi> construct_gh_tree(flow_network &g) { 
    int n = g.n; 
    int v; 
    vii par(n, ii(0, 0)); 
    vvi cap(n, vi(n, -1)); 
    rep(s,1,n) { 
     int l = 0, r = 0; 
     par[s].second = g.max_flow(s, par[s].first, false); 
     memset(d, 0, n * sizeof(int)); 
     memset(same, 0, n * sizeof(int)); 
     d[q[r++] = s] = 1; 
     while (l < r) { 
      same[v = q[l++]] = true; 
      for (int i = g.head[v]; i != -1; i = g.e[i].nxt) 
       if (g.e[i].cap > 0 && d[g.e[i].v] == 0) 
        d[q[r++] = g.e[i].v] = 1; 
     } 
     rep(i,s+1,n) 
      if (par[i].first == par[s].first && same[i]) par[i].first = s; 
     g.reset(); 
    } 
    rep(i,0,n) { 
     int mn = INF, cur = i; 
     while (true) { 
      cap[cur][i] = mn; 
      if (cur == 0) break; 
      mn = min(mn, par[cur].second), cur = par[cur].first; 
     } 
    } 
    return make_pair(par, cap); 
} 
int compute_max_flow(int s, int t, const pair<vii, vvi> &gh) { 
    if (s == t) return 0; 
    int cur = INF, at1 = s; 
    while (gh.second[at1][t] == -1) 
     cur = min(cur, gh.first[at1].second), at1 = gh.first[at1].first; 
    return min(cur, gh.second[at1][t]); 
} 

void test() { 
    int N,M,source,sink,cap; 
    cout<<"Enter the vertices and edges"; 
    cin>>N>>M; 


    flow_network g(N); 
    pair<vii, vvi> gh; 

cout<<"Now enter the edges and their capacity"; 
    for(int i=0; i < M; i++) { 
      cin>>source; 
      cin>>sink; 
      cin>>cap; 
     g.add_edge(source, sink, cap, cap); 
     assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh)); 
    } 
gh = construct_gh_tree(g); 
for(int i = 0; i < N; ++i) { 
    for(int j = 0; j < N; ++j) { 
     assert_equal(g.max_flow(i, j), compute_max_flow(i, j, gh)); 
    } 
} 
} 


int main() 
{ 
    test(); 
    return 0; 
} 

此外， another.cpp

#include <iostream> 
#include <vector> 
#include <string.h> 
#include <algorithm> 

using namespace std; 

#define MAXV 2000 

int q[MAXV], d[MAXV]; 

struct flow_network { 
    struct edge { 
     int v, cap, nxt; 
     edge() { } 
     edge(int _v, int _cap, int _nxt) : v(_v), cap(_cap), nxt(_nxt) { } 
    }; 
    int n, ecnt, ecnt1, *head, *curh; 
    vector<edge> e, e_store; 
    flow_network(int _n, int m = -1) : n(_n), ecnt(0) { 
     e.reserve(2 * (m == -1 ? n : m)); 
     head = new int[n], curh = new int[n]; 
     memset(head, -1, n * sizeof(int)); 
    } 
    void destroy() { delete[] head; delete[] curh; } 

    void reset() { e = e_store; } 

    void add_edge(int u, int v, int uv, int vu = 0) { 
     e.push_back(edge(v, uv, head[u])); 
     head[u] = ecnt++; 
     e.push_back(edge(u, vu, head[v])); 
     head[v] = ecnt++; 
     //cout<<ecnt; 
    } 
    int augment(int v, int t, int f) { 
     if (v == t) return f; 
     for (int &i = curh[v], ret; i != -1; i = e[i].nxt) 
      if (e[i].cap > 0 && d[e[i].v] + 1 == d[v]) 
       if ((ret = augment(e[i].v, t, min(f, e[i].cap))) > 0) 
        return (e[i].cap -= ret, e[i^1].cap += ret, ret); 
     return 0; 
    } 
    int max_flow(int s, int t, bool res = true) { 
     if(s == t) return 0; 
     e_store = e; 
     int f = 0, x, l, r; 
     while (true) { 
      memset(d, -1, n * sizeof(int)); 
      l = r = 0, d[q[r++] = t] = 0; 
      while (l < r) 
       for (int v = q[l++], i = head[v]; i != -1; i = e[i].nxt) 
        if (e[i^1].cap > 0 && d[e[i].v] == -1) 
         d[q[r++] = e[i].v] = d[v]+1; 
      if (d[s] == -1) break; 
      memcpy(curh, head, n * sizeof(int)); 
      while ((x = augment(s, t, 0)) != 0) f += x; 
     } 
     if (res) reset(); 
     return f; 
    } 
}; 

当我编译代码并运行它，输入没有按不要停下来。什么可能是错误？ 基本上，我试图编译gom.cpp文件，运行测试并最终显示结果。 另外，我无法显示结果。

输入如下：

6 8 -> vertices and edges 
0 1 2 -> edge from 0-1 with capacity 2 
and so on -> 8 edges present. 

我输入变得分段错误。

Answer 1

你在这条线上得到一个segmentation fault：gh.second[at1][t]在gom.cpp因为gh从未初始化。

我想你的意思是把g.add_edge(source, sink, cap, cap);之前compute_max_flow(source, sink, gh)被称为。

下面是一些提示，以帮助你......

1. 你不应该包括.cpp文件。只包含.h（标题）文件。 将声明放入.cpp中的头文件和定义中。
2. 简单的cout语句可以告诉您发生分段错误的位置。
3. 总是明确地使用圆括号来标记代码块的开始和结束。

GOOD：

int x =1; 
if(x==1) 
{ 
    std::cout<<"x is 1"<<std::endl; 
} 
else 
{ 
    std::cout<<"x is not 1"<<std::endl; 
} 

坏习惯：

int x=1; 
if(x==1) 
    std::cout<<"x is 1"<<std::endl; 
else 
    std::cout<<"x is not 1"<<std::endl; 

用GDB调试问题与您的代码：

GDB是一个程序，可以帮助您调试您的c/C++程序的问题。要运行在gdb程序，只需键入gdb <your_program>

在gdb运行这个程序我有一个SIGSEGV：

Program received signal SIGSEGV, Segmentation fault. 
0x00000000004029a8 in std::vector<int, std::allocator<int> >::operator[](unsigned long) const() 
Missing separate debuginfos, use: debuginfo-install glibc-2.16-34.fc18.x86_64 libgcc-4.7.2-8.fc18.x86_64 libstdc++-4.7.2-8.fc18.x86_64 
(gdb) bt 
#0 0x00000000004029a8 in std::vector<int, std::allocator<int> >::operator[](unsigned long) const() 
#1 0x0000000000401488 in compute_max_flow(int, int, std::pair<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > const&)() 
#2 0x00000000004015bd in test()() 
#3 0x000000000040171f in main() 

为了进一步缩小发生的分段错误在哪里，我用简单的cout语句找到确切的错误。

编辑：

变化

pair<vii, vvi> gh; 

cout<<"Now enter the edges and their capacity"; 
    for(int i=0; i < M; i++) { 
      cin>>source; 
      cin>>sink; 
      cin>>cap; 
     g.add_edge(source, sink, cap, cap); 
     assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh)); 
    } 
gh = construct_gh_tree(g); 

要

pair<vii, vvi> gh; 

cout<<"Now enter the edges and their capacity"; 
    for(int i=0; i < M; i++) { 
      cin>>source; 
      cin>>sink; 
      cin>>cap; 
     g.add_edge(source, sink, cap, cap); 
     gh = construct_gh_tree(g); 
     assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh)); 
    } 

但是，在此之后，你仍然有max_flow一个无限循环，你需要处理...

Answer 2

我在第一个提示中输入了“6 8”，第二个输入了“0 1 2”。 它在max_flow（）中处于无限循环。 特别是，这条线

if (d[s] == -1) break; 

永不休息。在我的例子中，s是第二个提示的0输入。

下面是将分配线d [秒]：

d[q[r++] = e[i].v] = d[v]+1; 

我得到尽可能确定d [0]被赋予1，并永远不会改变。