Untitled

By Sole Kangaroo, ago, written in C++.
URL http://pastecode.org/index.php/view/92433435
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
  1. Виталий Павленко
  2. ЮграНефтеТранс(Частичное решение)
  3. 115
  4. #define _CRT_SECURE_NO_WARNINGS
  5.  
  6. #include <cstdio>
  7. #include <iostream>
  8. #include <cstdlib>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <algorithm>
  12. #include <vector>
  13.  
  14. using namespace std;
  15.  
  16. const int maxn = 2010;
  17. const int maxm = 100100;
  18. const double T0 = 100;
  19. const int maxk = 50;
  20.  
  21. double alpha = 0.99;
  22.  
  23. struct solution {
  24.         bool a[maxn];
  25.         int cost;
  26. };
  27.  
  28. int n, m, k, t = 0;
  29. double T = T0;
  30. pair<int, int> edges[maxm];
  31. vector< vector <int> > adj(maxn, vector<int> ());
  32. solution curr, next, best;
  33. int a[maxk];
  34. bool b[maxn];
  35.  
  36. void check() {
  37.         bool flag = true;
  38.         for (int i = 0; i < m; ++i)
  39.                 flag = flag && (b[edges[i].first] || b[edges[i].second]);
  40.         if (flag) {
  41.                 printf("Yes\n");
  42.                 for (int i = 1; i <= k; ++i)
  43.                         printf("%d ", a[i] + 1);
  44.                 exit(0);
  45.         }       
  46. }
  47.  
  48. void rec(int level) {
  49.         for (int i = a[level - 1] + 1; i < n; ++i) {
  50.                 a[level] = i;
  51.                 b[i] = true;
  52.                 if (level < k) {
  53.                         rec(level + 1);
  54.                 } else {
  55.                         check();
  56.                 }
  57.                 b[i] = false;
  58.         }
  59. }
  60.  
  61. void alternate() {
  62.         a[0] = -1;
  63.         for(int i = 0; i < n; ++i)
  64.                 b[i] = false;
  65.         rec(1);
  66. }
  67.  
  68. void setcost(solution& sol) {
  69.         sol.cost = m;
  70.         for(int i = 0; i < m; ++i) {
  71.                 if (sol.a[edges[i].first] || sol.a[edges[i].second])
  72.                         sol.cost--;
  73.         }
  74. }
  75.  
  76. int calcbadedges(int vertex, solution& sol) {
  77.         int res = 0;
  78.         for(int i = 0; i < int(adj[vertex].size()); i++) {
  79.                 if (!(sol.a[edges[adj[vertex][i]].first] || sol.a[edges[adj[vertex][i]].second]))
  80.                         res++;
  81.         }
  82.         return res;
  83. }
  84.  
  85. void setnext(solution& sol) {
  86.         int before, after;
  87.         for(int cnt = 0; cnt <= T; ++cnt) {
  88.                 int a = rand() % n, b = rand() % n;
  89.                 before = calcbadedges(a, sol) + calcbadedges(b, sol);
  90.                 swap(sol.a[a], sol.a[b]);
  91.                 after = calcbadedges(a, sol) + calcbadedges(b, sol);
  92.                 sol.cost -= before - after;
  93.         }
  94. //      setcost(sol);
  95. }
  96.  
  97. bool admit(int dF) {
  98.         return dF < 0 || exp(-dF / T) > rand() / double(RAND_MAX);
  99. }
  100.  
  101. int main() {
  102.         clock_t start = clock();
  103.         srand(3271);
  104.  
  105. //      freopen("pipeline.in", "r", stdin);
  106. //      freopen("pipeline.out", "w", stdout);
  107.         scanf("%d%d%d", &n, &m, &k);
  108.         for(int i = 0; i < m; ++i) {
  109.                 scanf("%d%d", &edges[i].first, &edges[i].second);
  110.                 edges[i].first--;
  111.                 edges[i].second--;
  112.                 adj[edges[i].first].push_back(i);
  113.                 adj[edges[i].second].push_back(i);
  114.         }
  115.         if (m * pow(double(n), k) < 10000000) {
  116.                 cerr << "brute force\n";
  117.                 alternate();
  118.                 printf("No\n");
  119.                 return 0;
  120.         }
  121.         cerr << "annealing\n";
  122.         T = n;
  123.         alpha = pow(1 / T, m / 1200000.0);
  124. //      printf("alpha: %f\n", alpha);
  125.         for(int i = 0; i < k; ++i) {
  126.                 curr.a[i] = true;
  127.         }
  128.         for(int i = k; i < n; ++i) {
  129.                 curr.a[i] = false;
  130.         }
  131.         setcost(curr);
  132.         best = curr;
  133.         int t = 0;
  134.  
  135.         while(best.cost > 0) {
  136.                 t++;
  137.                 next = curr;
  138.                 setnext(next);
  139.                 if (admit(next.cost - curr.cost)) {
  140.                         curr = next;
  141.                         if (curr.cost < best.cost)
  142.                                 best = curr;
  143.                 }
  144.                 if (t > (1000000.0 / m) / 1000) {
  145.                         if ((clock() - start) / double(CLOCKS_PER_SEC) > 1.95) {
  146.                                 printf("No\n");
  147. //                              printf("t = %d, T = %f\n", t, T);
  148.                                 return 0;
  149.                         }
  150.                 }
  151.                 t++;
  152.                 T *= alpha;
  153.         }
  154.         //printf("t = %d, T = %f\n", t, T);
  155.         printf("Yes\n");
  156.         for(int i = 0; i < n; ++i)
  157.                 if (best.a[i])
  158.                         printf("%d ", i + 1);
  159.         scanf("\n");
  160.         return 0;
  161. }

Here you can reply to the paste above

Make Private

   

Feeling clever? Set some advanced options.