over 4 years ago

总结有很多:有2004国家集训队论文汪汀《最小生成树问题的扩展》,mato的blog:[http://www.cppblog.com/MatoNo1/archive/2011/05/29/147627.aspx---mato1]
http://www.cppblog.com/MatoNo1/archive/2011/11/16/149812.html——mato2
CQX:http://blog.renren.com/share/235365847/6633394303MARK:这两个我没看懂……】

次小生成树一共有4种做法

1、处理出最小生成树,用o(n^2)的dp预处理o(1)查询来弄出所有点对在最小生成树上最大边,再枚举每一条不在最小生成树上的边,找到差额最小替换,累加到最小生成树的值里即可
prim:o(2n^2+m)【MARK:我已经不知道prim的时间复杂度了,当n^2算的】
kruskal:o(mlogm+2m+n^2)
2、在处理最小生成树时就跟着预处理【MARK:这个方法比较神,感觉不好实现】详见mato的blog:mato1
prim:o(n^2)
kruskal:O(M*(logN+logM))【注意这里的小优化】
即为:①、合并并查集时从小树遍历 ②、每次找到边(i, j)后,一处理完这条边就把它从图中删掉,因为当S1和S2合并后,(i, j)就永远不可能再是可行变换中的E2了。
3、还有一种除去最小生成树部分后类tarjan算法o(n)来搞的……颓太多搞得竟然不想看了【MARK!!!】详见CQX或者AHdoc的人人
4、处理最小生成树后,求出lca,枚举每条未加入的边,用logn的时间求mst上两点间的最大值。在这里要注意一个问题,如果要求严格最小生成树,那分为两种情况:①枚举的边权==两点间最大值,这是要记录两点间次大值(严格的),delta为边权-次大值 ②枚举的边权!=两点间最大值,就正常做,delta为边权-最大值
prim:(n^2+nlogn+2mlogn)
kruskal:(mlogm+m+2mlogn)

PAY ATTENTION:

prim:注意三种特殊情况:【1】图G不连通,此时最小生成树和次小生成树均不存在。判定方法:在扩展T的过程中找不到新的可以加入的边;【2】图G本身就是一棵树,此时最小生成树存在(就是G本身)但次小生成树不存在。判定方法:在成功求出T后,发现邻接矩阵中的值全部是无穷大;【3】图G存在平行边。这种情况最麻烦,因为这时代价最小的可行变换(-E1, +E2)中,E1和E2可能是平行边!因此,只有建立两个邻接矩阵,分别存储每两点间权值最小的边和权值次小的边的权值,然后,每当一条新边(i, j)加入时,不是将邻接矩阵中边(i, j)权值改为无穷大,而是改为连接点i、j的权值次小的边的权值。

kruskal:对于三种特殊情况:【1】图G不连通。判定方法:遍历完所有的边后,实际加入T的边数小于(N-1);【2】图G本身就是一棵树。判定方法:找不到这样的边(i, j);【3】图G存在平行边。这个对于Kruskal来说完全可以无视,因为Kruskal中两条边只要编号不同就视为不同的边。

本题

对于bzoj1977最小生成树,因为是稀疏图而数据又很大,所以1不适用,我用4来写的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define maxn 100001
#define maxm 300001
using namespace std;
struct wide{int u,v,w;}a[maxm];
bool can[maxm]={0};
int next[maxn*2],point[maxn],u[maxn*2],v[maxn*2],w[maxn*2];
int lca[maxn][20]={0},cost[maxn][20]={0},dfn[maxn]={0},fa[maxn]={0},f[maxn]={0};
int fir,sec,minn=2143456789,deep=0,n,m,widen=0;
long long result=0; 
int readln()
{
 char c=getchar();int bj=1,result=0;
 while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
        if (c=='-') bj=-1,c=getchar();
      while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
bool cmp(const wide a,const wide b)
{
  return a.w<b.w; 
} 
int find(int x)
{
   if (f[x]==x) return x;return f[x]=find(f[x]);
}
void addedge(int x,int y,int z)
{
  widen++;next[widen]=point[x];point[x]=widen;u[widen]=x;v[widen]=y;w[widen]=z;
       widen++;next[widen]=point[y];point[y]=widen;u[widen]=y;v[widen]=x;w[widen]=z;
}
void dfs(int father,int x,int step)
{
      dfn[x]=step;deep=max(deep,step);
    for (int k=point[x];k!=0;k=next[k])
         if (v[k]!=father)
           {
                   fa[v[k]]=father;
                    lca[v[k]][0]=x;cost[v[k]][0]=w[k];
                  dfs(x,v[k],step+1);
         }
}
void prepare()
{
       int i,j,border=(int)ceil(log(deep)/(double)log(2));
 for (i=1;i<=border;i++)
          for (j=1;j<=n;j++)
               {lca[j][i]=lca[lca[j][i-1]][i-1];
             cost[j][i]=max(cost[j][i-1],cost[lca[j][i-1]][i-1]);}
}
void query(int x,int y)
{   fir=sec=0;
   if (dfn[x]<dfn[y]) {int o=x;x=y;y=o;}
    int i,border=(int)ceil(log(deep)/(double)log(2));
   for (i=border;i>=0;i--)
          if (dfn[lca[x][i]]>=dfn[y])
              {
                   if (cost[x][i]>fir) {sec=fir;fir=cost[x][i];}
                            else if (cost[x][i]<fir&&cost[x][i]>sec) sec=cost[x][i];
                      x=lca[x][i];
                }
   for (i=border;i>=0;i--)
          if (lca[x][i]!=lca[y][i])
           {
                   if (cost[x][i]>fir) {sec=fir;fir=cost[x][i];}
                            else if (cost[x][i]<fir&&cost[x][i]>sec) sec=cost[x][i];
                      if (cost[y][i]>fir) {sec=fir;fir=cost[y][i];}
                            else if (cost[y][i]<fir&&cost[y][i]>sec) sec=cost[y][i];
                      x=lca[x][i];y=lca[y][i];
            }
   if (lca[x][0]==lca[y][0])
   {
                   if (cost[x][0]>fir) {sec=fir;fir=cost[x][0];}
                    else if (cost[x][0]<fir&&cost[x][0]>sec) sec=cost[x][0];
                      if (cost[y][0]>fir) {sec=fir;fir=cost[y][0];}
                    else if (cost[y][0]<fir&&cost[y][0]>sec) sec=cost[y][0];
      }
}
int main()
{
   int i,j,tot=0,x,y,delta; 
   n=readln();m=readln();
      for (i=1;i<=m;i++){a[i].u=readln();a[i].v=readln();a[i].w=readln();}
     sort(a+1,a+m+1,cmp);
        for (i=1;i<=n;i++) f[i]=i;
       for (i=1;i<=m;i++)
       {
           x=find(a[i].u);y=find(a[i].v);
              if (x!=y) {result+=a[i].w;can[i]=true;addedge(a[i].u,a[i].v,a[i].w);tot++;f[x]=y;if (tot==n-1) break;}
      }
   dfs(0,1,1);
 prepare();
  for (i=1;i<=m;i++)
               if(!can[i]) 
                {
                   query(a[i].u,a[i].v);
                       if (fir==a[i].w) delta=a[i].w-sec;
                  else delta=a[i].w-fir;
                      minn=min(minn,delta);
               }
   printf("%lld\n",result+minn);
}
← 【bzoj2423】最长公共子序列 【spoj104】【生成树计数】highways →
 
comments powered by Disqus