fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <iomanip>
  5. #include <string>
  6. #include <algorithm>
  7. #include <set>
  8. using namespace std;
  9.  
  10. const int N = 5; // Кол-во городов
  11. const int INF = 1e6;
  12.  
  13. using Matrix = vector<vector<int>>;
  14.  
  15. void printMatrix(const Matrix& mat) {
  16.     for (int i = 0; i < N; ++i) {
  17.         for (int j = 0; j < N; ++j) {
  18.             if (mat[i][j] >= INF)
  19.                 cout << "M ";
  20.             else
  21.                 cout << setw(2) << mat[i][j] << " ";
  22.         }
  23.         cout << endl;
  24.     }
  25. }
  26.  
  27. // Простая верхняя граница (жадный ближайший сосед)
  28. int calculateUpperBound(const Matrix& mat) {
  29.     int total = 0;
  30.     vector<bool> visited(N, false);
  31.     int current = 0;
  32.     visited[current] = true;
  33.  
  34.     for (int step = 1; step < N; ++step) {
  35.         int next = -1, minCost = INF;
  36.         for (int j = 0; j < N; ++j) {
  37.             if (!visited[j] && mat[current][j] < minCost) {
  38.                 minCost = mat[current][j];
  39.                 next = j;
  40.             }
  41.         }
  42.         if (next == -1) return INF;
  43.         total += minCost;
  44.         visited[next] = true;
  45.         current = next;
  46.     }
  47.  
  48.     // Возвращение в начальную точку
  49.     total += mat[current][0];
  50.     return total;
  51. }
  52.  
  53. int reduceRows(Matrix& mat) {
  54.     int reduction = 0;
  55.     for (int i = 0; i < N; ++i) {
  56.         int rowMin = INF;
  57.         for (int j = 0; j < N; ++j)
  58.             rowMin = min(rowMin, mat[i][j]);
  59.         if (rowMin == INF) continue;
  60.         for (int j = 0; j < N; ++j)
  61.             if (mat[i][j] < INF) mat[i][j] -= rowMin;
  62.         reduction += rowMin;
  63.     }
  64.     return reduction;
  65. }
  66.  
  67. int reduceCols(Matrix& mat) {
  68.     int reduction = 0;
  69.     for (int j = 0; j < N; ++j) {
  70.         int colMin = INF;
  71.         for (int i = 0; i < N; ++i)
  72.             colMin = min(colMin, mat[i][j]);
  73.         if (colMin == INF) continue;
  74.         for (int i = 0; i < N; ++i)
  75.             if (mat[i][j] < INF) mat[i][j] -= colMin;
  76.         reduction += colMin;
  77.     }
  78.     return reduction;
  79. }
  80.  
  81. pair<int, pair<int, int>> selectNextEdge(const Matrix& mat) {
  82.     int maxPenalty = -1;
  83.     pair<int, int> bestEdge = {-1, -1};
  84.  
  85.     for (int i = 0; i < N; ++i)
  86.         for (int j = 0; j < N; ++j)
  87.             if (mat[i][j] == 0) {
  88.                 int rowMin = INF, colMin = INF;
  89.                 for (int k = 0; k < N; ++k) {
  90.                     if (k != j) rowMin = min(rowMin, mat[i][k]);
  91.                     if (k != i) colMin = min(colMin, mat[k][j]);
  92.                 }
  93.                 int penalty = (rowMin == INF ? 0 : rowMin) + (colMin == INF ? 0 : colMin);
  94.                 if (penalty > maxPenalty) {
  95.                     maxPenalty = penalty;
  96.                     bestEdge = {i, j};
  97.                 }
  98.             }
  99.  
  100.     return {maxPenalty, bestEdge};
  101. }
  102.  
  103. int main() {
  104.     Matrix cost(N, vector<int>(N));
  105.     cout << "Введите матрицу " << N << "x" << N << " (используйте M для больших значений):\n";
  106.     for (int i = 0; i < N; ++i)
  107.         for (int j = 0; j < N; ++j) {
  108.             string s;
  109.             cin >> s;
  110.             if (s == "M" || s == "m")
  111.                 cost[i][j] = INF;
  112.             else
  113.                 cost[i][j] = stoi(s);
  114.         }
  115.  
  116.     vector<pair<int, int>> path;
  117.     int totalCost = 0;
  118.     Matrix current = cost;
  119.     int level = 0;
  120.  
  121.     while (path.size() < N) {
  122.         cout << "\nИтерация " << level + 1 << ":\n";
  123.  
  124.         // Верхняя граница
  125.         int upperBound = calculateUpperBound(current);
  126.         cout << "Верхняя граница (жадная оценка): " << (upperBound >= INF ? -1 : upperBound) << "\n";
  127.  
  128.         // Z до вычеркивания
  129.         int tempZ = totalCost;
  130.         Matrix temp = current;
  131.         int red1 = reduceRows(temp);
  132.         int red2 = reduceCols(temp);
  133.         int Z = totalCost + red1 + red2;
  134.  
  135.         cout << "Z перед вычеркиванием: " << tempZ << "\n";
  136.         cout << "Редукция по строкам: " << red1 << ", по столбцам: " << red2 << "\n";
  137.         cout << "Z после редукции: " << Z << "\n";
  138.         cout << "Матрица после редукции:\n";
  139.         printMatrix(temp);
  140.  
  141.         auto [penalty, edge] = selectNextEdge(temp);
  142.         int i = edge.first;
  143.         int j = edge.second;
  144.  
  145.         if (i == -1 || j == -1) {
  146.             cout << "Нет подходящего ребра\n";
  147.             break;
  148.         }
  149.  
  150.         cout << "Выбрана дуга: " << char('A' + i) << " → " << char('A' + j) << "\n";
  151.  
  152.         path.push_back({i, j});
  153.         totalCost += cost[i][j];
  154.  
  155.         // Обновляем матрицу: вычеркиваем строку i и столбец j, и запрещаем обратный путь
  156.         for (int k = 0; k < N; ++k) {
  157.             current[i][k] = INF;
  158.             current[k][j] = INF;
  159.         }
  160.         current[j][i] = INF;
  161.  
  162.         level++;
  163.     }
  164.  
  165.     cout << "\nОптимальный путь:\n";
  166.     for (auto [from, to] : path) {
  167.         cout << char('A' + from) << " → " << char('A' + to) << "\n";
  168.     }
  169.     cout << "Общая стоимость пути: " << totalCost << "\n";
  170.  
  171.     return 0;
  172. }
  173.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
M 100 220 150 210
120 M 80 120 130
220 110 M 160 185
150 110 160 M 190
210 130 185 190 M
stdout
copy 
Введите матрицу 5x5 (используйте M для больших значений):

Итерация 1:
Верхняя граница (жадная оценка): 740
Z перед вычеркиванием: 0
Редукция по строкам: 530, по столбцам: 130
Z после редукции: 660
Матрица после редукции:
M  0 120 10 60 
 0 M  0  0  0 
70  0 M 10 25 
 0  0 50 M 30 
40  0 55 20 M 
Выбрана дуга: B → C

Итерация 2:
Верхняя граница (жадная оценка): -1
Z перед вычеркиванием: 80
Редукция по строкам: 500, по столбцам: 65
Z после редукции: 645
Матрица после редукции:
M  0 M 50 85 
M M M M M 
20 M M  0  0 
 0  0 M M 55 
40  0 M 60 M 
Выбрана дуга: C → E

Итерация 3:
Верхняя граница (жадная оценка): -1
Z перед вычеркиванием: 265
Редукция по строкам: 340, по столбцам: 90
Z после редукции: 695
Матрица после редукции:
M  0 M  0 M 
M M M M M 
M M M M M 
 0  0 M M M 
40  0 M 10 M 
Выбрана дуга: D → A

Итерация 4:
Верхняя граница (жадная оценка): -1
Z перед вычеркиванием: 415
Редукция по строкам: 230, по столбцам: 60
Z после редукции: 705
Матрица после редукции:
M  0 M M M 
M M M M M 
M M M M M 
M M M M M 
M  0 M  0 M 
Выбрана дуга: A → B

Итерация 5:
Верхняя граница (жадная оценка): -1
Z перед вычеркиванием: 515
Редукция по строкам: 190, по столбцам: 0
Z после редукции: 705
Матрица после редукции:
M M M M M 
M M M M M 
M M M M M 
M M M M M 
M M M  0 M 
Выбрана дуга: E → D

Оптимальный путь:
B → C
C → E
D → A
A → B
E → D
Общая стоимость пути: 705
https://ideone.com/pjdelv
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!