1 Отредактировано Coding_disciple (2014-08-15 15:29:09)

Тема: Испорченный паркет

Есть задача про испорченный паркет. Выяснилось, что задача относительно старая, и разбиралась тут: http://olymp.kture.kharkov.ua/files/Sbo … k_2009.pdf, стр. 118.
Там предлагается свести задачу к задаче на графах и найти максимальное парасочетание, и говорится, что "это можно сделать с помощью любого алгоритма нахождения потока или алгоритма."
Я думаю, что решать надо в два хода: прочитать "паркетную" матрицу со стандартного ввода, преобразовать её в двудольный граф, а затем найти в ней максимальный поток.
Поток я думаю искать или методом проталкивания предпотока, или по алгоритму Динитца.

На правильном ли я пути?

UPD: Код почти готов, осталось сообразить, как читать строки и преобразовывать их в граф. Исходники могу выложить. Кто-нибудь мог бы помочь?

2

Re: Испорченный паркет

Выложи пожалуйта исходники

Re: Испорченный паркет

   //#include "stdafx.h"
#include <cassert>
#include <cmath>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

typedef long long LL;

struct Edge 
{
    int from, to, cap, flow, index;
    Edge(int from, int to, int cap, int flow, int index) :
        from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct PushRelabel 
{
int N;
vector<vector<Edge>> Graph;
vector<LL> excess;
vector<int> dist, active, count;
queue<int> Queue;

PushRelabel(int N) : N(N), Graph(N), excess(N), dist(N), active(N), count(2 * N) {}

void AddEdge(int from, int to, int cap)                     //this constructs a graph
{
    Graph[from].push_back(Edge(from, to, cap, 0, Graph[to].size()));
    if (from == to) 
        Graph[from].back().index++;
    Graph[to].push_back(Edge(to, from, 0, 0, Graph[from].size() - 1));
}

void Enqueue(int v) 
{
    if (!active[v] && excess[v] > 0) 
    { 
        active[v] = true;
        Queue.push(v);
    }
}

void Push(Edge &e)                                          // the operation in the heart of all this
{
    int amt = int(min(excess[e.from], LL(e.cap - e.flow)));
    if (dist[e.from] <= dist[e.to] || amt == 0)
        return;
    e.flow += amt;
    Graph[e.to][e.index].flow -= amt;
    excess[e.to] += amt;
    excess[e.from] -= amt;
    Enqueue(e.to);
}

void Gap(int k)
{
    for (int v = 0; v < N; v++)
    {
        if (dist[v] < k) 
            continue;
        count[dist[v]]--;
        dist[v] = max(dist[v], N + 1);
        count[dist[v]]++;
        Enqueue(v);
    }
}

void Relabel(int v)                                 // the other operation in the heart of all this
{
    count[dist[v]]--;
    dist[v] = 2 * N;
    for (int i = 0; i < Graph[v].size(); i++)
        if (Graph[v][i].cap - Graph[v][i].flow > 0)
            dist[v] = min(dist[v], dist[Graph[v][i].to] + 1);
    count[dist[v]]++;
    Enqueue(v);
}

void Discharge(int v) 
{
    for (int i = 0; excess[v] > 0 && i < Graph[v].size(); i++) Push(Graph[v][i]);
    if (excess[v] > 0) 
    {
        if (count[dist[v]] == 1)
            Gap(dist[v]);
        else
            Relabel(v);
    }
}

LL GetMaxFlow(int s, int t)                                 //this is essentially what we're after
{
    count[0] = N - 1;
    count[N] = 1;
    dist[s] = N;
    active[s] = active[t] = true;
    for (int i = 0; i < Graph[s].size(); i++) 
    {
        excess[s] += Graph[s][i].cap;
        Push(Graph[s][i]);
    }

    while (!Queue.empty()) 
    {
        int v = Queue.front();
        Queue.pop();
        active[v] = false;
        Discharge(v);
    }

    LL totflow = 0;
    for (int i = 0; i < Graph[s].size(); i++)
        totflow += Graph[s][i].flow;
    return totflow;
}
};


    int main()
{

struct PushRelabel prGraph(4);
prGraph.AddEdge(0, 1, 2);
prGraph.AddEdge(0, 2, 2);
prGraph.AddEdge(1, 3, 1);
prGraph.AddEdge(2, 3, 3);

int N, M, A, B;

cin >> N;
assert ((N >= 1) && (N <= 300));
cin >> M;
assert ((M >= 1) && (M <= 300));
cin >> A;
assert(A <= 1000);
cin >> B;
assert(B <= 1000);

for (int i = 0; i < N; ++i)
{
    std::cin >> string__;       // that's where I have to read the string
    std::cin >> next_string__;  //...and the next string
                                // use these 2 strings to update a graph
                                // with prGraph.AddEdge()
}

//the extra prGraph code is here to test the whole thing works (it does)

cout << prGraph.GetMaxFlow(0, 3) << endl;
return 0;
}

Комментарии в коде я привык по-английски писать. Если что, переведу.

4

Re: Испорченный паркет

Спасибо!

5

Re: Испорченный паркет

А у тебя получилось решить задачу?