题目描述

又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这B样东西价格都是A元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第I样东西，再买第J样，那么就可以只花K I,J元，更巧的是，K I,J竟然等于K J,I。

现在明明想知道，他最少要花多少钱。

原题链接

Solve

用Kruskal建立最小生成树（MST）。

1.将每件物品视作一个节点，物品之间的优惠或费用为边的权值。

2 . 设置一个序号为零的节点（精髓所在） ， 此点直接连接的节点即为通过花费a元直接购买的物品。

3.每一样物品都可通过直接花费a元来购买，所以从节点零向每一个节点连接一条权值为a的边。

4.正常建边，正常Kruskal

Tips

如果每个优惠都太实惠太小了，会导致没有物品通过直接购买的方式取得么？

不会的，Kruskal是不会放过一条边的，一定会将节点零加入的。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;  //标准开头
const int N=1000;
int a,b;
struct note{
	int u,r,w;
}d[N*N];  //每条边的信息，u,r——端点，w——权值
int f[N];  //f[i]表示节点i的父节点
int num,cnt,ans;  //cnt——边数，ans——答案
int e,r;
bool cmp(const note &x,const note &y){  //排序
	return x.w<y.w;
}
int find(int s){
	if(s!=f[s]) f[s]=find(f[s]);
	return f[s];
}
int main()
{
	cin>>a>>b;
	for(int i=0;i<=b;i++) f[i]=i;
	for(int i=1;i<=b;i++){
		d[++cnt].u=0;
		d[cnt].r=i;
		d[cnt].w=a;
	}
	for(int i=1;i<=b;i++){
		for(int j=1;j<=b;j++){
			cin>>num;
			if(num!=0){
				d[++cnt].u=i;
				d[cnt].r=j;
				d[cnt].w=num;
			}
		}
	}
	sort(d+1,d+cnt+1,cmp);
	for(int i=1;i<=cnt;i++){
		e=find(d[i].u);
		r=find(d[i].r);
		if(e!=r){
			ans+=d[i].w;
			f[r]=e;
		}
	}
	cout<<ans;
	return 0;
}