999ms

Untitled

Aug 12th, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct edge
  6. {
  7.     int y, c, f, cost;
  8.     edge() {};
  9.     edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
  10. };
  11.  
  12. vector<edge> e;
  13.  
  14. const int N = 14043;
  15. vector<int> g[N];
  16.  
  17. long long ans = 0;
  18. long long d[N];
  19. int p[N];
  20. int pe[N];
  21. int inq[N];
  22.  
  23. const long long INF64 = (long long)(1e18);
  24.  
  25. int s = N - 2;
  26. int t = N - 1;
  27.  
  28. int rem(int x)
  29. {
  30.     return e[x].c - e[x].f;
  31. }
  32.  
  33. void push_flow()
  34. {
  35.     for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0;
  36.     d[s] = 0;
  37.     queue<int> q;
  38.     q.push(s);
  39.     inq[s] = 1;
  40.     while(!q.empty())
  41.     {
  42.         int k = q.front();
  43.         q.pop();
  44.         inq[k] = 0;
  45.         for(auto x : g[k])
  46.         {
  47.             if(!rem(x)) continue;
  48.             int c = e[x].cost;
  49.             int y = e[x].y;
  50.             if(d[y] > d[k] + c)
  51.             {
  52.                 d[y] = d[k] + c;
  53.                 p[y] = k;
  54.                 pe[y] = x;
  55.                 if(inq[y] == 0)
  56.                 {
  57.                     inq[y] = 1;
  58.                     q.push(y);
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     int cur = t;
  64. //  vector<int> zz(1, cur);
  65.     while(cur != s)
  66.     {
  67.         e[pe[cur]].f++;
  68.         e[pe[cur] ^ 1].f--;
  69.         cur = p[cur];
  70. //      zz.push_back(cur);
  71.     }
  72. //  reverse(zz.begin(), zz.end());
  73. //  for(auto x : zz) cerr << x << " ";
  74. //  cerr << endl;
  75.     ans += d[t];
  76. }
  77.  
  78. void add_edge(int x, int y, int c, int cost)
  79. {
  80.     g[x].push_back(e.size());
  81.     e.push_back(edge(y, c, 0, cost));
  82.     g[y].push_back(e.size());
  83.     e.push_back(edge(x, 0, 0, -cost));
  84. }
  85.  
  86. int main()
  87. {
  88.     int n, m, k, c, d;
  89.     cin >> n >> m >> k >> c >> d;
  90.     for(int i = 0; i < k; i++)
  91.     {
  92.         int x;
  93.         cin >> x;
  94.         --x;
  95.         add_edge(s, x, 1, 0);
  96.     }
  97.     int tt = 101;
  98.     for(int i = 0; i < tt; i++)
  99.         add_edge(0 + i * n, t, k, i * c);
  100.     for(int i = 0; i < m; i++)
  101.     {
  102.         int x, y;
  103.         cin >> x >> y;
  104.         --x;
  105.         --y;
  106.         for(int i = 0; i < tt - 1; i++)
  107.             for(int j = 0; j < k; j++)
  108.                 add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1));
  109.         for(int i = 0; i < tt - 1; i++)
  110.             for(int j = 0; j < k; j++)
  111.                 add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1));
  112.     }
  113.     for(int i = 0; i < n; i++)
  114.         for(int j = 0; j < tt - 1; j++)
  115.             add_edge(i + j * n, i + j * n + n, k, 0);
  116.     for(int i = 0; i < k; i++)
  117.         push_flow();
  118.     cout << ans << endl;
  119. }
Add Comment
Please, Sign In to add comment