洛谷P1194 买礼物（Prim）

题目描述

又到了一年一度的明明生日了，明明想要买

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

如果你买了第 $III样东西，再买第JJJ样，那么就可以只花KI,JK_{I,J}KI,J元，更巧的是，KI,JK_{I,J}KI,J竟然等于KJ,IK_{J,I}KJ,I。$

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

输入格式

第一行两个整数，

接下来 $BBB行，每行BBB个数，第III行第JJJ个为KI,JK_{I,J}KI,J。$

我们保证 $KI,J=KJ,IK_{I,J}=K_{J,I}KI,J=KJ,I并且KI,I=0K_{I,I}=0KI,I=0。$

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

输出格式

一个整数，为最小要花的钱数。

输入输出样例

输入 #1

1 1
0

输出 #1

输入 #2

输出 #2

7
只要想得到的话其实很简单。有优惠关系的两个点建边，求最小生成树后再加上一个a即可，看到数据范围跑Prim就行。
有几个重要的地方：
1.Kij可能大于a，因此建边要取min
2.要对Prim的模板稍微修改一下，忽略掉Kij=0的情况（没有优惠/i=j），因为没有优惠时Kij=0而非INF，不太符合一般认知2333

#include <bits/stdc++.h>
using namespace std;
int a,b,mmap[1005][1005],d[1005],ans=0;
bool v[1005];
void prim()
{
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[1]=0;
    int i,j;
    for(i=1;i<b;i++)
    {
        int x=0;
        for(j=1;j<=b;j++)
        {
            if(!v[j] &&  (x==0 || (d[j] && d[j] < d[x]) ) ) x = j;
        }
        v[x]=1;
        int y;
        for(y=1;y<=b;y++)
        {
            if(mmap[x][y]==0)continue;
            if(!v[y])d[y]=min(d[y],mmap[x][y]);
        }
    }
}
int main()
{
    cin>>a>>b;
    int i,j;
    for(i=1;i<=b;i++)
    {
        for(j=1;j<=b;j++)
        {
            scanf("%d",&mmap[i][j]);
            mmap[i][j]=min(mmap[i][j],a);
        }
    }
    prim();
    for(i=2;i<=b;i++)
    {
        ans+=d[i];
    }
    cout<<ans+a;
    return 0;
}