SHARE
TWEET

Untitled

a guest Apr 22nd, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. fin = open("input.txt")
  2. lines = []
  3. for line in fin:
  4.     lines.append(line)
  5. n = len(lines) - 1
  6. print(n)
  7.  
  8. d = []
  9. smejnost = []
  10. v = []
  11. vstar = []
  12. p = []
  13. inf = 1e9
  14. for i in range(n):
  15.     d.append([])
  16.     p.append([])
  17.     smejnost.append([])
  18.     v.append(0)
  19.     vstar.append([])
  20.     for j in range(n):
  21.         smejnost[i].append(0)
  22.         d[i].append(inf)
  23.         p[i].append(0)
  24.         vstar[i].append(0)
  25.  
  26. for i in range(n):
  27.     s = lines[i]
  28.     a, s = s.split('=')
  29.     ss = s.split(')')
  30.     a = int(a)
  31.     a -= 1
  32.     for c in range(len(ss) - 1):
  33.         sss = ss[c].split('(')
  34.         b, cost = sss[1].split(',')
  35.         b = int(b)
  36.         cost = int(cost)
  37.         b -= 1
  38.         d[a][b] = cost
  39.         smejnost[a][b] = cost
  40. fin.close()
  41.  
  42. mxlen = 0
  43. for i in range(n):
  44.     for j in range(n):
  45.         mxlen = max(mxlen, smejnost[i][j])
  46.  
  47. mxlen *= n
  48. for i in range(n):
  49.     for j in range(n):
  50.         if smejnost[i][j] == -1:
  51.             smejnost[i][j] = mxlen
  52.         d[i][j] = smejnost[i][j]
  53. s = lines[n]
  54. s = s[1:len(s) - 1].split(',')
  55. for c in s:
  56.     a, b = c.split(':')
  57.     a = int(a)
  58.     b = int(b)
  59.     v[a - 1] = b
  60.  
  61. for i in range(n):
  62.     d[i][i] = 0
  63.  
  64. for k in range(n):
  65.     for i in range(n):
  66.         for j in range(n):
  67.             if d[i][k] < inf and d[k][j] < inf:
  68.                 d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  69.  
  70. CBB = []
  71. for i in range(n):
  72.     CBB.append(0)
  73.     for j in range(n):
  74.         CBB[i] += d[i][j]
  75. mediana = 0
  76. for i in range(n):
  77.     if CBB[mediana] > CBB[i]:
  78.         mediana = i
  79.  
  80. MBB = []
  81. for i in range(n):
  82.     MBB.append(d[i][0])
  83.     for j in range(n):
  84.         MBB[i] = max(MBB[i], d[i][j])
  85. center = 0
  86. for i in range(n):
  87.     if MBB[center] > MBB[i]:
  88.         center = i
  89.  
  90. print("Smejnost")
  91. for i in range(n):
  92.     s = ""
  93.     for j in range(n):
  94.         s += str(smejnost[i][j]) + ' '
  95.     print(s)
  96. print("D")
  97. for i in range(n):
  98.     s = ""
  99.     for j in range(n):
  100.         s += str(d[i][j]) + ' '
  101.     print(s)
  102. print("center " + str(center + 1))
  103. print("mediana " + str(mediana + 1))
  104.  
  105. P = inf
  106. for i in range(n):
  107.     for j in range(i + 1, n):
  108.         if smejnost[i][j] > 0 and smejnost[i][j]!=mxlen:
  109.             # print(i+1,j+1,end=': ')
  110.  
  111.             for k in range(n):
  112.                 if k == i or k == j:
  113.                     continue
  114.                 if v[k] * min(d[k][i], d[k][j]) > p[i][j]:
  115.                     vstar[i][j] = k
  116.                     p[i][j] = v[k] * min(d[k][i], d[k][j])
  117.  
  118.                     # print(v[k]*min(d[k][i],d[k][j]),end=', ')
  119.  
  120.                     # print()
  121.                     # print(p[i][j])
  122.  
  123.             P = min(P, p[i][j])
  124. H = inf
  125. for i in range(n):
  126.     for j in range(i + 1, n):
  127.         if smejnost[i][j] > 0:
  128.             H = min(H, p[i][j] + v[vstar[i][j]] * smejnost[i][j] / 2)
  129.  
  130. print("P =", P)
  131. print("H =", H)
  132. print("rebra kotorie ostalis")
  133. for i in range(n):
  134.     for j in range(n):
  135.         if H >= smejnost[i][j] >= P and smejnost[i][j]!=mxlen:
  136.             print(i + 1, j + 1)
  137.         else:
  138.             smejnost[i][j] = 0
  139.  
  140. for i in range(n):
  141.     for j in range(n):
  142.         d[i][j] *= v[j]
  143. print("D")
  144. for i in range(n):
  145.     s = ""
  146.     for j in range(n):
  147.         s += str(d[i][j]) + ' '
  148.     print(s)
  149.  
  150. ok = False
  151. minf = 0
  152. minv1 = 0
  153. minv2 = 0
  154. fepsilon = 0
  155. for i in range(n):
  156.     for j in range(n):
  157.         if smejnost[i][j] > 0 and smejnost[i][j] != mxlen:
  158.             print("Rebro ({},{})".format(i + 1, j + 1))
  159.  
  160.             print("Ksi")
  161.             e = []  # 1 etap
  162.             for k in range(n):
  163.                 brv = d[j][k]
  164.                 alv = d[i][k]
  165.                 vv = v[k]
  166.                 #  print("brv = {} alv = {} vv = {} toapp = {}".format(brv,alv,vv,(brv-alv)/(2*vv)))
  167.                 e.append((brv - alv) / (2 * vv))
  168.             print(e)
  169.  
  170.             print("eps")
  171.             eps = []  # 2 этап
  172.             for v1 in range(n):
  173.                 eps.append([])
  174.                 for v2 in range(n):
  175.                     #           print("Look for {},{}".format(v1, v2))
  176.                     bv1 = d[j][v1]
  177.                     av2 = d[i][v2]
  178.                     vv1 = v[v1]
  179.                     vv2 = v[v2]
  180.                     #        print("bv1 = {} av2 = {} vv1 = {} vv2 = {} toapp = {}".format(bv1,av2,vv1,vv2,(bv1-av2)/(vv1+vv2)))
  181.  
  182.                     eps[v1].append((bv1 - av2) / (vv1 + vv2))
  183.                 print(eps[v1])
  184.  
  185.             print("f")
  186.             f = []  # 3 этап
  187.             found = False
  188.             mnv1 = 0
  189.             mnv2 = 0
  190.             mnf = 0
  191.             for v1 in range(n):
  192.                 f.append([])
  193.                 for v2 in range(n):
  194.                     bv1 = d[j][v1]
  195.                     vv1 = v[v1]
  196.                     f[v1].append(bv1 - vv1 * eps[v1][v2])
  197.                     # if i == 0 and j == 2 and v1 == 1 and v2 == 3:
  198.                     #    print("CHECK ",f[v1][v2])
  199.                     if e[v1] <= eps[v1][v2] <= smejnost[i][j] and 0 < eps[v1][v2] < e[v2]:
  200.                         if not found:
  201.                             found = True
  202.                             mnf = f[v1][v2]
  203.                             mnv1 = v1
  204.                             mnv2 = v2
  205.                         else:
  206.                             if f[v1][v2] < mnf:
  207.                                 mnf = f[v1][v2]
  208.                                 mnv1 = v1
  209.                                 mnv2 = v2
  210.                 print(f[v1])
  211.             print("f* = {} eps = {}".format(mnf, eps[mnv1][mnv2]))
  212.             fl = 0  # 4 ETAP
  213.             fr = 0
  214.             for v1 in range(n):
  215.                 fl = max(fl, d[v1][i])
  216.                 fr = max(fr, d[v1][j])
  217.             print("fl = {} fr = {}".format(fl, fr))
  218.             epsilon = 0
  219.             a = sorted([fl, fr, mnf])
  220.             if a[0] == fr:
  221.                 epsilon = fr
  222.             elif a[0] == mnf:
  223.                 epsilon = eps[mnv1][mnv2]
  224.  
  225.             if not ok:  # 5 etap
  226.                 ok = True
  227.                 fepsilon = epsilon
  228.                 minf = mnf
  229.             else:
  230.                 if mnf < minf:
  231.                     minf = mnf
  232.                     minv1 = i
  233.                     minv2 = j
  234.                     fepsilon = epsilon
  235.             print("f = {} eps = {}".format(minf, epsilon))
  236. print("min f = {}, epsilon = {}, ({},{})".format(minf, fepsilon, minv1 + 1, minv2 + 1))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top