首页 > 代码库 > luogu P1194 买礼物

luogu P1194 买礼物

题目描述

又到了一年一度的明明生日了,明明想要买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。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long

using namespace std;
const ll N=500001;
const ll Maxn=9999999;

struct node{
    ll u,v,w;
}E[N];
ll js;
ll f[N];
ll val,muc;
ll answer;

inline ll read()
{
    ll x=0;char c=getchar();
    while(c<0||c>9)c=getchar();
    while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
    return x;
}

bool cmp(node a,node b)
{
    return a.w<b.w;
}

ll getfa(ll x)
{
    return f[x]==x?x:f[x]=getfa(f[x]);
}

int main()
{
    val=read();
    muc=read();
    ll my;
    
    for(int i=1;i<=muc;i++)
        f[i]=i;
        
    for(int i=1;i<=muc;i++)
        for(int j=1;j<=muc;j++)
        {
            my=read();
            if(my)
            {
                E[++js].u=i;
                E[js].v=j;
                E[js].w=my;
            }    
        }
    
    sort(E+1,E+js+1,cmp);
    int tot=0;
    for(int i=1;i<=js;i++)
    {
        ll fu=getfa(E[i].u);
        ll fv=getfa(E[i].v);
        if(fu!=fv)
        {
            f[fu]=fv;
            tot++;
            answer+=E[i].w;
        }
        if(tot==muc-1)
            break;
    }
    
    for(int i=1;i<=muc;i++)
        if(f[i]==i);
            answer+=val;
    
    printf("%lld",answer);
    return 0;
}

 

luogu P1194 买礼物