洛谷——P1194 买礼物

P1194 买礼物

题目描述

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

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

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

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

输入输出格式

输入格式：

第一行两个整数，

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

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

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

输出格式：

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

输入输出样例

输入样例#1：复制

1 1
0

输出样例#1：复制

输入样例#2：复制

输出样例#2：复制

说明

样例解释

先买第

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用

数据规模

对于 $30\%30%的数据,1 le B le 101≤B≤10。$

对于 $100\%100%的数据,1 le B le 500,0 le A,K_{I,J} le 10001≤B≤500,0≤A,KI,J≤1000。$

2018.7.25新添数据一组

其实这题不这样做也可以，跑一边最小生成树，再加上a即可，相当于你先使用a元买一个物品，剩余的

物品可以由这个物品拓展出来，不过有个坑，就是最后一个点的促销的值要比原价要高，取个min即可。

#include<bits/stdc++.h>

#define N 5100
using namespace std;

int a,b,g[5010][5050],minn[N],n;
bool vis[N];
long long ans;
int main()
{
    scanf("%d%d",&a,&b);
    for(int i=1;i<=b;i++)
        for(int j=1;j<=b;j++){
            scanf("%d",&g[i][j]);
            if(!g[i][j]) g[i][j]=0x7fffffff;
        }
    for(int i=0;i<=b;i++)    
        g[b+1][i]=a,g[i][b+1]=0x7fffffff;
    memset(minn,0x7f,sizeof(minn));
    n=b+1;
    int k=0;minn[n]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(minn[j]<minn[k]&&!vis[j]) k=j;
        }
        vis[k]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&minn[j]>g[k][j])
                minn[j]=g[k][j];
        }k=0;
    }
    for(int i=1;i<=n;i++)
        ans+=minn[i];
    printf("%lld
",ans);
    return 0;
}