做网站的股哥,网站教程dw,广告模板在哪个网站好,网站需求设计文档牛客地址
题意#xff1a;中文题目很简单#xff0c;就是每条路径有一个w权值#xff0c;你要从s到t#xff0c;问你#xff0c;从s到t的路径中#xff0c;w的最小值为L#xff0c;最大值为R#xff0c;你要保证L尽可能的大的情况下R尽量小#xff0c;输出该L和R值
…牛客地址
题意中文题目很简单就是每条路径有一个w权值你要从s到t问你从s到t的路径中w的最小值为L最大值为R你要保证L尽可能的大的情况下R尽量小输出该L和R值
思路可以先从权值最大的边开始添加然后s和t是连通的话那么就说明L的最大值就为这个再大就无法连通了在这个基础上我们从L开始再找R的最小值完事。
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
const ll mod1e97;
const ll N 3e610;
const double eps 1e-6;
const double piacos(-1);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};
ll n,m,s,t;
ll p[N];
struct p
{ll u,v,w;bool operator(const p M)const{return wM.w;}
}a[N];
ll f(ll x) {return xp[x]?p[x]:p[x]f(p[x]);}
void solve()
{cinnmst;for(ll i1;in;i) p[i]i;for(ll i1;im;i){ll u,v,w;cinuvw;a[i]{u,v,w};}sort(a1,a1m);ll lpos,rpos;for(lposm;lpos1;lpos--){ll ua[lpos].u;ll va[lpos].v;if(f(u)!f(v)){p[f(u)]f(v);}if(f(s)f(t)) break;}for(ll i1;in;i) p[i]i;for(rposlpos;rposm;rpos){ll ua[rpos].u;ll va[rpos].v;if(f(u)!f(v)){p[f(u)]f(v);}if(f(s)f(t)) break;}couta[lpos].w a[rpos].w;
}
int main()
{iosint T;//cinT;T1;while(T--){solve();}return 0;
}
