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

luogu P1194 买礼物

2024-10-08 19:26:02   217人阅读

题目描述

又到了一年一度的明明生日了，明明想要买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 10【样例输入2】3 30 2 42 0 24 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 500006int A,B;int n;struct node{    int u,v,w;}edge[N];int read(){    int x=0,f=1;char c=getchar();    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;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+1,edge+num+1,cmp);    for(int i = 1;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 = 1;i <= B;i ++)father[i] = i;    for (int i = 1;i <= B;i ++)        for (int j = 1;j <= B;j ++)            {                int a;                a=read();                if(i<j&&a!=0) edge[++num].u=i,edge[num].v=j,edge[num].w=a;            }    kruskal();        for (int i = 1;i <= B;i ++)    if (father[i] == i)ans += A;    printf("%d",ans);    return 0;}

 

luogu P1194 买礼物


联系
我们