P1194 買禮物

題目描述

又到了一年一度的明明生日了，明明想要買B樣?xùn)|西，巧的是，這B樣?xùn)|西價(jià)格都是A元。

但是，商店老板說(shuō)最近有促銷活動(dòng)，也就是：

如果你買了第I樣?xùn)|西，再買第J樣，那么就可以只花K[I,J]元，更巧的是，K[I,J]竟然等于K[J,I]。

現(xiàn)在明明想知道，他最少要花多少錢。

輸入輸出格式

輸入格式：

?

第一行兩個(gè)整數(shù)，A,B。

接下來(lái)B行，每行B個(gè)數(shù)，第I行第J個(gè)為K[I,J]。

我們保證K[I,J]=K[J,I]并且K[I,I]=0。

特別的，如果K[I,J]=0，那么表示這兩樣?xùn)|西之間不會(huì)導(dǎo)致優(yōu)惠。

?

輸出格式：

?

僅一行一個(gè)整數(shù)，為最小要花的錢數(shù)。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 【樣例輸入1】 1 1 0 【樣例輸入2】 3 3 0 2 4 2 0 2 4 2 0 輸出樣例#1：?復(fù)制 【樣例輸出1】 1 【樣例輸出2】 7

說(shuō)明

樣例解釋2

先買第2樣?xùn)|西，花費(fèi)3元，接下來(lái)因?yàn)閮?yōu)惠，買1，3樣都只要2元，共7元。

（同時(shí)滿足多個(gè)“優(yōu)惠”的時(shí)候，聰明的明明當(dāng)然不會(huì)選擇用4元買剩下那件，而選擇用2元。）

數(shù)據(jù)規(guī)模

對(duì)于30%的數(shù)據(jù),1<=B<=10。

對(duì)于100%的數(shù)據(jù),1<=B<=500，0<=A,K[I,J]<=1000。

?

裸的最小生成樹

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 500100 using namespace std; int n,m,x,y,z,fx,fy,tot,sum,ans,fa[N]; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } struct Node {int x,y,z; }node[N]; int cmp(Node a,Node b) {return a.z<b.z; } int find(int x) {if(fa[x]==x) return x;fa[x]=find(fa[x]);return fa[x]; } int main() {m=read(),n=read();for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){z=read();if(z!=0){++tot;node[tot].x=i;node[tot].y=j;node[tot].z=z;}}sort(node+1,node+1+tot,cmp);for(int i=1;i<=tot;i++){x=node[i].x,y=node[i].y;fx=find(x),fy=find(y);if(fx==fy) continue;else fa[fy]=fx;ans+=node[i].z;sum++;if(sum==n-1) break; }for(int i=1;i<=n;i++) if(fa[i]==i) ans+=m;printf("%d",ans);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/z360/p/8213415.html

總結(jié)

以上是生活随笔為你收集整理的洛谷——P1194 买礼物的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。