P1194 买礼物

题目描述
又到了一年一度的明明生日了，明明想要买BB样东西，巧的是，这BB样东西价格都是AA元。

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

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

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

输入格式
第一行两个整数，A,BA,B。

接下来BB行，每行BB个数，第II行第JJ个为K_{I,J}K
I,J
​
。

我们保证K_{I,J}=K_{J,I}K
I,J
​
=K
J,I
​
并且K_{I,I}=0K
I,I
​
=0。

特别的，如果K_{I,J}=0K
I,J
​
=0，那么表示这两样东西之间不会导致优惠。
特别的，如果K_{I,J}=0K
I,J
​
=0，那么表示这两样东西之间不会导致优惠。

输出格式
一个整数，为最小要花的钱数。

输入输出样例
输入 #1复制
1 1
0

输出 #1复制
1
输入 #2复制
3 3
0 2 4
2 0 2
4 2 0
输出 #2复制
7
分析：因为两个商品之间有优惠，可以看成一个图，而两个商品之间的优惠可以看成图的边，所以看成最小生成树，
可以使用kruscal算法求最小生成树。要注意：当两个商品之间的优惠为0时，这个优惠不存在。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node
{
    int x,y,val;
    bool operator <(const node y)const
    {
        return val<y.val;
    }
} a[1000005];
int n,m,b[1000005],f[1005],d[1000005];
int findx(int x)
{
    return f[x]==x? x:f[x]=findx(f[x]);
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,x,sum=0,total=0;
    cin>>m>>n;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            cin>>x;
            if(x==0)
                continue;
            if(i==j)
                continue;
            a[++total].val=x;
            a[total].x=i;
            a[total].y=j;
        }
    }
    sort(a+1,a+total+1);
    for(i=1; i<=n; i++)
    {
        f[i]=i;
    }
    for(i=1; i<=total; i++)
    {

        int r1=findx(a[i].x),r2=findx(a[i].y);//对两个顶点进行查询
        if(r1!=r2)
        {
            f[r1]=r2;
            if(a[i].val>m)
                a[i].val=m;
            sum+=a[i].val;
        }
    }
    cout<<sum+m;
    return 0;
}