[关闭]
@darkproject 2018-02-15T23:14:32.000000Z 字数 5309 阅读 836

生成树

2018寒假集训

次小生成树：

基本的思想就是连入一条不在最小生成树上的边，从而形成一个环，去掉在环中并且在最小生成树上最大的边，遍历所有不在最小生成树上的边并进行同样的操作最小值即为次小生成树，简单证明就是连入一条边后去掉一个最大值相当于比原来的值增加的值最小（增加量=添加的边-环上的某一条边(并且这条边在最小生成树上)，添加的边的权值一定，因此使环上的边最大）

A - Qin Shi Huang's National Road System (UVALive - 5713)

n个城市，使其任意连通。我们可以选择一条路不消耗劳动力（这里可以等价于距离0的路）。输入给予每2个城市的坐标和人口，我们要使法术路所连接的人口数量A尽量大，所有连接路的劳动力B尽量小，求A/B的最大值。贪心做法显然不可以。
首先使所有连接路劳动力最小，求出最小生成树.然后枚举法术路，枚举出的法术路有2种情况，在原最小生成树上，在最小生成树外。对于在最小生成树外的情况，我们加入一条0权边，使其有环，我们需要减去在最小生成树上且在环上的最长边（即最小瓶颈路：2点间最长边最短的路径,最小生成树上的最长边即为最小瓶颈路）这样来保证B尽量小。这同时也是次小生成树的思想。对于在最小生成树上的情况，我们直接令此边边权为0即可。
复杂度O(mlogn+)
生成树一般均为无向图，有向的话朱刘。
补充cayley定理：n个结点的完全图中，可以产生个生成树

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. using namespace std;
  7. const int maxn = 1005;
  8. const int inf =0x3f3f3f3f;
  9. double map[maxn][maxn],path[maxn][maxn];
  10. bool used[maxn][maxn];
  11. int pre[maxn];
  12. double dis[maxn];
  13. int t,n,x[maxn],y[maxn],p[maxn];
  14. void init()
  15. {
  16.     for(int i=1;i<=n;i++)
  17.         for(int j=1;j<=n;j++)
  18.         {
  19.             if(i==j) map[i][j]=0;
  20.             else map[i][j]=inf;
  21.         }
  22.     memset(used,0,sizeof(used));
  23.     memset(path,0,sizeof(path));
  24. }
  25. double prim()
  26. {
  27.     double ans=0;
  28.     bool vis[maxn];
  29.     memset(vis,0,sizeof(vis));
  30.     memset(path,0,sizeof(path));
  31.     for(int i=1;i<=n;i++)
  32.     {
  33.         dis[i]=map[1][i];
  34.         pre[i]=1;
  35.     }
  36.     dis[1]=0,vis[1]=1;
  37.     for(int i=2;i<=n;i++)
  38.     {
  39.         double minn=inf;
  40.         int k;
  41.         for(int j=1;j<=n;j++)
  42.         {
  43.             if(!vis[j]&&minn>dis[j])
  44.             {
  45.                 minn=dis[j];
  46.                 k=j;
  47.             }
  48.         }
  49.         ans+=minn;
  50.         vis[k]=1;
  51.         used[k][pre[k]]=used[pre[k]][k]=1;
  52.         //对最小生成树上的边进行标记
  53.         for(int j=1;j<=n;j++)
  54.         {
  55.             if(vis[j]&&j!=k) path[j][k]=path[k][j]=max(path[j][pre[k]],dis[k]);//求2点的最小瓶颈路同时也是最小生成树上2点之间的最长边
  56.             if(!vis[j]&&dis[j]>map[k][j])
  57.             {
  58.                 dis[j]=map[k][j];
  59.                 pre[j]=k;
  60.             }
  61.         }
  62.     }
  63.     return ans;
  64. }
  65. int main()
  66. {
  67.     scanf("%d",&t);
  68.     while(t--)
  69.     {
  70.         scanf("%d",&n);
  71.         init();
  72.         for(int i=1;i<=n;i++)
  73.             scanf("%d%d%d",&x[i],&y[i],&p[i]);
  74.         for(int i=1;i<=n;i++)
  75.             for(int j=i+1;j<=n;j++)
  76.             {
  77.                 int xx=x[i]-x[j];
  78.                 int yy=y[i]-y[j];
  79.                 double d=sqrt((double)xx*xx+yy*yy);
  80.                 map[i][j]=map[j][i]=d;
  81.             }
  82.         double ans=prim();
  83.         double rel=-1;
  84.         for(int i=1;i<=n;i++)
  85.             for(int j=i+1;j<=n;j++)
  86.             {
  87.                 double num=p[i]+p[j];
  88.                 if(!used[i][j])
  89.                 {
  90.                     double tmp=ans-path[i][j];
  91.                     rel=max(rel,num/tmp);
  92.                 }
  93.                 else if(used[i][j])
  94.                 {
  95.                     int xx=x[i]-x[j];
  96.                     int yy=y[i]-y[j];
  97.                     double d=sqrt((double)xx*xx+yy*yy);
  98.                     double tmp=ans-d;
  99.                     rel=max(rel,num/tmp);
  100.                 }
  101.             }
  102.         printf("%.2f\n",rel);
  103.     }
  104.     return 0;
  105. }

D - Slim Span (UVALive - 3887)

含n个结点的无向图，求其所有生成树中最大边减去最小边的值中的最小值。暴力枚举区间[l,r]kruskal求所有生成树。复杂度O()

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn =105;
  7. const int inf = 0x3f3f3f3f;
  8. int par[maxn];
  9. int n,m;
  10. struct mxr
  11. {
  12.     int from,to,w;
  13.     bool operator <(const mxr a)const{
  14.         return w<a.w;
  15.     }
  16. }edge[maxn*maxn];
  17. void init()
  18. {
  19.     for(int i=1;i<=n;i++)
  20.         par[i]=i;
  21. }
  22. int find(int x)
  23. {
  24.     if(x==par[x])
  25.         return x;
  26.     else
  27.         return par[x]=find(par[x]);
  28. }
  29. int main()
  30. {
  31.     while(scanf("%d%d",&n,&m))
  32.     {
  33.         if(n==0&&m==0) break;
  34.         for(int i=1;i<=m;i++)
  35.             scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w);
  36.         sort(edge+1,edge+m+1);
  37.         int ans=inf;
  38.         for(int l=1;l<=m;l++)
  39.         {
  40.             int cnt=0;
  41.             init();
  42.             for(int r=l;r<=m;r++)
  43.             {
  44.                 int x=find(edge[r].from);
  45.                 int y=find(edge[r].to);
  46.                 if(x!=y){
  47.                     par[x]=y;
  48.                     cnt++;
  49.                     if(cnt==n-1){
  50.                         ans=min(ans,edge[r].w-edge[l].w);
  51.                         break;
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         if(ans==inf) printf("-1\n");
  57.         else printf("%d\n",ans);
  58.     }
  59.     return 0;
  60. }

E - ACM Contest and Blackout (UVA - 10600)

无向图，使其连通即求生成树。要求给出花费最小和第二小的方案，即求最小生成树和次小生成树，输出即可裸。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 105;
  7. const int inf = 0x3f3f3f3f;
  8. int map[maxn][maxn],dis[maxn],path[maxn][maxn];
  9. int n,m,q,pre[maxn],t;
  10. bool used[maxn][maxn];
  11. void init()
  12. {
  13.     for(int i=1;i<=n;i++)
  14.         for(int j=1;j<=n;j++)
  15.         {
  16.             if(i==j) map[i][j]=0;
  17.             else map[i][j]=inf;
  18.         }
  19.     memset(used,0,sizeof(used));
  20.     memset(path,0,sizeof(path));
  21. }
  22. int prim()
  23. {
  24.     int ans=0;
  25.     bool vis[maxn];
  26.     memset(vis,0,sizeof(vis));
  27.     for(int i=1;i<=n;i++)
  28.     {
  29.         dis[i]=map[1][i];
  30.         pre[i]=1;
  31.     }
  32.     dis[1]=0,vis[1]=1;
  33.     for(int i=2;i<=n;i++)
  34.     {
  35.         int minn=inf;
  36.         int k;
  37.         for(int j=1;j<=n;j++)
  38.         {
  39.             if(!vis[j]&&minn>dis[j])
  40.             {
  41.                 minn=dis[j];
  42.                 k=j;
  43.             }
  44.         }
  45.         ans+=minn;
  46.         vis[k]=1;
  47.         used[k][pre[k]]=used[pre[k]][k]=1;
  48.         for(int j=1;j<=n;j++)
  49.         {
  50.             if(vis[j]&&j!=k) path[j][k]=path[k][j]=max(path[j][pre[k]],dis[k]);
  51.             if(!vis[j]&&dis[j]>map[k][j]){
  52.                 dis[j]=map[k][j];
  53.                 pre[j]=k;
  54.             }
  55.         }
  56.     }
  57.     return ans;
  58. }
  59. int main()
  60. {
  61.     int mxr,hyx;
  62.     scanf("%d",&t);
  63.     while(t--)
  64.     {
  65.         scanf("%d%d",&n,&m);
  66.         init();
  67.         int a,b,c;
  68.         for(int i=0;i<m;i++)
  69.         {
  70.             scanf("%d%d%d",&a,&b,&c);
  71.             map[a][b]=map[b][a]=c;
  72.         }
  73.         mxr=prim();
  74.         hyx=inf;
  75.         for(int i=1;i<=n;i++)
  76.             for(int j=i+1;j<=n;j++)
  77.             {
  78.                 if(!used[i][j])
  79.                     hyx=min(hyx,mxr+map[i][j]-path[i][j]);
  80.             }
  81.         printf("%d %d\n",mxr,hyx);
  82.     //  printf("\n");
  83.     }
  84.     return 0;
  85. }

G - Arctic Network (UVA - 10369)

有P个地点需要进行通信有2种方式卫星和无线电，卫星交互无距离限制，而无线电有距离限制要求为D，其中有S个地点可以进行卫星交互。要使所有地点均通信成功，且D值尽量小。输出D值。我们求一遍最小生成树，将边排序即可，因为其中有s-1条边不受距离限制，我们排除这S-1条边后下一条边的边权即是我们要求的D值。即排序后的第p-s条边为我们所要的解。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. using namespace std;
  7. const int maxn = 505;
  8. const int inf =0x3f3f3f3f;
  9. int n,s,p,pre[maxn];
  10. double dis[maxn],map[maxn][maxn];
  11. int x[maxn],y[maxn];
  12. double mxr[maxn];
  13. void init()
  14. {
  15.     for(int i=1;i<=p;i++)
  16.         for(int j=1;j<=p;j++)
  17.             if(j==i) map[i][j]=0;
  18.             else map[i][j]=inf;
  19. }
  20. int prim()
  21. {
  22.     int cnt=0;
  23.     bool vis[maxn];
  24.     memset(vis,0,sizeof(vis));
  25.     for(int i=1;i<=p;i++)
  26.     {
  27.         dis[i]=map[1][i];
  28.         pre[i]=1;
  29.     }
  30.     vis[1]=1,dis[1]=0;
  31.     for(int i=2;i<=p;i++)
  32.     {
  33.         double minn=inf;
  34.         int k;
  35.         for(int j=1;j<=p;j++)
  36.         {
  37.             if(!vis[j]&&minn>dis[j])
  38.             {
  39.                 minn=dis[j];
  40.                 k=j;
  41.             }
  42.         }
  43.         vis[k]=1;
  44.         mxr[cnt++]=map[k][pre[k]];
  45.         for(int j=1;j<=p;j++)
  46.         {
  47.             if(!vis[j]&&dis[j]>map[k][j])
  48.             {
  49.                 dis[j]=map[k][j];
  50.                 pre[j]=k;
  51.             }
  52.         }
  53.     }
  54.     return cnt;
  55. }
  56. int main()
  57. {
  58.     scanf("%d",&n);
  59.     while(n--)
  60.     {
  61.         scanf("%d%d",&s,&p);
  62.         for(int i=1;i<=p;i++)
  63.             scanf("%d%d",&x[i],&y[i]);
  64.         for(int i=1;i<=p;i++)
  65.             for(int j=i+1;j<=p;j++)
  66.             {
  67.                 int xx=x[i]-x[j];
  68.                 int yy=y[i]-y[j];
  69.                 double d=sqrt((double)xx*xx+yy*yy);
  70.                 map[i][j]=map[j][i]=d;
  71.             }
  72.         int m=prim();
  73.         sort(mxr,mxr+m);
  74.         printf("%.2f\n",mxr[p-s-1]); 
  75.     }
  76.     return 0;
  77. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注