Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Chặt nhị phân + bfs (hoặc dfs cũng đc ._.)
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 1005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m, s, t;
- vector<ii> g[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- cin >> n >> m >> s >> t;
- for(int i=1; i<=m; i++){
- int u, v, w;
- cin >> u >> v >> w;
- g[u].pb(ii(v,w));
- g[v].pb(ii(u,w));
- }
- }
- int d[N];
- bool ok(int z){
- queue<int> q;
- memset(d, -1, sizeof d);
- d[s] = 1;
- q.push(s);
- while (q.size()){
- int u = q.front();
- q.pop();
- for(auto i : g[u]){
- int v = i.fi;
- int uv = i.se;
- if (z <= uv && d[v]==-1){
- d[v] = 1;
- q.push(v);
- }
- }
- }
- return (d[t]!=-1);
- }
- void proc()
- {
- int l = 1, r=1e9;
- int ans = -1;
- while (r-l>0){
- int mid=(l+r)/2;
- if (ok(mid)){
- ans = mid;
- l = mid+1;
- }
- else r = mid;
- }
- cout << ans;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
- //cây khung nhỏ nhất
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 1005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m, s, t;
- struct edges{
- int u, v, w;
- };
- bool cmp(edges a, edges b){
- return a.w > b.w;
- }
- edges a[10005];
- int par[1005];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- cin >> n >> m >> s >> t;
- for(int i=1; i<=m; i++){
- cin >> a[i].u >> a[i].v >> a[i].w;
- }
- for(int i=1; i<=n; i++) par[i] = i;
- sort(a+1,a+1+m,cmp);
- }
- int get(int u){
- return (par[u]==u ? u : par[u] = get(par[u]));
- }
- void join(int u, int v){
- u = get(u);
- v = get(v);
- par[u] = v;
- }
- void proc()
- {
- int ans=-1;
- for(int i=1; i<=m; i++){
- int u = a[i].u;
- int v = a[i].v;
- int w = a[i].w;
- if (get(s)!=get(t)){
- join(u,v);
- ans = w;
- }
- }
- if (get(s)!=get(t)) cout << -1;
- else cout << ans;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement