Отказ от ответственности: не весь код, который я использовал для решения проблемы, необходим для ответа на мой вопрос, но я предоставлю остальное, если это необходимо.
Проблема (если необходим контекст): http://www.usaco.org/index.php?page=viewproblem2&CPID = 93
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 1000000000
struct Edge{
int from, to, cap, flow;
Edge* backwards;
Edge(int a, int b, int c, int d): from(a), to(b), cap(c), flow(d) {}
};
struct Dinic{
int n, source, sink, dist [1000];
queue<int> q;
vector<Edge> adjacency [1000];
bool blocked [1000];
Dinic(int x): n(x), source(n++), sink(n++) { }
void add(int v1, int v2, int c, int f){
Edge e(v1, v2, c, f); Edge r(v2, v1, 0, 0);
e.backwards = &r; r.backwards = &e;
adjacency[v1].push_back(e); adjacency[v2].push_back(r);
}
bool bfs(){
q = queue<int>(); fill_n(dist, 1000, -1); dist[sink] = 0; q.push(sink);
while(q.size() > 0){
int node = q.front(); q.pop();
if(node == source) return true;
for(int i = 0; i < adjacency[node].size(); i++){
if(adjacency[node][i].backwards->cap > adjacency[node][i].backwards->flow && dist[adjacency[node][i].to] == -1){
dist[adjacency[node][i].to] = dist[node]+1;
q.push(adjacency[node][i].to);
}
}
}
return dist[source] != -1;
}
int dfs(int pos, int mini){
if(pos == sink) return mini;
int flowy = 0;
for(int i = 0; i < adjacency[pos].size(); i++){
int curr = 0;
if(!blocked[adjacency[pos][i].to] && dist[adjacency[pos][i].to] == dist[pos]-1 && adjacency[pos][i].cap > adjacency[pos][i].flow){
curr = dfs(adjacency[pos][i].to, min(mini-flowy, adjacency[pos][i].cap-adjacency[pos][i].flow));
adjacency[pos][i].flow += curr; adjacency[pos][i].backwards->flow -= adjacency[pos][i].flow;
flowy += curr;
}
if(flowy == mini) return flowy;
}
blocked[pos] = flowy != mini;
return flowy;
}
int flow(){
int ret = 0; fill_n(blocked, 1000, false);
while(bfs()){
fill_n(blocked, 1000, false);
ret += dfs(source, INF);
cout << ret << endl;
}
return ret;
}
};
Задача существенно сужается до нахождения минимального числа вершин, которые составляют покрытие вершин двудольного графа. Я смог успешно построить указанный граф в невидимой части моего кода, но моя проблема заключается в том, чтобы запустить на нем алгоритм Диника.
При этом я продолжаю получать бесконечный цикл, который происходит из-за ошибки в методе «dfs ()». Всякий раз, когда я пытаюсь обновить указатель «обратный край», он не сохраняет изменения, как предполагалось, в результате один и тот же путь берется снова и снова.
Я очень плохо знаком с использованием указателей, и мне не удалось найти решение или объяснение моей проблемы, связанной с указателями, после нескольких часов поиска.
Пожалуйста, помогите, и спасибо заранее!
РЕДАКТИРОВАТЬ: Добавлено в сегмент кода, который отображает проблему.
Dinic solve(3);
solve.add(0, 3, 1, 0);
solve.adjacency[3][0].backwards->flow = 1;
cout << solve.adjacency[0][0].flow << endl; //prints out 0 instead of 1
Основные проблемы, выделенные вашим примером, заключаются в add()
метод:
void add(int v1, int v2, int c, int f){ Edge e(v1, v2, c, f); Edge r(v2, v1, 0, 0); e.backwards = &r; r.backwards = &e; adjacency[v1].push_back(e); adjacency[v2].push_back(r); }
Сначала заметьте, что вы объявляете Edge
экземпляры, обозначенные e
а также r
в стеке и, следовательно, их время жизни заканчивается, когда переменные выходят из области видимости в конце метода. Это действительно отличается от Java, в котором объекты могут быть размещены только в куче, а у вас есть только ссылки на них.
В каждом Edge
Вы устанавливаете указатель на другой стек, выделенный Edge
, но это значение указателя полезно только для времени жизни объектов, на которые указывают (выделяются стеки); разыменование их позже, то есть после возврата этого метода, приводит к неопределенному поведению.
Кроме того, важно понимать, что vector::push_back
создает копию своего аргумента; в этом смысле это не похоже, скажем, на Java List.add()
, Эти копии содержат копии значений backward
указатели, указывая на те же объекты, выделенные стеком, на которые указывают указатели оригиналов. Так как это разные объекты из копий в adjacency
векторы, элементы векторов смежности не указывают друг на друга.
То есть непосредственно перед возвратом метода у вас есть
e.backwards
указывает на r
r.backwards
указывает на e
e
в adjacency[v1]
).backwards
также указывает на r
r
в adjacency[v2]
).backwards
также указывает на e
Таким образом, в вашем примере, выполняя solve.adjacency[3][0].backwards->flow = 1
не изменяет объект, обозначенный solve.adjacency[0][0]
, поскольку backwards
указатель не указывает на этот объект. (На самом деле срок жизни объекта, на который он когда-то указывал, закончился, поэтому присваивание приводит к неопределенному поведению.) Поэтому неудивительно, что вы не наблюдаете каких-либо изменений в solve.adjacency[0][0]
,
Есть несколько способов решить эти проблемы, среди них
выделить Edge
объекты в куче, и хранить указатели на них в вашем векторе
назначать backward
указатели, которые указывают на правильный в-вектор Edges
Последнее может быть реализовано в add()
без изменения чего-либо еще; это должно сделать это:
void add(int v1, int v2, int c, int f){
Edge e(v1, v2, c, f);
Edge r(v2, v1, 0, 0);
adjacency[v1].push_back(e);
adjacency[v2].push_back(r);
adjacency[v1].back().backwards = &adjacency[v2].back();
adjacency[v2].back().backwards = &adjacency[v1].back();
}
Других решений пока нет …