宜宾网站建设工作室,网站工作状态建设,谷歌seo专员,大连装修公司前十名《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
简…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
简化农场” 链接
http://oj.ecustacm.cn/problem.php?id1879 题目描述
【题目描述】 约翰的农场可以看做一个图农田代表图中顶点田间小路代表图中的边每条边有一定的长度。 约翰发现自己的农场中最多有三条小路有着相同的长度。 约翰想删除一些小路使得农场成为一棵树使得两块农田间只有一条路径。 约翰想把农场设计成最小生成树也就是农场道路的总长度最短。 请帮助约翰找出最小生成树的总长度同时请计算出总共有多少种最小生成树。 【输入格式】 输入第一行为两个正整数 N 和 M 表示点数和边数(1 N 40,000; 1 M 100,000)。 接下来 M 行每行三个整数 ai, bi, ci表示点 ai 和 bi 之间存在长度为 ci 的无向边。(1 ai, bi N; 1 ci 1,000,000) 【输出格式】 输出一行包含两个整数分别表示最小生成树的长度和最小生成树的数目。 数目对 1,000,000,007 求余. 【输入样例】
4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2【输出样例】
4 3题解 有两种最小生成树MST算法kruskal、prim。Kruskal的思路是对边贪心“最短的边一定在MST上”prim的思路是对点贪心“最近的邻居点一定在MST上”。 本题描述中比较特殊的地方是1最多有三条小路边有相同长度2计算总共有多少种最小生成树。着重点在边上所以用kruskal算法。 kruskal算法执行步骤是1对边排序2从最短的边开始从小到大依次把边加入到MST中3加边的过程中用并查集判断是否产生圈如果形成了圈就丢弃这个边4所有边处理完后结束或者加边的数量等于n-1时结束。 如果所有的边长都不同那么只有一种最小生成树。题目指出“最多有三条边的长度相同”从样例可知有等长的两条边也有等长的三条边。对边排序时这些相等的边会挨在一起。 处理等长边设cnt是合法所谓合法是指这个边加入到MST不会产生圈的边的数量num是这几个等长边有几个能同时加入到MST。sum是最小生成树的数目。 1有两条等长边。 若cnt1只有一条边是合法的也就是说这条边别无选择那么sum不变。 若cnt2有2条边合法继续讨论 1num1即这两条等长边只有一条能加入到MST中。那么sum sumcnt即sumsum2。以下图为例s1和s2是两棵已经加入到MST的子树它们内部没有圈。现在加两条等长边(x1,y1)、(x2,y2)它们单独加入MST都是合法的但是同时加入就会形成圈。 2num2即这两条等长边都应该加入到MST中。那么sum不变即sumsum1。以下图为例。 2有三个等长边。 若cnt1只有一条边合法sum不变。 若cnt2有两条边合法和1有两条等长边且cnt2的情况一样。 若cnt3有三条边合法那么 1num 1只有一条边能加入到MST中sum sumcntsum3。以下图为例三条边任选一条有3种情况。 2num 2有两条边能加入到MST中且其中一条边必须加sum sum2。以下图为例三条边任选两条有2种情况。 3num 2有两条边能加入到MST中且是任意两条sum sum*3。以下图为例三条边任选两条有3种情况。 3num 3三条边都应该加入到MST中sum不变。
【重点】 kruskal 。
C代码
#includebits/stdc.h
using namespace std;
#define int long long
const int N 1e610;
const int mod 1e97;
struct Node{int x,y,val;}e[N1];
bool cmp(Node a,Node b){return a.valb.val;}//按边权排序
int n,m;
int s[N]; //并查集
int ans0,sum1; //ans: MST的总长度 sum最小生成树的数目
int find_set(int x){ //查询并查集返回x的根if(x ! s[x]) s[x] find_set(s[x]); //路径压缩return s[x];
}
void kruscal(){for(int i1;in;i) s[i] i; //并查集初始化sort(e1,em1,cmp); //边升序排序for(int i1;im;){ //遍历所有边每次处理其中的等长边int cnt 0; //这次的等长边中有几个可以加入MSTsetpairint,int st; //set用于存储并去重int j; //第i~j个边等长for(ji;ji2 e[i].vale[j].val;j){ //枚举等长边最多3个相同。更新jint s1 find_set(e[j].x); //边的一个端点属于哪个集int s2 find_set(e[j].y); //边的另一个端点属于哪个集if(s1 s2) swap(s1,s2);if(s1 ! s2){ //两个集不等这个边可以加入到MST中cnt ; //cnt: 允许加入MST的边的数量st.insert(make_pair(s1,s2)); //这个边的两端点所属的集存到st中}} //第i~j个边是等长的int num 0;for(;ij;i){ //开始时第i~j个边是等长的。ij时退出int s1 find_set(e[i].x);int s2 find_set(e[i].y);if(s1 ! s2){ //不属于一个集可以加入到树里s[s2] s1; //并查集合并num; //这几个等长边有num个可以同时加入树}}ans e[i-1].val*num; //这几个等长边最后有num个可以加入到MST计算MST总长if(num 1) sum sum*cnt%mod; //只有一条边能加入树直接乘以cntif(cnt 3 num2 st.size() 2) sum 2*sum%mod;if(cnt 3 num2 st.size() 3) sum 3*sum%mod;//其他情况方案数都不变}
}
signed main(){scanf(%lld%lld,n,m); //读点边for(int i1;im;i) //存边用最简单的“边集数组”存边scanf(%lld%lld%lld,e[i].x,e[i].y,e[i].val);kruscal(); //最小生成树printf(%lld %lld\n,ans,sum);
}Java代码 Python代码
