USACO Steeplechase: алгоритм Dinic / изменения в указателе не регистрируются

Отказ от ответственности: не весь код, который я использовал для решения проблемы, необходим для ответа на мой вопрос, но я предоставлю остальное, если это необходимо.

Проблема (если необходим контекст): 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

0

Решение

Основные проблемы, выделенные вашим примером, заключаются в 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();
}
1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]