E070. Обратная 题目 SSSP (inverse-SSSP - обратная 题目 кратчайших путей из одной вершины)

e-maxx algorithm original: C/C++ #algorithm #emaxx #graph #shortest-path

题目文本会按所选界面语言从俄语翻译；代码保持不变。

Static

Источник: e-maxx.ru/algo, страница PDF 208.

Имеется взвешенный неориентированный мульти图 G из N вершин и M рёбер. Дан 数组 P[1..N] и указана некоторая начальная vertex S. it is required изменить веса рёбер так, чтобы для всех I P[I] было равно длине кратчайшего пути из S в I, причём сумма всех изменений (сумма модулей изменений весов рёбер) была бы наименьшей. Если этого сделать невозможно, то 算法 должен выдать "No solution". Делать вес ребра отрицательным запрещено.

Описание решения

Мы решим эту задачу за линейное время, просто перебрав все рёбра (т.е. за один проход). Пусть на текущем шаге мы рассматриваем edge из вершины A в вершину B длиной R. Мы предполагаем, что для вершины A уже все условия выполнены (т.е. расстояние от S до A действительно равно P[A]), и будем проверять выполнение условий для вершины B. Имеем несколько вариантов ситуации:

● 1. P[A] + R < P[B]

Это означает, что мы нашли путь, более короткий, чем он должен быть. Поскольку P[A] и P[B] мы изменять не можем, то мы обязаны удлинить текущее edge (независимо от остальных рёбер), а именно выполнить: R += P[B] - P[A] - R. Кроме того, это означает, что мы нашли уже путь в вершину B из S, длина которого равна требуемому значению P [B], поэтому на последующих шагах нам не придётся укорачивать какие-либо рёбра (см. вариант 2).

● 2. P[A] + R >= P[B]

Это означает, что мы нашли путь, более длинный, чем требуемый. Поскольку таких путей может быть несколько, мы должны выбрать среди всех таких путей (рёбер) то, которое потребует наименьшего изменения. Повторимся, что если мы удлиняли какое-то edge, ведущее в вершину B (вариант 1), то этим мы фактически построили 最短路径 в вершину B, а потому укорачивать никакое edge уже не надо будет. Таким образом, для каждой вершины мы должны хранить edge, которое собираемся укорачивать, т.е. edge с наименьшим весом изменения. Таким образом, просто перебрав все рёбра, и рассмотрев для каждого ребра ситуацию (за O(1)), мы решим обратную задачу SSSP за линейное время. Если в какой-то момент мы пытаемся изменить уже изменённое edge, то, очевидно, этого делать нельзя, и следует выдать "No solution". Кроме того, у некоторых вершин может быть так и не достигнута требуемая оценка кратчайшего пути, тогда ответ тоже будет "No solution". Во всех остальных случаях (кроме, конечно, явно некорректных значений в 数组е P, т.е. P[S] != 0 или отрицательные значения) ответ будет существовать.

实现

Программа выводит "No solution", если решения нет, иначе выводит в первой строке минимальную сумму изменений весов рёбер, а в последующих M 字符串х - новые веса рёбер.

const int INF = 100010001000;

int n, m;

vector<int> p (n);

bool ok = true;

vector<int> cost (m), cost_ch (m), decrease (n, INF), decrease_id (n, -1);

decrease[0] = 0;

for (int i=0; i<m; ++i) {

int a, b, c; // текущее edge (a,b) с ценой c

cost[i] = c;

for (int j=0; j<=1; ++j) {

int diff = p[b] - p[a] - c;

if (diff > 0) {

ok &= cost_ch[i] == 0 || cost_ch[i] == diff;

cost_ch[i] = diff;

decrease[b] = 0;

}

else

if (-diff <= c && -diff < decrease[b]) {

decrease[b] = -diff;

decrease_id[b] = i;

}

swap (a, b);

} }

for (int i=0; i<n; ++i) {

ok &= decrease[i] != INF;

int r_id = decrease_id[i];

if (r_id != -1) {

ok &= cost_ch[r_id] == 0 || cost_ch[r_id] == -decrease[i];

cost_ch[r_id] = -decrease[i];

} }

if (!ok)

cout << "No solution";

else {

long long sum = 0;

for (int i=0; i<m; ++i)  sum += abs (cost_ch[i]);

cout << sum << '\n';

for (int i=0; i<m; ++i)

printf ("%d ", cost[i] + cost_ch[i]);

}

C# 解法

自动草稿，提交前请检查

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    const int INF = 1000*1000*1000;
    int n, m;
    List<int> p (n);
    bool ok = true;
    List<int> cost (m), cost_ch (m), decrease (n, INF), decrease_id (n, -1);
    decrease[0] = 0;
    for (int i=0; i<m; ++i) {
            int a, b, c; // текущее ребро (a,b) с ценой c
            cost[i] = c;
            for (int j=0; j<=1; ++j) {
                    int diff = p[b] - p[a] - c;
                    if (diff > 0) {
                            ok &= cost_ch[i] == 0 || cost_ch[i] == diff;
                            cost_ch[i] = diff;
                            decrease[b] = 0;
                    }
                    else
                            if (-diff <= c && -diff < decrease[b]) {
                                    decrease[b] = -diff;
                                    decrease_id[b] = i;
                            }
                    swap (a, b);
            }
    }
    for (int i=0; i<n; ++i) {
            ok &= decrease[i] != INF;
            int r_id = decrease_id[i];
            if (r_id != -1) {
                    ok &= cost_ch[r_id] == 0 || cost_ch[r_id] == -decrease[i];
                    cost_ch[r_id] = -decrease[i];
            }
    }
    if (!ok)
            Console.WriteLine( "No solution";
    else {
            long sum = 0;
            for (int i=0; i<m; ++i)  sum += abs (cost_ch[i]);
            Console.WriteLine( sum << '\n';
            for (int i=0; i<m; ++i)
                    Console.Write ("%d ", cost[i] + cost_ch[i]);
    }
}

C++ 解法

匹配/原始

const int INF = 1000*1000*1000;
int n, m;
vector<int> p (n);
bool ok = true;
vector<int> cost (m), cost_ch (m), decrease (n, INF), decrease_id (n, -1);
decrease[0] = 0;
for (int i=0; i<m; ++i) {
        int a, b, c; // текущее ребро (a,b) с ценой c
        cost[i] = c;
        for (int j=0; j<=1; ++j) {
                int diff = p[b] - p[a] - c;
                if (diff > 0) {
                        ok &= cost_ch[i] == 0 || cost_ch[i] == diff;
                        cost_ch[i] = diff;
                        decrease[b] = 0;
                }
                else
                        if (-diff <= c && -diff < decrease[b]) {
                                decrease[b] = -diff;
                                decrease_id[b] = i;
                        }
                swap (a, b);
        }
}
for (int i=0; i<n; ++i) {
        ok &= decrease[i] != INF;
        int r_id = decrease_id[i];
        if (r_id != -1) {
                ok &= cost_ch[r_id] == 0 || cost_ch[r_id] == -decrease[i];
                cost_ch[r_id] = -decrease[i];
        }
}
if (!ok)
        cout << "No solution";
else {
        long long sum = 0;
        for (int i=0; i<m; ++i)  sum += abs (cost_ch[i]);
        cout << sum << '\n';
        for (int i=0; i<m; ++i)
                printf ("%d ", cost[i] + cost_ch[i]);
}

Java 解法

自动草稿，提交前请检查

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    const int INF = 1000*1000*1000;
    int n, m;
    ArrayList<Integer> p (n);
    boolean ok = true;
    ArrayList<Integer> cost (m), cost_ch (m), decrease (n, INF), decrease_id (n, -1);
    decrease[0] = 0;
    for (int i=0; i<m; ++i) {
            int a, b, c; // текущее ребро (a,b) с ценой c
            cost[i] = c;
            for (int j=0; j<=1; ++j) {
                    int diff = p[b] - p[a] - c;
                    if (diff > 0) {
                            ok &= cost_ch[i] == 0 || cost_ch[i] == diff;
                            cost_ch[i] = diff;
                            decrease[b] = 0;
                    }
                    else
                            if (-diff <= c && -diff < decrease[b]) {
                                    decrease[b] = -diff;
                                    decrease_id[b] = i;
                            }
                    swap (a, b);
            }
    }
    for (int i=0; i<n; ++i) {
            ok &= decrease[i] != INF;
            int r_id = decrease_id[i];
            if (r_id != -1) {
                    ok &= cost_ch[r_id] == 0 || cost_ch[r_id] == -decrease[i];
                    cost_ch[r_id] = -decrease[i];
            }
    }
    if (!ok)
            System.out.println( "No solution";
    else {
            long sum = 0;
            for (int i=0; i<m; ++i)  sum += abs (cost_ch[i]);
            System.out.println( sum << '\n';
            for (int i=0; i<m; ++i)
                    System.out.print ("%d ", cost[i] + cost_ch[i]);
    }
}

Материал разбит как 算法ическая 题目: изучить постановку, понять асимптотику и реализовать 算法 на выбранном языке.

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。