题目描述
又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这B样东西价格都是A元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第I样东西，再买第J样，那么就可以只花K[I,J]元，更巧的是，K[I,J]竟然等于K[J,I]。
现在明明想知道，他最少要花多少钱。
输入输出格式
输入格式：
第一行两个整数，A,B。
接下来B行，每行B个数，第I行第J个为K[I,J]。
我们保证K[I,J]=K[J,I]并且K[I,I]=0。
特别的，如果K[I,J]=0，那么表示这两样东西之间不会导致优惠。
输出格式：
仅一行一个整数，为最小要花的钱数。
输入输出样例
输入样例#1：
【样例输入1】
1 1
0
【样例输入2】
3 3
0 2 4
2 0 2
4 2 0
输出样例#1：
【样例输出1】
1
【样例输出2】
7
说明
样例解释2
先买第2样东西，花费3元，接下来因为优惠，买1，3样都只要2元，共7元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用4元买剩下那件，而选择用2元。）
数据规模
对于30%的数据,1<=B<=10。
对于100%的数据,1<=B<=500，0<=A,K[I,J]<=1000。
最小生成树，最后加上没father合并的
#include<cstdio>
#include<algorithm>
using namespace std; #define N 500006
int A,B;
int n;
struct node{
int u,v,w;
}edge[N];
int read(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}return x*f;
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
int father[N]; int find(int x)
{
if(x!=father[x])father[x]=find(father[x]);
return father[x];
}
int cnt,ans;
int num;
inline void kruskal()
{
sort(edge+,edge+num+,cmp);
for(int i = ;i <= num;i++)
{
int fx = find(edge[i].u),fy = find(edge[i].v);
if(fx != fy)
{
cnt++;
ans += edge[i].w;
father[fy] = fx;
}
}
}
int main()
{ A=read();B=read();
for (int i = ;i <= B;i ++)father[i] = i;
for (int i = ;i <= B;i ++)
for (int j = ;j <= B;j ++)
{
int a;
a=read();
if(i<j&&a!=) edge[++num].u=i,edge[num].v=j,edge[num].w=a; }
kruskal(); for (int i = ;i <= B;i ++)
if (father[i] == i)ans += A;
printf("%d",ans);
return ;
}