SHARE
TWEET

Untitled

a guest Sep 13th, 2017 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.IO;
  6.  
  7. namespace locopt
  8. {
  9.     class Lab
  10.     {
  11.         int n;
  12.         int[,] Way;
  13.         List<int> d = new List<int>();
  14.         public Lab()
  15.         {
  16.             StreamReader Sr = new StreamReader("salesmanopt.in");
  17.             n = int.Parse(Sr.ReadLine());
  18.             Way = new int[n, n];
  19.             for (int i = 0; i < n; i++)
  20.             {
  21.                 string[] line = Sr.ReadLine().Split(" ".ToArray(), StringSplitOptions.RemoveEmptyEntries);
  22.                 for (int j = 0; j < n; j++)
  23.                 {
  24.                     Way[i, j] = int.Parse(line[j]);
  25.                 }
  26.             }
  27.             d = new List<int>();
  28.             GetBestWay();
  29.         }
  30.         void swap(int i, int j)
  31.         {
  32.             int c = d[i];
  33.             d[i] = d[j];
  34.             d[j] = c;
  35.         }
  36.         private void GetBestWay()
  37.         {
  38.             bool[] isgood = new bool[n];
  39.             isgood[0] = false;
  40.             for (int hg = 1; hg < n; hg++) { isgood[hg] = true; }
  41.             d.Add(0);
  42.             while (d.Count != n)
  43.             {
  44.                 double Min = int.MaxValue;
  45.                 int min = 0;
  46.                 int k = d[d.Count - 1];
  47.                 for (int i = 0; i < n; i++)
  48.                 {
  49.                     if (Way[k, i] < Min && k != i && isgood[i] == true)
  50.                     {
  51.                         min = i;
  52.                         Min = Way[k, i];
  53.                     }
  54.                 }
  55.                 d.Add(min);
  56.                 isgood[min] = false;
  57.             }
  58.             Sic();
  59.         }
  60.  
  61.         private void Sic()
  62.         {
  63.             StreamWriter sw = new StreamWriter("salesmanopt.out");
  64.             string r = "";
  65.             for (int p = 0; p < n; p++)
  66.             {
  67.                 r += d[p].ToString();
  68.                 if (p != n - 1)
  69.                 {
  70.                     r += " ";
  71.                 }
  72.             }
  73.             sw.WriteLine(r);
  74.             while (true)
  75.             {
  76.                 bool good = false;
  77.                 for (int i = 1; i < n; i++)
  78.                 {
  79.                     for (int j = i + 1; j < n; j++)
  80.                         if (j == i + 1)
  81.                         {
  82.                             if (checkFirst(i, j) == true)
  83.                             {
  84.                                 string r1 = i.ToString() + " " + j.ToString();
  85.                                 sw.WriteLine(r1);
  86.                                 swap(i, j);
  87.                                 good = true;
  88.                                 break;
  89.                             }
  90.                         }
  91.                         else
  92.                         {
  93.                             if (checkSecond(i, j) == true)
  94.                             {
  95.                                 string r2 = i.ToString() + " " + j.ToString();
  96.                                 sw.WriteLine(r2);
  97.                                 swap(i, j);
  98.                                 good = true;
  99.                                 break;
  100.                             }
  101.                         }
  102.                     if (good == true) break;
  103.                 }
  104.                 if (good == false) break;
  105.             }
  106.             sw.WriteLine("optimal");
  107.             sw.Close();
  108.         }
  109.         private bool checkFirst(int i, int j)
  110.         {
  111.             if (Way[d[i - 1], d[i]] + Way[d[i], d[j]] + Way[d[j], d[(j + 1) % n]] >
  112.                                 Way[d[i - 1], d[j]] + Way[d[j], d[i]] + Way[d[i], d[(j + 1) % n]])
  113.             {
  114.                 return true;
  115.             }
  116.             else return false;
  117.         }
  118.         private bool checkSecond(int i, int j)
  119.         {
  120.             if (Way[d[i - 1], d[i]] + Way[d[i], d[i + 1]] + Way[d[j - 1], d[j]] + Way[d[j], d[(j + 1) % n]] >
  121.                                 Way[d[i - 1], d[j]] + Way[d[j], d[i + 1]] + Way[d[j - 1], d[i]] + Way[d[i], d[(j + 1) % n]])
  122.             {
  123.                 return true;
  124.             }
  125.             else return false;
  126.         }
  127.     }
  128.  
  129.     class Program
  130.     {
  131.         static void Main(string[] args)
  132.         {
  133.             Lab x = new Lab();
  134.         }
  135.     }
  136. }
RAW Paste Data
Top