Advertisement
MinhNGUYEN2k4

Untitled

Aug 29th, 2021
1,145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.20 KB | None | 0 0
  1. //Chặt nhị phân + bfs (hoặc dfs cũng đc ._.)
  2. //Nguyen Huu Hoang Minh
  3. #include <bits/stdc++.h>
  4. #define sz(x) int(x.size())
  5. #define all(x) x.begin(),x.end()
  6. #define reset(x) memset(x, 0,sizeof(x))
  7. #define pb push_back
  8. #define mp make_pair
  9. #define fi first
  10. #define se second
  11. #define N 1005
  12. #define remain(x) if (x > MOD) x -= MOD
  13. #define ii pair<int, int>
  14. #define iiii pair< ii , ii >
  15. #define viiii vector< iiii >
  16. #define vi vector<int>
  17. #define vii vector< ii >
  18. #define bit(x, i) (((x) >> (i)) & 1)
  19. #define Task "test"
  20. #define int long long
  21.  
  22. using namespace std;
  23.  
  24. typedef long double ld;
  25. const int inf = 1e10;
  26. const int minf = -1e10;
  27.  
  28. int n, m, s, t;
  29. vector<ii> g[N];
  30.  
  31. void readfile()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(0);cout.tie(0);
  35.     cin >> n >> m >> s >> t;
  36.     for(int i=1; i<=m; i++){
  37.         int u, v, w;
  38.         cin >> u >> v >> w;
  39.         g[u].pb(ii(v,w));
  40.         g[v].pb(ii(u,w));
  41.     }
  42. }
  43.  
  44. int d[N];
  45.  
  46. bool ok(int z){
  47.     queue<int> q;
  48.     memset(d, -1, sizeof d);
  49.     d[s] = 1;
  50.     q.push(s);
  51.     while (q.size()){
  52.         int u = q.front();
  53.         q.pop();
  54.         for(auto i : g[u]){
  55.             int v = i.fi;
  56.             int uv = i.se;
  57.             if (z <= uv && d[v]==-1){
  58.                 d[v] = 1;
  59.                 q.push(v);
  60.             }
  61.         }
  62.     }
  63.     return (d[t]!=-1);
  64. }
  65.  
  66. void proc()
  67. {
  68.     int l = 1, r=1e9;
  69.     int ans = -1;
  70.     while (r-l>0){
  71.         int mid=(l+r)/2;
  72.         if (ok(mid)){
  73.             ans = mid;
  74.             l = mid+1;
  75.         }
  76.         else r = mid;
  77.     }
  78.     cout << ans;
  79. }
  80.  
  81. signed main()
  82. {
  83.     readfile();
  84.     proc();
  85.     return 0;
  86. }
  87.    
  88. //cây khung nhỏ nhất
  89. //Nguyen Huu Hoang Minh
  90. #include <bits/stdc++.h>
  91. #define sz(x) int(x.size())
  92. #define all(x) x.begin(),x.end()
  93. #define reset(x) memset(x, 0,sizeof(x))
  94. #define pb push_back
  95. #define mp make_pair
  96. #define fi first
  97. #define se second
  98. #define N 1005
  99. #define remain(x) if (x > MOD) x -= MOD
  100. #define ii pair<int, int>
  101. #define iiii pair< ii , ii >
  102. #define viiii vector< iiii >
  103. #define vi vector<int>
  104. #define vii vector< ii >
  105. #define bit(x, i) (((x) >> (i)) & 1)
  106. #define Task "test"
  107. #define int long long
  108.  
  109. using namespace std;
  110.  
  111. typedef long double ld;
  112. const int inf = 1e10;
  113. const int minf = -1e10;
  114.  
  115. int n, m, s, t;
  116. struct edges{
  117.     int u, v, w;
  118. };
  119. bool cmp(edges a, edges b){
  120.     return a.w > b.w;
  121. }
  122. edges a[10005];
  123. int par[1005];
  124.  
  125. void readfile()
  126. {
  127.     ios_base::sync_with_stdio(false);
  128.     cin.tie(0);cout.tie(0);
  129.     cin >> n >> m >> s >> t;
  130.     for(int i=1; i<=m; i++){
  131.         cin >> a[i].u >> a[i].v >> a[i].w;
  132.     }
  133.     for(int i=1; i<=n; i++) par[i] = i;
  134.     sort(a+1,a+1+m,cmp);
  135. }
  136.  
  137. int get(int u){
  138.     return (par[u]==u ? u : par[u] = get(par[u]));
  139. }
  140.  
  141. void join(int u, int v){
  142.     u = get(u);
  143.     v = get(v);
  144.     par[u] = v;
  145. }
  146.  
  147. void proc()
  148. {
  149.     int ans=-1;
  150.     for(int i=1; i<=m; i++){
  151.         int u = a[i].u;
  152.         int v = a[i].v;
  153.         int w = a[i].w;
  154.         if (get(s)!=get(t)){
  155.             join(u,v);
  156.             ans = w;
  157.         }
  158.     }
  159.     if (get(s)!=get(t)) cout << -1;
  160.     else cout << ans;
  161. }
  162.  
  163. signed main()
  164. {
  165.     readfile();
  166.     proc();
  167.     return 0;
  168. }
  169.    
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement