MST的三种解法
1>prim
2>kruskal
算法步骤
步骤一：T是边的集合，其初始状态为空；
步骤二：从原图剩余边中选取一条最小代价的边；
步骤三：看其是否与当前T中其它边构成环路；
步骤四：如果未构成环路，则加入T中；否则，丢弃该边；
步骤五：是否还有剩余边，如果有则返回步骤二，否则，程序结束。
算法证明（来自网络）
（1）Kruskal算法一定能得到一个生成树；
（2）该生成树具有最小代价。
=》
（1）假设该算法得到的不是生成树，根据树的定义，就有两种情形，第一是得到的图是有环的，第二就是得到的图是不连通的。由于算法要求每次加入边都是无环的，所以第一种情形不存在，下面就只需证明第二种情形不存在即可。
假设得到的图是不连通的，则至少包含两个独立的的边集，假设其中一个为E，则E中边对应的所有点都无法到达其它边集对应的点
（否则，根据算法定义，相应的联系边应被加入树中），而这与原图是连通的产生矛盾，因此，第二种情形也不可能存在。得证。
（2）假设图有n个顶点，则生成树一定具有n-1条边.由于图的生成树个数是有限的，所以至少有一棵树具有最小代价，假设该树为U。
先做出如下假设：
1)得到的树为T。
2)U和T中不同的边的条数为k,其它n-1-k条边相同，这n-1-k条边构成边集E。；
3)在T中而不在U中的边按代价从小到大依次为a1，a2，...，ak。
4)在U中而不在T中的边按代价从小到大依次为x1，x2，...，xk。
现在我们通过把U转换为T（把T的边依次移入U中），来证明U和T具有相同代价。
首先，我们将a1移入U中，由于U本身是一棵树，此时任意加一条边都构成回路，所以a1的加入必然产生一条回路，且这条回路必然包括x1，x2，...，xk中的边。
（否则a1与E中的边构成回路，而E也在T中，这与T中无回路矛盾。）
在这个回路中删除属于x1，x2，...，xk且代价最大边xi构成一个新的生成树V。
假设a1代价小于xi，则V的代价小于U，这与U是最小代价树矛盾，所以a1不可能小于xi。
假设a1大于xi，按照Kruskal算法，首先考虑代价小的边，则执行Kruskal算法时，xi应该是在a1之前考虑，而a1又在a2，...，ak之前考虑，所以考虑xi之前，T中的边只能是E中的边，而xi既然没加入树T，就说明xi必然与E中的某些边构成回路，但xi和E又同时在U中，这与U是生成树矛盾，所以a1也不可能大于xi。
因此，新得到的树V与T具有相同代价。
依次类推，把a1，a2，...，ak的边逐渐加到U中，最终得到的树（T)与U代价相同。
证明结束。
3>破圈 这个容易超时
<1>最小生成树计数
kruskal+并查集
想象：
把图分成两部分，一部分是环，一部分是链
从破圈法反过来：
一个环，假设是1-2-3（-1）
我现在破圈，就是找里面最大的除去，
但是K，就是找前两条小的边
然后链，因为不连通，所以都要加上
那么如果我想在这个过程中加边，
就是一个环中多个边的值一样，选择多样，
然后找个办法，找出一环环，环上环的选择数
据说这是一个定理
1.不同的最小生成树中,每种权值的边出现的个数是确定的。
2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的 。
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int n,m; const int N=103,M=1003,mod=31011; struct node { int u,v,w; bool operator < (const node & o) const { return w<o.w; } } sd[M]; struct nd { int l,r; int tm,val; }dd[M]; int fa[N]; int find(int x) { return !fa[x] ?x : find(fa[x]); }//这道题不能路径压缩，？？？？ int sum,goal,r; void dfs(int nw,int kk) { if(kk==goal) { sum++; return ; } if(nw>=r) return ; else { int fu=find(sd[nw].u ),fv=find(sd[nw].v ); if(fu!=fv) fa[fu]=fv,dfs(nw+1,kk+1),fa[fu]=fa[fv]=0; } dfs(nw+1,kk); } int ans; int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d%d",&sd[i].u ,&sd[i].v ,&sd[i].w ); sort(sd,sd+m); int cnt=1,pos=0; for(int i=0;i<m;i++)//我在这放了一个cnt，然后去掉了不少可能的结果。。。 { if(sd[i].w !=dd[pos].val ) dd[++pos].val =sd[i].w ,dd[pos].l =dd[pos-1].r =i; int fu=find(sd[i].u ),fv=find(sd[i].v ); if(fu^fv) fa[fu]=fv,dd[pos].tm ++,cnt++; }dd[pos].r =m; if(cnt^n) { printf("0 "); return 0; } else ans=1; memset(fa,0,sizeof(fa)); for(int i=1;i<=pos;i++) { if(!dd[i].tm ) continue; //if(dd[i].r -dd[i].l ==dd[i].tm ) continue;//我这里计算，想减掉枝，忘了让fa更新，然后一直wa sum=0,goal=dd[i].tm ,r=dd[i].r ; dfs(dd[i].l ,0); ans=ans*sum%mod; for(int j=dd[i].l ;j<dd[i].r ;j++) { int fu=find(sd[j].u ),fv=find(sd[j].v ); if(fu!=fv) fa[fu]=fv; } } printf("%d",ans); return 0; }
<1.5>新的开始
简单的加超级源点，然后建MST
<2>黑暗城堡
简单最短路+生成树思维+乘法原理
解决了一个新的问题：最短路径生成树
#include<cstdio> #include<cstdlib> #include<queue> #include<cstring> #include<algorithm> using namespace std; int n,m; const int N=1003; int g[N][N],dis[N]; bool in[N]; queue <int> q; struct node { int d,xh; bool operator < (const node & o) const { return d<o.d; } }dd[N]; void SPFA() { memset(g,0x3f,sizeof(g)); memset(dis,0x3f,sizeof(dis)); int u,v,w; while(m--) scanf("%d%d%d",&u,&v,&w),g[u][v]=g[v][u]=w; dis[1]=0,q.push(1); while(!q.empty() ) { int u=q.front() ;q.pop() ; for(int i=2;i<=n;i++) if(dis[i]>dis[u]+g[u][i]) { dis[i]=dis[u]+g[u][i]; if(!in[i]) in[i]=true,q.push(i); } in[u]=false; } } const long long mod=(1<<30)-1 +(1<<30); long long ans=1; int main() { scanf("%d%d",&n,&m); SPFA(); for(int i=1;i<=n;i++) dd[i].d =dis[i],dd[i].xh =i; sort(dd+1,dd+n+1); for(int i=2;i<=n;i++) { int u=dd[i].xh ; long long sum=0; for(int j=1;j<i;j++) { int v=dd[j].xh ; if(dis[u]==dis[v]+g[u][v]) sum++; } if(!sum) { printf("0 "); return 0; } ans=sum%mod*ans%mod; } printf("%lld",ans); return 0; }
我...又因为看错数据范围wa了
<3>北极通讯网络
好神奇的题，
n座村庄，每座村庄的坐标用一对整数 (x,y) 表示。
两种通讯工具：
无限的 无线电收发机，k台 卫星设备。
不同型号的无线电收发机有一个不同的参数 ，两座村庄之间的距离如果不超过 d就可以用该型号的无线电收发机直接通讯， d值越大的型号价格越贵。
拥有卫星设备的两座村庄无论相距多远都可以直接通讯。通讯有传递性。
求d的最小值
神仙思路：将点分为两种，一种普通点，一种神奇点。
神奇点之间的交流不花钱，但与普通点交流要钱，
你看这个神奇点，全部合起来像不像是一个点，
所以这其实是：求k个生成树，
或者换句话说：kruskal的时候，不求完，只做一半的工作
最小生成树的第k大边
#include<cstdio> #include<cstdlib> #include<queue> #include<cmath> using namespace std; int n,k; const int N=503; int pz[N][2]; struct node { int u,v;double w; bool operator < (const node & o) const { return w>o.w; } node(int uu,int vv,double ww) { u=uu,v=vv,w=ww; } node(){} }; priority_queue <node> q; double get_dis(int u,int v) { double a=pz[u][0]-pz[v][0]; double b=pz[u][1]-pz[v][1]; return sqrt(a*a+b*b); } double ans; int fa[N]; int find(int x) { return !fa[x]?x:fa[x]=find(fa[x]); } void kruskal() { if(k>=n) { printf("0.00 "); return ; } int cnt=k; if(!k) cnt++; while(cnt<n) { node t=q.top() ;q.pop() ; int fu=find(t.u ),fv=find(t.v ); if(fu==fv) continue; fa[fu]=fv,cnt++; ans=t.w ; } printf("%.2lf ",ans); } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d%d",&pz[i][0],&pz[i][1]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) q.push(node(i,j,get_dis(i,j))); kruskal(); return 0; }
<4>构造完全图
给你看我傻乎乎的枚举判断+LCA倍增
最后只过了50分，tle掉了
#include<cstdio> #include<cstdlib> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n; const int N=1e5+3; struct node { int v,w; node(int vv,int ww) { v=vv,w=ww; } node(){} }; vector <node> g[N]; int g_sz[N]; bool f[N]; int fa[N][19],d[N][19],dep[N]; void dfs(int nw,int pre) { fa[nw][0]=pre; for(int i=1;i<19 && fa[nw][i-1];i++) fa[nw][i]=fa[fa[nw][i-1]][i-1], d[nw][i]=max(d[nw][i-1],d[fa[nw][i-1]][i-1]); dep[nw]=dep[pre]+1; g_sz[nw]=g[nw].size() ; for(int i=0;i<g_sz[nw];i++) { int v=g[nw][i].v ; if(v!=pre) d[v][0]=g[nw][i].w ,dfs(v,nw); } } int LCA(int u,int v) { int mx=0; if(dep[u]<dep[v]) swap(u,v); int dis=dep[u]-dep[v]; for(int i=18,j=1<<18;j;i--,j>>=1) if(dis&j) { mx=max(mx,d[u][i]); u=fa[u][i]; } if(u==v) return mx; for(int i=18;i>=0;i--) if(fa[u][i]!=fa[v][i]) { mx=max(mx,max(d[u][i],d[v][i])); u=fa[u][i],v=fa[v][i]; } return max(mx,max(d[u][0],d[v][0])); } inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } long long ans; int main() { n=read(); int u,v,w; for(int i=1;i<n;i++) u=read(),v=read(),w=read(),g[u].push_back(node(v,w)),g[v].push_back(node(u,w)),ans+=w; dfs(1,0); for(int i=1;i<=n;i++) { memset(f,false,sizeof(f)); for(int j=0;j<g_sz[i];j++) f[g[i][j].v ]=true; for(int j=1;j<i;j++) if(!f[j]) ans+=LCA(i,j)+1; } printf("%lld ",ans); return 0; } 正解是这样的： 再次从kruskal的过程入手操作，一边连入最优边，一边在自己记录答案的小册子上，加上那些不优的边 对于当前这条边的2个端点u和v，所处的2个连通块U和V之间必然是还未连通的。 加入这条边之后2个才能够连通， 换言之，使得这2个连通块连通的，权值最小的边，就是当前的u和v边。 因此被排除的边就是Sum(U)*Sum(V) -1（U中取一个点，V中取一个点，然后排除u,v这条边），而这条边的权值就是w(u,v) + 1。 #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int n; const int N=1e5+3; struct node { int u,v,w; bool operator < (const node & o) const { return w<o.w; } }g[N]; int fa[N],cnt[N]; int find(int x) {return !fa[x]?x:fa[x]=find(fa[x]);} long long ans=0; int main() { scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d%d%d",&g[i].u ,&g[i].v ,&g[i].w ); sort(g+1,g+n); for(int i=1;i<=n;i++) cnt[i]=1; for(int i=1;i<n;i++) { int fu=find(g[i].u ),fv=find(g[i].v ); ans+=1LL*cnt[fu]*cnt[fv]*(g[i].w +1); fa[fu]=fv,cnt[fv]+=cnt[fu]; } printf("%lld ",ans-n+1); return 0; }
然后正解：
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; int n; const int N=1e5+3; struct node { int u,v,w; bool operator < (const node & o) const { return w<o.w; } }g[N]; int fa[N],cnt[N]; int find(int x) {return !fa[x]?x:fa[x]=find(fa[x]);} long long ans=0; int main() { scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d%d%d",&g[i].u ,&g[i].v ,&g[i].w ); sort(g+1,g+n); for(int i=1;i<=n;i++) cnt[i]=1; for(int i=1;i<n;i++) { int fu=find(g[i].u ),fv=find(g[i].v ); ans+=1LL*cnt[fu]*cnt[fv]*(g[i].w +1); fa[fu]=fv,cnt[fv]+=cnt[fu]; } printf("%lld ",ans-n+1); return 0; }
<5>tree
求恰好nd条白边时的最小生成树
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } int n,m,nd; const int N=5e4+3,M=1e5+3; int uu[M],vv[M],ww[M],cc[M]; struct node { int u,v,w;bool c; bool operator < (const node & o) const { return w==o.w ?c<o.c :w<o.w; }//我现在还是很奇怪，为什么这个找的时候，用的是int不是double类 }g[M]; int fa[N],ans=0;; int find(int x) { return !fa[x] ?x :fa[x]=find(fa[x]); } int kruskal(int add) { for(int i=0;i<m;i++) { g[i].u =uu[i],g[i].v =vv[i],g[i].w =ww[i],g[i].c =cc[i]; if(!g[i].c ) g[i].w +=add; }sort(g,g+m); ans=0; int cnt=1,sum=0; memset(fa,0,sizeof(fa)); for(int i=0;cnt<n;i++) { int fu=find(g[i].u ),fv=find(g[i].v ); if(fu==fv) continue; fa[fu]=fv,cnt++; ans+=g[i].w ; if(!g[i].c ) sum++; } if(sum==nd) { printf("%d ",ans-nd*add); exit(0); } else return sum; } int t_ans; int main() { n=read(),m=read(),nd=read(); for(int i=0;i<m;i++) uu[i]=read(),vv[i]=read(),ww[i]=read(),cc[i]=read(),uu[i]++,vv[i]++; //两种题型：一种求l(恰好成立的那个变量)，一种求ans(恰好成立后的结果) //两种写法，1)l<r,r=mid 2)l<=r,r=mid-1 int l=-103,r=103; while(l<=r) { int mid=(l+r)>>1; if(kruskal(mid)>nd) l=mid+1,t_ans=ans-nd*mid;//这里防止因为边的排列问题，导致在一片等长的边中，先选了白边 else r=mid-1; } printf("%d ",t_ans); return 0; }