[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线
这两个题是一样的啊……
让路径上最大值最小当然要玩瓶颈路，瓶颈路需要MST，然后Kruskal求MST时最小边不是不可控的！也就是说我们可以控制最小边，从而求出符合要求的生成树，然后凿出瓶颈路。
所以我们可以直接枚举最小边，然后Kruskal求生成树，之后求瓶颈路。至于是否有解，第一遍Kruskal（第一遍求的其实是MST）之后看看是否联通即可。
不过这个题求瓶颈路个人建议用BFS而不是DFS，且不谈BFS效率高还不易炸堆栈段（尽管这个题没有炸堆栈段的隐患），DFS本身细节就很多，容易错。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 | /************************************************************** 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; // Graphint 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;} // BFSbitset<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 Setint 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);} // MSTstruct 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;} |
