首页 > 代码库 > 【KM】BZOJ1937 [Shoi2004]Mst 最小生成树

【KM】BZOJ1937 [Shoi2004]Mst 最小生成树

这道题拖了好久因为懒,结果1A了,惊讶∑( 口 ||

【题目大意】

给定一张n个顶点m条边的有权无向图。现要修改各边边权,使得给出n-1条边是这张图的最小生成树,代价为变化量的绝对值。求最小代价之和。

【思路】

思路有点神,并不是我这种蒟蒻能够想到的XD

显然由贪心,树边必定变成wi-di,非树边必定变成wi+di (di≥0)

为了满足Mst的性质,考察一条非树边j,它加最小生成树后,必定构成一个环。对于环上的每一条树边i,有wi-di≤wj+dj,即di+dj≥wi-wj。这非常类似于KM的形式x[i]+y[i]≥wt[i][j]。

那么我们就如下操作:对于最小生成树,先预处理出所有节点的深度。对于一条非树边E(u,v),求出lca(u,v)。对于u->lca,lca->v上的每一条树边,由树边向非树边连一条(w树边-w非树边)的边。然后跑KM。

注意这个值可能小于0,由于变化量的绝对值之和必定大于0,我们就取为0即可。

【错误点】

lca和KM都写挂了一发orz

LCA的时候忘记了swim后,若u==v,返回u。

KM取slack的时候是取min的。

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<vector>   6 #include<cmath>  7 using namespace std;  8 const int MAXN=55;  9 const int MAXM=800+50; 10 const int INF=0x7fffffff; 11 struct Edge 12 { 13     int u,v,w,t; 14 }edge[MAXM]; 15 vector<int> E[MAXN]; 16 int val[MAXM][MAXM]; 17 int dep[MAXN],anc[MAXN][20],faedge[MAXN]; 18 int cnt,m,n; 19  20 /**build tree**/ 21 void addedge(int u,int v,int w) 22 { 23     edge[++cnt]=(Edge){u,v,w,0}; 24     E[u].push_back(cnt); 25     E[v].push_back(cnt); 26 } 27  28 void dfs(int rt,int fa,int id) 29 { 30     dep[rt]=dep[fa]+1; 31     anc[rt][0]=fa; 32     faedge[rt]=id; 33     for (int i=0;i<E[rt].size();i++) 34     { 35         int now=E[rt][i]; 36         if (edge[now].t && edge[now].u!=fa && edge[now].v!=fa) 37         { 38             if (edge[now].u==rt) dfs(edge[now].v,rt,now); 39                 else dfs(edge[now].u,rt,now); 40         } 41     } 42 } 43  44 /*lca*/ 45 int getanc() 46 { 47     for (int i=1;i<20;i++) 48         for (int j=1;j<=n;j++) 49             anc[j][i]=anc[anc[j][i-1]][i-1]; 50 } 51  52 int swim(int u,int H) 53 { 54     int i=0; 55     while (H>0) 56     { 57         if (H&1) u=u[anc][i]; 58         H>>=1; 59         i++; 60     } 61     return u; 62 } 63  64 int LCA(int u,int v) 65 { 66     if (dep[u]<dep[v]) swap(u,v); 67     if (dep[u]!=dep[v]) u=swim(u,dep[u]-dep[v]); 68     if (u==v) return u;//不要忘了这句语句 69     for (int i=19;i>=0;i--) 70     { 71         if (anc[u][i]!=anc[v][i]) 72         { 73             u=anc[u][i]; 74             v=anc[v][i]; 75         } 76     } 77     return anc[u][0]; 78 } 79  80  81 /*KM*/ 82  83 void Addedge(int u,int v,int w) 84 { 85     val[u][v]=max(w,0);//由于两条边的变化量的绝对值之和不可能为负数,则必定设为0 ☆☆☆☆☆☆  86 } 87  88 void build(int a,int b,int id) 89 { 90     if (dep[a]<dep[b]) swap(a,b); 91     while (a!=b) 92     { 93         Addedge(faedge[a],id,edge[faedge[a]].w-edge[id].w); 94         a=anc[a][0]; 95     } 96 } 97  98 int fx[MAXM],fy[MAXM],visx[MAXM],visy[MAXM],slack[MAXM],lk[MAXM]; 99 100 int Hungary_dfs(int u)101 {102     visx[u]=1;103     for (int i=1;i<=m;i++)104     {105         int wt=fx[u]+fy[i]-val[u][i];106         if (!visy[i] && wt==0)107         {108             visy[i]=1;109             if (lk[i]==-1 || Hungary_dfs(lk[i]))110             {111                 lk[i]=u;112                 return 1;113             }114         }115         else slack[i]=min(slack[i],wt);//注意这里是取较小值不是较大 116     }117     return 0;118 }119 120 void KM()121 {122     memset(lk,-1,sizeof(lk));123     for (int i=1;i<=m;i++)124     {125         fx[i]=-INF;126         fy[i]=0;127         for (int j=1;j<=m;j++) fx[i]=max(fx[i],val[i][j]);128     }129     for (int i=1;i<=m;i++)130     {131         memset(visx,0,sizeof(visx));132         memset(visy,0,sizeof(visy));133         memset(slack,0x3f,sizeof(slack));134         while (!Hungary_dfs(i))135         {136             int delta=INF;137             for (int j=1;j<=m;j++)138                 if (!visy[j]) delta=min(delta,slack[j]);139             for (int j=1;j<=m;j++)140             {141                 if (visx[j])142                 {143                     fx[j]-=delta;144                     visx[j]=0;145                 }146                 if (visy[j])147                 {148                     fy[j]+=delta;149                     visy[j]=0;150                 }151             }152         }153     }154     int ans=0;155     for (int i=1;i<=m;i++) ans+=(fx[i]+fy[i]);156     printf("%d",ans);157 }158 159 /**main part**/160 void init()161 {162     cnt=0;163     scanf("%d%d",&n,&m);164     for (int i=1;i<=m;i++)165     {166         int u,v,w;167         scanf("%d%d%d",&u,&v,&w);168         addedge(u,v,w);169     }170     171     for (int i=1;i<=(n-1);i++)172     {173         int x,y;174         scanf("%d%d",&x,&y);175         for (int j=0;j<E[x].size();j++)176         {177             int id=E[x][j];178             if ((edge[id].u==x && edge[id].v==y)||(edge[id].v==x && edge[id].u==y))179             {180                 edge[id].t=1;181                 break;182             }183         }184     }185     dfs(1,0,0);//建立以1为根的树,方便后续lca操作。注意仅有树边加入,非树边不加入186 }187 188 void solve()189 {190     memset(val,0,sizeof(val));191     getanc();192     for (int i=1;i<=m;i++)193     {194         if (!edge[i].t)195         {196             int lca=LCA(edge[i].u,edge[i].v);197             build(edge[i].u,lca,i);198             build(edge[i].v,lca,i);199         }200     }201     KM();202 }203 204 int main()205 {206     init();207     solve();208     return 0;209 }

 

【KM】BZOJ1937 [Shoi2004]Mst 最小生成树