自动搬运

查看原文

来自洛谷，原作者为

	ShuYuMo AFO on 2021.7.28 早凉了

搬运于2025-08-24 21:44:39，当前版本为作者最后更新于2019-08-04 09:37:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

如果没有边权相同的边，那么其实时不存在多种最小生成树的方案的。

题目中同一边权的个数不超过三个

按照Kruskal的建树流程进行模拟。

边权排完序后，边权相同的会聚到一起，然后在从小到大枚举的时候分类讨论即可。

流程

首先找到边权相同到的几条边。

这是我们需要在这些边中选出有用边。

所谓有用边就是加入其中一条边，不会产生环。因为之前已经加入的边是不能再反悔的，所以如果当前等待加入的边与之前的边存在矛盾的话，当前边一定是无用的。 如下图，下图的橙色边就是无用边：

然后我们考虑哪些情况会使最小生成树方案增加：

• 如过当前权值有两条边相同： 就有这两种情况：

  • 
  • 对于第一种情况，这两条边只能同时加入其中任意一条，这样就有两种建树方案。 对于第二种情况，这两条边没有选择余地，必须都加入。

• 如过当前权值有三条边相同： 以下三种情况能产生多种建树方案：

  • 
  • 
  • 这三种情况分别产生$3$（选其中一条不加入），$2$（选重复的两条中的一条），$3$（选三条中的任意一条）种生成树方案。

代码

使用set帮助区分三条边权相同时，第一种情况和第二种情况。

/*!
 * FileName: luogu-3037.cpp
 * This Problem is on luogu. The ID of the problem is 3037. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-08-03 22:47:58 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int _M = 1e5 + 100;
const int _N = 4e4 + 100;
const int MOD = 1000000007;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
struct edges{
	int u;
	int v;
	int w;
	bool operator < (const edges & A) const {
		return w < A.w;
	}
}E[_M];
int n, m;
//Kruskal 所用的并查集   Start
int f[_N];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
void initForSet()
{
	for(register int i = 1;i <= n;i++)
		f[i] = i;
}
void marge(int x, int y)
{
	x = find(x);
	y = find(y);
	if(x == y) return;
	f[x] = y;
}
bool ask(int x, int y)
{
	return find(x) == find(y);
}
//Kruskal 所用的并查集   End
int nxtIt(int now)//往下找最后一个边权相同的位置
{
	for(register int i = now;i <= m;i++)
		if(E[now].w != E[i].w)
			return i - 1;
	return m;
}
set <pair<int , int >  >  S;//
int main()
{
	n = read(), m = read();
	for(register int i = 1;i <= m;i++)
	{
		E[i].u = read();
		E[i].v = read();
		E[i].w = read(); 
	}
	initForSet();
	sort(E + 1, E + 1 + m);
	int ans1 = 0;
	int ans2 = 1;
	int nxt;
	for(register int i = 1;i <= m;)
	{
		S.clear();
		nxt = nxtIt(i);
		int totEdge = 0;
		for(register int j = i;j <= nxt;j++)
			if(!ask(E[j].u, E[j].v))
			{
				totEdge ++;
				int k1 = min(find(E[j].u), find(E[j].v));
				int k2 = max(find(E[j].u), find(E[j].v));
				S.insert(make_pair(k1, k2));
			}
		int totAdd = 0;
		for(register int j = i;j <= nxt;j++)
		{
			if(!ask(E[j].u, E[j].v))
			{
				marge(E[j].u, E[j].v);
				totAdd ++;
				ans1 = (ans1 + E[j].w) % MOD;
			}
		}
		if(totAdd == 1)
			ans2 = ans2 * 1LL * totEdge % MOD;//分别是两条边权相同时的第一种情况    和    三条边权相同时的第三种情况。
		if(totAdd == 2 && totEdge == 3)
		{
			if(S.size() == 3) ans2 = ans2 * 3LL % MOD;//三条边权相同时的第一种情况
			if(S.size() == 2) ans2 = ans2 * 2LL % MOD; //三条边权相同时的第二种情况
		}
		i = nxt + 1;
	}
	printf("%d %d\n", ans1 % MOD, ans2 % MOD);
    return 0;
}