MST – GNAQ 的心语屋

题面不放

这是道好题一开始还以为是 $\rm{Matrix Tree}$ 定理，后来发现不是QAQ

其实暴搜可过

先一遍Kruskal，顺便把权值相等的边们分到一个块里面，随便怎么实现都行记录一下每个块有多少边在MST中出现过

然后重置一下并查集，枚举块，每个块跑DFS选哪些边（注意连通性，如果这条边加入成环就不能选，这很显然qwq），答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等，证明？

开始时，每个点单独构成一个集合。

首先只考虑权值最小的边，将它们全部添加进图中，并去掉环，由于是全部尝试添加，那么只要是用这种权值的边能够连通的点，最终就一定能在一个集合中。

那么不管添加的是哪些边，最终形成的集合数都是一定的，且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢？我们将之间得到的集合每个集合都缩为一个点，那么权值第二小的边就变成了当前权值最小的边，也有上述的结论。

因此每个阶段，添加的边数都是相同的。我们以权值划分阶段，那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

哦，还有，这段代码BZOJ编译会CE，不知道为什么她就是不支持C++11 [摊手]

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#define mo 31011
#define ll long long
using namespace std;

struct ed { int fr,to,w; }edge[100010]={0};
struct gr { int w,cnt; } gro[100010]={0};
struct blocks { int lx,rx,num; } blk[100010]={0};
int nodenum,edgenum,mstnum=0,blkm=0,nblk,ans=1,ansx;
int fa[100010]={0};

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int findx(int e) { if (fa[e]!=e) return findx(fa[e]); return fa[e]; }

inline void dfs(int npos,int used)
{
	if (npos==blk[nblk].rx+1)
	{
		if (used==blk[nblk].num) ansx++;
		return;
	}
	int u=findx(edge[npos].fr),v=findx(edge[npos].to);
	if (u!=v)
	{
		fa[u]=v;
		dfs(npos+1,used+1);
		fa[u]=u; fa[v]=v;
	}
	dfs(npos+1,used);
}

int main()
{
	readx(nodenum); readx(edgenum);
	for (int i=1;i&lt;=edgenum;i++) { readx(edge[i].fr); readx(edge[i].to); readx(edge[i].w); }
	for (int i=1;i&lt;=nodenum;i++) fa[i]=i;
	sort(edge+1,edge+edgenum+1,[](ed a,ed b){return a.w&lt;b.w;});
	
	for (int i=1;i&lt;=edgenum;i++)
	{
		if (edge[i].w!=edge[i-1].w) { blk[blkm].rx=i-1; blk[++blkm].lx=i; }
		if (findx(edge[i].fr)!=findx(edge[i].to))
		{
			fa[findx(edge[i].fr)]=findx(edge[i].to); mstnum++;
			blk[blkm].num++;
		}
	}
	if (mstnum&lt;nodenum-1) { printf("0\n"); return 0; }
	
	blk[blkm].rx=edgenum;
	for (int i=1;i&lt;=nodenum;i++) fa[i]=i;
	
	for (int i=1;i&lt;=blkm;i++)
	{
		nblk=i; ansx=0;
		dfs(blk[i].lx,0); ans=(ans*ansx)%mo;
		for (int j=blk[i].lx;j&lt;=blk[i].rx;j++) if (findx(edge[j].fr)!=findx(edge[j].to)) 
			fa[findx(edge[j].fr)]=findx(edge[j].to);
	}
	printf("%d\n",ans);
	return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

#define mo 31011

#define ll long long

using namespace std;

struct ed { int fr,to,w; }edge[100010]={0};

struct gr { int w,cnt; } gro[100010]={0};

struct blocks { int lx,rx,num; } blk[100010]={0};

int nodenum,edgenum,mstnum=0,blkm=0,nblk,ans=1,ansx;

int fa[100010]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline int findx(int e) { if (fa[e]!=e) return findx(fa[e]); return fa[e]; }

inline void dfs(int npos,int used)

{

if (npos==blk[nblk].rx+1)

{

if (used==blk[nblk].num) ansx++;

return;

}

int u=findx(edge[npos].fr),v=findx(edge[npos].to);

if (u!=v)

{

fa[u]=v;

dfs(npos+1,used+1);

fa[u]=u; fa[v]=v;

}

dfs(npos+1,used);

}

int main()

{

readx(nodenum); readx(edgenum);

for (int i=1;i<=edgenum;i++) { readx(edge[i].fr); readx(edge[i].to); readx(edge[i].w); }

for (int i=1;i<=nodenum;i++) fa[i]=i;

sort(edge+1,edge+edgenum+1,[](ed a,ed b){return a.w<b.w;});

for (int i=1;i<=edgenum;i++)

{

if (edge[i].w!=edge[i-1].w) { blk[blkm].rx=i-1; blk[++blkm].lx=i; }

if (findx(edge[i].fr)!=findx(edge[i].to))

{

fa[findx(edge[i].fr)]=findx(edge[i].to); mstnum++;

blk[blkm].num++;

}

if (mstnum<nodenum-1) { printf("0\n"); return 0; }

blk[blkm].rx=edgenum;

for (int i=1;i<=nodenum;i++) fa[i]=i;

for (int i=1;i<=blkm;i++)

{

nblk=i; ansx=0;

dfs(blk[i].lx,0); ans=(ans*ansx)%mo;

for (int j=blk[i].lx;j<=blk[i].rx;j++) if (findx(edge[j].fr)!=findx(edge[j].to))

fa[findx(edge[j].fr)]=findx(edge[j].to);

}

printf("%d\n",ans);

return 0;

}

城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2．在满足要求1的情况下，改造的道路尽量少。

3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。

任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。

大意就是用最小的代价把N个点的图变成连通图（要求1、2）

那么，N个点的联通图最小需要N-1条边，这显然是一个MST的题。

根据要求3，显然使用并查集维护的Kruskal更优。

那这就是个MST的裸题了……QnQ这么简单为什么还要发题解

关于s，可以知道它肯定是N-1 （N是点数）

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;cmath&gt;
#include&lt;string&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
using namespace std;

struct ed
{
    int from,to,w;
}edge[50010]={0};
int edgenum=0,nodenum=0;
int fatherx[1010]={0},mst=0,c1=0;

bool cmp(ed a,ed b)
{
    return a.w&lt;b.w;
}

int findx(int e1)
{
    if (fatherx[e1]!=e1) fatherx[e1]=findx(fatherx[e1]);
    return fatherx[e1];
}

void mergex(int e1,int e2)
{
    fatherx[findx(e2)]=findx(e1);
}

int main()
{
    scanf("%d%d",&amp;nodenum,&amp;edgenum);
    for (int i=1;i&lt;=edgenum;i++)
    {
        scanf("%d%d%d",&amp;edge[i].from,&amp;edge[i].to,&amp;edge[i].w);
    }
    
    sort(edge+1,edge+1+edgenum,cmp);
    for (int i=1;i&lt;=nodenum;i++) fatherx[i]=i;
    
    for (int i=1;i&lt;=edgenum;i++)
    {
        if (findx(edge[i].from)!=findx(edge[i].to))
        {
            mergex(edge[i].from,edge[i].to);
            mst=edge[i].w;
            c1++;
        }
        if (c1==nodenum-1) break;
    }
    printf("%d %d\n",nodenum-1,mst);
    return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<string>

#include<algorithm>

#include<iterator>

using namespace std;

struct ed

{

int from,to,w;

}edge[50010]={0};

int edgenum=0,nodenum=0;

int fatherx[1010]={0},mst=0,c1=0;

bool cmp(ed a,ed b)

{

return a.w<b.w;

}

int findx(int e1)

{

if (fatherx[e1]!=e1) fatherx[e1]=findx(fatherx[e1]);

return fatherx[e1];

}

void mergex(int e1,int e2)

{

fatherx[findx(e2)]=findx(e1);

}

int main()

{

scanf("%d%d",&nodenum,&edgenum);

for (int i=1;i<=edgenum;i++)

{

scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].w);

}

sort(edge+1,edge+1+edgenum,cmp);

for (int i=1;i<=nodenum;i++) fatherx[i]=i;

for (int i=1;i<=edgenum;i++)

{

if (findx(edge[i].from)!=findx(edge[i].to))

{

mergex(edge[i].from,edge[i].to);

mst=edge[i].w;

c1++;

}

if (c1==nodenum-1) break;

}

printf("%d %d\n",nodenum-1,mst);

return 0;

}

标签： MST

BZOJ1016 | JSOI2008 最小生成树计数

[SCOI2005]繁忙的都市