[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线
转载请注明出处:http://danihao123.is-programmer.com/
这两个题是一样的啊……
让路径上最大值最小当然要玩瓶颈路,瓶颈路需要MST,然后Kruskal求MST时最小边不是不可控的!也就是说我们可以控制最小边,从而求出符合要求的生成树,然后凿出瓶颈路。
所以我们可以直接枚举最小边,然后Kruskal求生成树,之后求瓶颈路。至于是否有解,第一遍Kruskal(第一遍求的其实是MST)之后看看是否联通即可。
不过这个题求瓶颈路个人建议用BFS而不是DFS,且不谈BFS效率高还不易炸堆栈段(尽管这个题没有炸堆栈段的隐患),DFS本身细节就很多,容易错。
代码:
/************************************************************** Problem: 1050 User: danihao123 Language: C++ Result: Accepted Time:3588 ms Memory:1172 kb ****************************************************************/ #include <cstdio> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <bitset> #include <vector> #include <queue> using namespace std; const int maxn=501,maxm=10001; #define REP(i,n) for(i=0;i<(n);i++) #define REPB(i,n) for(i=1;i<=(n);i++) #define CUS_REP(i,u,v) for(i=(u);i<(v);i++) #define REP_G(i,u) for(i=first[u];i;i=next[i]) #define CL_ARR(x,v) memset(x,v,sizeof(x)) typedef pair<int,int> pii; int n; int S,T; // Graph int first[maxn]; int next[maxm],to[maxm],dist[maxm]; int G_cnt=0; inline void Add_Edge(int u,int v,int d){ G_cnt++; next[G_cnt]=first[u]; first[u]=G_cnt; to[G_cnt]=v; dist[G_cnt]=d; } inline void Clear_Graph(){ CL_ARR(first,0); CL_ARR(next,0); CL_ARR(to,0); CL_ARR(dist,0); G_cnt=0; } // BFS bitset<maxn> vis; struct Node{ int x,maxv,minv; }; pii BFS(){ register int a,b,i; queue<Node> Q; Node tt; Q.push((Node){S,-1,0x7fffffff}); vis[S]=true; while(!Q.empty()){ tt=Q.front(); Q.pop(); if(tt.x==T) return make_pair(tt.maxv,tt.minv); REP_G(i,tt.x){ if(!vis[to[i]]){ vis[to[i]]=true; Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])}); } } } } // BINGCHA Set int p[maxn],rank[maxn]; int find_set(int x){ if(p[x]==x) return x; else return p[x]=find_set(p[x]); } void link_set(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; }else{ p[x]=y; if(rank[x]==rank[y]) rank[y]++; } } inline void union_set(int x,int y){ link_set(find_set(x),find_set(y)); } inline bool is_same(int x,int y){ return find_set(x)==find_set(y); } inline void init_set(){ register int i; for(i=1;i<=n;i++) p[i]=i; CL_ARR(rank,0); } // MST struct Edge{ int u,v,d; bool operator <(const Edge& x) const{ return d<x.d; } }; vector<Edge> E; bool OK=false; pii ans; void MST(int x){ register int i,a,b,cnt=0; pii que; register double jia,yi; Clear_Graph(); init_set(); CUS_REP(i,x,E.size()){ if(!is_same(E[i].u,E[i].v)){ Add_Edge(E[i].u,E[i].v,E[i].d); Add_Edge(E[i].v,E[i].u,E[i].d); cnt++; union_set(E[i].u,E[i].v); if(cnt==n-1) break; } } if(is_same(S,T)){ OK=true; }else{ return; } vis.reset(); que=BFS(); a=que.first; b=que.second; jia=((double)a)/((double)b); yi=(double(ans.first))/(double(ans.second)); if(jia<yi){ ans.first=a; ans.second=b; } } int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } // I/O优化 inline int readint(){ char c=getchar(); register int x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); } return x; } int main(){ int m; register int i,u,v,d; n=readint(); m=readint(); REP(i,m){ u=readint(); v=readint(); d=readint(); E.push_back((Edge){u,v,d}); } S=readint(); T=readint(); sort(E.begin(),E.end()); ans.first=0x7fffffff; ans.second=1; REP(i,m){ MST(i); if(!OK){ if(!i){ puts("IMPOSSIBLE"); return 0; }else{ break; } } } d=gcd(ans.first,ans.second); ans.first/=d; ans.second/=d; if(ans.second==1) printf("%d\n",ans.first); else printf("%d/%d\n",ans.first,ans.second); return 0; }
Jul 04, 2023 11:32:19 AM
Our team consists of experts. Publishing education updates in the interest of transparency is a cause dear to the hearts of writers and citizen journalists with a diverse range of media interests, as well as 10thmodelquestionpaper.in an initiative of skilled journalists who have gathered for specialised news coverage of recent occurrences across the country.