P1194 买礼物
网页链接
P1194 买礼物
题目描述
又到了一年一度的明明生日了，明明想要买B BB样东西，巧的是，这B BB样东西价格都是A AA元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第I II样东西，再买第J JJ样，那么就可以只花K I , J K_{I,J}KI,J元，更巧的是，K I , J K_{I,J}KI,J竟然等于K J , I K_{J,I}KJ,I。
现在明明想知道，他最少要花多少钱。
输入格式
第一行两个整数，A , B A,BA,B。
接下来B BB行，每行B BB个数，第I II行第J JJ个为K I , J K_{I,J}KI,J。
我们保证K I , J = K J , I K_{I,J}=K_{J,I}KI,J=KJ,I并且K I , I = 0 K_{I,I}=0KI,I=0。
特别的，如果K I , J = 0 K_{I,J}=0KI,J=0，那么表示这两样东西之间不会导致优惠。
注意K I , J K_{I,J}KI,J可能大于A AA。
输出格式
一个整数，为最小要花的钱数。
输入输出样例 #1
输入 #1
1 1 0输出 #1
1输入输出样例 #2
输入 #2
3 3 0 2 4 2 0 2 4 2 0输出 #2
7说明/提示
样例解释2 22。
先买第2 22样东西，花费3 33元，接下来因为优惠，买1 , 3 1,31,3样都只要2 22元，共7 77元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用4 44元买剩下那件，而选择用2 22元。）
数据规模
对于30 % 30\%30%的数据，1 ≤ B ≤ 10 1\le B\le 101≤B≤10。
对于100 % 100\%100%的数据，1 ≤ B ≤ 500 , 0 ≤ A , K I , J ≤ 1000 1\le B\le500,0\le A,K_{I,J}\le10001≤B≤500,0≤A,KI,J≤1000。
2018.7.25新添数据一组
解题思路
本题核心是最小生成树建模 + Kruskal算法，将礼物购买的优惠问题转化为图论最优解问题。把每件礼物看作一个节点，新增虚拟节点0，虚拟节点与每个礼物节点连边，边权为礼物原价A AA（代表单独购买）；将礼物间的有效优惠（K I , J > 0 K_{I,J}>0KI,J>0）作为无向边，边权为优惠价格。构建完整图后，使用Kruskal算法结合并查集求解最小生成树，生成树的总权值就是购买所有礼物的最小花费。最小生成树能保证以最低总成本连通所有节点，完美对应最优购买策略，算法适配B ≤ 500 B≤500B≤500的数据规模，高效稳定。
总结
核心逻辑：将购买优惠建模为无向图，通过最小生成树求解最低总成本。
关键操作：虚拟节点建边、优惠边筛选、K r u s k a l KruskalKruskal算法+并查集实现最小生成树。
效率保障：排序+并查集路径压缩，计算高效，完全满足题目数据约束。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;structE{intu,v,w;}e[250008];intf[10010],n,m,c,fl,x,y,res;intfd(intx){returnf[x]==x?x:f[x]=fd(f[x]);}boolcmp(E a,E b){returna.w<b.w;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(inti=0;i<=m;++i)f[i]=i;c=0;for(inti=1;i<=m;++i){e[++c]={0,i,n};}for(inti=1;i<=m;++i){for(intj=1;j<=m;++j){cin>>fl;if(fl){e[++c]={i,j,fl};}}}sort(e+1,e+c+1,cmp);res=0;for(inti=1;i<=c;++i){x=fd(e[i].u);y=fd(e[i].v);if(x==y)continue;f[x]=y;res+=e[i].w;}cout<<res<<'\n';return0;}
