题目描述
又到了一年一度的明明生日了,明明想要买B样东西,巧的是,这BB样东西价格都是A元。
但是,商店老板说最近有促销活动,也就是:
如果你买了第II样东西,再买第JJ样,那么就可以只花K_{I,J}K ,J 元,更巧的是,K_{I,J}K I,J 竟然等于K_{J,I}K J,I
。
现在明明想知道,他最少要花多少钱。
输出格式
一个整数,为最小要花的钱数。
题解
考虑加一个超级点0,然后建树,边权为连到的下一个点的点权,然后跑kruskal即可
#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 2000000000
using namespace std;
const int M=200004;
const int N=5005;
int a,b,tot;
int fa[M];
struct NODE{
int x,y,z;
bool operator <(const NODE &a){
return this->z < a.z;
}
}bian[M*2];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int find(int x){
if(fa[x]==x) return x;
else return find(fa[x]);
}
inline void kruskal(){
int ans=0,cnt=0;
sort(bian+1,bian+tot+1);
for(int i=1;i<=tot;i++){
if(fa[find(bian[i].x)]!=fa[find(bian[i].y)]){
fa[find(bian[i].x)]=fa[find(bian[i].y)];
cnt++;
ans=ans+bian[i].z;
}
if(cnt==b){
printf("%lld",ans);
return ;
}
}
}
int main(){
a=read();b=read();
for(int i=1;i<=b;i++) fa[i]=i;
for(int i=1;i<=b;i++){
bian[i].x=0;
bian[i].y=i;
bian[i].z=a;
}
tot=b;
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int k=read();
if(i<j&&k!=0) {
tot++;
bian[tot].x=i;
bian[tot].y=j;
bian[tot].z=k;
}
}
}
kruskal();
return 0;
}