fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define db long double
  10. #define onBit(mask , i) (mask | (1 << i))
  11. #define offBit(mask , i) (mask & (~(1 << i)))
  12.  
  13. template <typename T> using pqmin = priority_queue<T , vector<T> , greater<T>>;
  14. pqmin<pair<long long , int>> pq;
  15. const long long INF = 1e16;
  16. const int N = 1e5 + 7;
  17. int dx[10] = {-1 , -2 , -2 , -1 , 1 , 2 , 2 , 1};
  18. int dy[10] = {-2 , -1 , 1 , 2 , -2 , -1 , 1 , 2};
  19. int n , m , k , pos[N];
  20. long long t[N] , p[N] , dist[N];
  21. vector<pair<int , long long>> a[N];
  22. vector<int> G[N];
  23. int seen[N], iteration = 0;
  24. int matchL[N], matchR[N];
  25.  
  26. void inp(){
  27. 	cin >> n >> m >> k;
  28. 	for (int i = 1 ; i <= k ; ++i) cin >> pos[i];
  29. 	for (int i = 1 ; i <= k ; ++i) cin >> t[i];
  30. 	for (int i = 1 ; i <= k ; ++i) cin >> p[i];
  31. 	for (int i = 1 ; i <= m ; ++i){
  32. 		int u , v;
  33. 		long long w;
  34. 		cin >> u >> v >> w;
  35. 		a[u].push_back({v , w});
  36. 		a[v].push_back({u , w});
  37. 	}
  38. }
  39.  
  40. void dijkstra(int s){
  41. 	for (int i = 1 ; i <= n ; ++i) dist[i] = INF;
  42. 	dist[s] = 0;
  43. 	pq.push({0 , s});
  44. 	while (pq.size()){
  45. 		pair<long long , int> val = pq.top();
  46. 		pq.pop();
  47.  
  48. 		int u = val.se;
  49. 		long long d_u = val.fi;
  50. 		if (d_u > dist[u]) continue;
  51. 		for (auto &c : a[u]){
  52. 			int v = c.fi;
  53. 			long long w = c.se;
  54. 			if (dist[v] > dist[u] + w){
  55. 				dist[v] = dist[u] + w;
  56. 				pq.push({dist[v] , v});
  57. 			}
  58. 		}
  59. 	}
  60. }
  61.  
  62. void ktao(){
  63. 	for (int i = 1 ; i <= k ; ++i){
  64. 		dijkstra(pos[i]);
  65. 		for (int j = 1 ; j <= k ; ++j)
  66. 			if (t[i] + p[i] + dist[pos[j]] <= t[j]) G[pos[i]].push_back(pos[j]);
  67. 	}
  68. }
  69.  
  70.  
  71. bool dfs(int u){
  72.     if (seen[u] == iteration) return false;
  73.     seen[u] = iteration;
  74.  
  75.     for (int v : G[u]) {
  76.         if (matchR[v] == -1) {
  77.             matchL[u] = v;
  78.             matchR[v] = u;
  79.             return true;
  80.         }
  81.     }
  82.  
  83.     for (int v : G[u]) {
  84.         if (dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v])) {
  85.             matchL[u] = v;
  86.             matchR[v] = u;
  87.             return true;
  88.         }
  89.     }
  90.  
  91.     return false;
  92. }
  93.  
  94. int matching(int M, int N) {
  95.     fill(matchL + 1, matchL + M + 1, -1);
  96.     fill(matchR + 1, matchR + N + 1, -1);
  97.  
  98.     int ans = 0;
  99.     while (true) {
  100.         queue<int> q;
  101.         for (int u = 1; u <= M; ++u) {
  102.             if (matchL[u] == -1) {
  103.                 dist[u] = 0;
  104.                 q.push(u);
  105.             } else {
  106.                 dist[u] = -1;
  107.             }
  108.         }
  109.  
  110.         while (!q.empty()) {
  111.             int u = q.front(); q.pop();
  112.             for (int v : G[u]) {
  113.                 if (matchR[v] != -1 && dist[matchR[v]] == -1) {
  114.                     dist[matchR[v]] = dist[u] + 1;
  115.                     q.push(matchR[v]);
  116.                 }
  117.             }
  118.         }
  119.  
  120.         int newMatches = 0;
  121.         ++iteration;
  122.         for (int u = 1; u <= M; ++u) {
  123.             if (matchL[u] == -1) {
  124.                 newMatches += dfs(u);
  125.             }
  126.         }
  127.         if (newMatches == 0) break;
  128.         ans += newMatches;
  129.     }
  130.     return ans;
  131. }
  132.  
  133. void solve(){
  134. 	ktao();
  135. 	cout << k - matching(n , n);
  136. }
  137.  
  138. int main(){
  139. // 	freopen("xhmax.inp" , "r" , stdin);
  140. // 	freopen("xhmax.out" , "w" , stdout);
  141.     faster;
  142.   	inp();
  143. 	solve();	
  144.     return 0;
  145. }
  146. // cnlk
  147.  
Success #stdin #stdout 0.01s 9660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/muMv4e
language:
C++14 (gcc 8.3)
created:
13 days 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!