[关闭]
@Metralix 2018-03-08T14:41:45.000000Z 字数 4349 阅读 775

寒假训练 DIV1（5）生成树

A - Qin Shi Huang's National Road System

最短路

题目大意

有n个城市，要修一些路使得任意两个城市都能连通。但是有人答应可以不计成本的帮你修一条路，为了使成本最低，你要慎重选择修哪一条路。假设其余的道路长度为B，那条别人帮忙修的道路两端城市中的总人口为B，要找一个使A/B最大的方案。

解题思路

 先求最小生成树，处理出MST中任意两点之间的最长边。因为别人只答应给修一条路，所以枚举这条路，用这条路替换下一条MST中最长的边（在加入这条路后构成的环中），比较求得A/B的最大值。实际上是把求次小生成树的一些后续操作改改。

  1. #include<stack>
  2. #include<queue>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<iostream>
  7. #include<algorithm>
  8. #pragma commment(linker,"/STACK: 102400000 102400000")
  9. using namespace std;
  10. const double eps=1e-6;
  11. const int INF=0x3f3f3f3f;
  12. const int MAXN=1e3+20;
  13. struct city
  14. {
  15.     int x,y,p;
  16. };
  18. city c[MAXN];
  19. int V,par[MAXN];//par数组记录生成树上i的上一个点
  20. bool used[MAXN][MAXN],visit[MAXN];
  21. double mincost[MAXN],cost[MAXN][MAXN],dp[MAXN][MAXN];
  23. double prim()
  24. {
  25.     memset(visit,false,sizeof(visit));
  26.     memset(dp,0,sizeof(dp));
  27.     memset(used,false,sizeof(used));
  28.     for(int i=1; i<=V; i++)
  29.     {
  30.         mincost[i]=cost[1][i];
  31.         par[i]=1;
  32.     }
  33.     visit[1]=true;
  34.     double res=0;
  35.     for(int i=1; i<V; i++)
  36.     {
  37.         int v=-1;
  38.         for(int j=1; j<=V; j++)
  39.             if(!visit[j]&&(v==-1||mincost[j]<mincost[v]))
  40.                 v=j;
  41.         if(v==-1)
  42.             break;
  43.         visit[v]=true;
  44.         used[v][par[v]]=used[par[v]][v]=true;
  45.         res+=mincost[v];
  46.         for(int j=1; j<=V; j++)
  47.         {
  48.             if(!visit[j]&&cost[v][j]<mincost[j])
  49.             {
  50.                 mincost[j]=cost[v][j];
  51.                 par[j]=v;
  52.             }
  53.             if(visit[j]&&j!=v)
  54.             {
  55.                 dp[v][j]=dp[j][v]=max(dp[j][par[v]],mincost[v]);
  56.             }
  57.         }
  58.     }
  59.     return res;
  60. }
  62. int main()
  63. {
  64. #ifndef ONLINE_JUDGE
  65.     freopen("in.txt","r",stdin);
  66. #endif // ONLINE_JUDGE
  67.     int tcase;
  68.     scanf("%d",&tcase);
  69.     while(tcase--)
  70.     {
  71.         scanf("%d",&V);
  72.         for(int i=1; i<=V; i++)
  73.             scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].p);
  74.         for(int i=1; i<=V; i++)
  75.             for(int j=1; j<=V; j++)
  76.                 cost[i][j]=cost[j][i]=sqrt((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y));
  77.         double mst=prim();
  78.         double ans=-1;
  79.         for(int i=1; i<=V; i++)
  80.         {
  81.             for(int j=1; j<=V; j++)
  82.             {
  83.                 if(i==j)
  84.                     continue;
  85.                 if(used[i][j])//i和j之间的边是否在最小生成树上
  86.                     ans=max(ans,(c[i].p+c[j].p+0.0)/(mst-cost[i][j]));
  87.                 else
  88.                     ans=max(ans,(c[i].p+c[j].p+0.0)/(mst-dp[i][j]));
  89.             }
  90.         }
  91.         printf("%.2lf\n",ans);
  92.     }
  93.     return 0;
  94. }

B - Bond

标签： 并查集

题目大意

  给出一张n个点m条边的无向图， 每条边有一个危险度，有q个询问， 每次给出两个点s、t，找一条路， 使得路径上的最大危险度最小。

解题思路

首先，我们可以发现，如果求一个最小生成树， 那么任意两点， 在生成树上有唯一路径， 而且这条路径上的最大危险值一定最小。 但是n和q都太大， 如果直接顺着树走，每次询问最大复杂度O(n)， 那么复杂度高达O(n^2)，会超时。   我们知道， 并查集在用了路径压缩之后效率高达O(n)， 但是却破坏了树形结构， 所以不能用路径压缩。  然而我们经常忽视了按秩合并这个方法， 即使不用路径压缩， 仅仅靠按秩合并， 复杂度也可低至O(logn)。  因此我们只需按秩合并， 然后询问的时候向根回溯就行了， 复杂度mlogn。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <queue>
  6. using namespace std;
  8. const int maxn=55000;
  9. const int maxm=250000;
  10. const int INF=0x3f3f3f3f;
  11. typedef long long LL;
  13. struct HeapNode{
  14.     int d,u;
  15.     HeapNode(){}
  16.     HeapNode(int a,int b):d(a),u(b){}
  17.     bool operator<(const HeapNode& rhs) const{
  18.         return d>rhs.d;
  19.     }
  20. };
  21. struct EdgeNode{
  22.     int to;
  23.     int w;
  24.     int next;
  25. };
  26. struct Prim{
  27.     EdgeNode edges[maxm];
  28.     int head[maxn];
  29.     int edge,n;
  30.     void init(int n){
  31.         this->n=n;
  32.         memset(head,-1,sizeof(head));
  33.         edge=0;
  34.     }
  35.     void addedge(int u,int v,int c){
  36.         edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
  37.     }
  38.     bool done[maxn];
  39.     int dis[maxn];
  40.     int pre[maxn];
  41.     int dep[maxn];
  42.     void prim(int s){
  43.         priority_queue<HeapNode>que;
  44.         for (int i=0;i<=n;i++) dis[i]=INF;
  45.         dis[s]=0;
  46.         memset(done,0,sizeof(done));
  47.         memset(dep,0,sizeof(dep));
  48.         que.push(HeapNode(0,s));
  49.         while (!que.empty()){
  50.             HeapNode x=que.top();
  51.             que.pop();
  52.             int u=x.u;
  53.             if (done[u]) continue;
  54.             done[u]=true;
  55.             for (int i=head[u];i!=-1;i=edges[i].next){
  56.                 int v=edges[i].to;
  57.                 int w=edges[i].w;
  58.                 if (!done[v]&&dis[v]>w){
  59.                     dis[v]=w;
  60.                     pre[v]=u;
  61.                     dep[v]=dep[u]+1;
  62.                     que.push(HeapNode(dis[v],v));
  63.                 }
  64.             }
  65.         }
  66.     }
  67. }solver;
  68. int n,m;
  69. int fa[maxn],cost[maxn],L[maxn];
  70. int anc[maxn][20];
  71. int maxCost[maxn][20];
  73. void preprocess(){
  74.     for (int i=1;i<=n;i++){
  75.         anc[i][0]=fa[i];
  76.         maxCost[i][0]=cost[i];
  77.         for (int j=1;(1<<j)<n;j++) anc[i][j]=-1;
  78.     }
  79.     for (int j=1;(1<<j)<n;j++){
  80.         for (int i=1;i<=n;i++){
  81.             if (anc[i][j-1]!=-1){
  82.                 int a=anc[i][j-1];
  83.                 anc[i][j]=anc[a][j-1];
  84.                 maxCost[i][j]=max(maxCost[i][j-1],maxCost[a][j-1]);
  85.             }
  86.         }
  87.     }
  88. }
  89. int query(int p,int q){
  90.     int log;
  91.     if (L[p]<L[q]) swap(p,q);
  92.     for (log=1;(1<<log)<=L[p];log++);log--;
  93.     int ans=-INF;
  94.     for (int i=log;i>=0;i--){
  95.         if (L[p]-(1<<i)>=L[q]){
  96.             ans=max(ans,maxCost[p][i]);
  97.             p=anc[p][i];
  98.         }
  99.     }
  100.     if (p==q) return ans;
  101.     for (int i=log;i>=0;i--){
  102.         if (anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
  103.             ans=max(ans,maxCost[p][i]);
  104.             p=anc[p][i];
  105.             ans=max(ans,maxCost[q][i]);
  106.             q=anc[q][i];
  107.         }
  108.     }
  109.     ans=max(ans,cost[p]);
  110.     ans=max(ans,cost[q]);
  111.     return ans;
  112. }
  114. int main()
  115. {
  116.     int cas=0;
  117.     while (~scanf("%d%d",&n,&m)){
  118.         if (cas!=0) puts("");
  119.         cas++;
  120.         solver.init(n);
  121.         for (int i=0;i<m;i++){
  122.             int x,y,z;
  123.             scanf("%d%d%d",&x,&y,&z);
  124.             solver.addedge(x,y,z);
  125.             solver.addedge(y,x,z);
  126.         }
  127.         solver.prim(1);
  128.         for (int i=1;i<=n;i++){
  129.             fa[i]=solver.pre[i];
  130.             cost[i]=solver.dis[i];
  131.             L[i]=solver.dep[i];
  132.         }
  133.         preprocess();
  134.         int Q;
  135.         scanf("%d",&Q);
  136.         while (Q--){
  137.             int x,y;
  138.             scanf("%d%d",&x,&y);
  139.             printf("%d\n",query(x,y));
  140.         }
  141.     }
  142.     return 0;
  143. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注