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

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

样例解释 $2$ 。

先买第 $2$ 样东西，花费 $3$ 元，接下来因为优惠，买 $1, 3$ 样都只要 $2$ 元，共 $7$ 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 $4$ 元买剩下那件，而选择用 $2$ 元。）

数据规模

对于 $30\%$ 的数据， $1\le B\le 10$ 。

对于 $100\%$ 的数据， $1\le B\le500,0\le A,K_{I,J}\le1000$ 。

2018.7.25新添数据一组

大致思路

~~简单的最小生成树问题~~
对于这种问题，关键是如何把题目转化为使用最小生成树解决。

对于本题，注意每个物品有自己的初始价格与优惠价格

但是！也有反向优惠（优惠了还不如不优惠）的情况

那么我们需要选择所有物品，而物品之间有优惠关系，可以把每个物品看做一个点，每个优惠看作一条边权为 w 的边，那么这个问题也就转化为了最小生成树问题

对于上述的反向优惠的情况，我们可以建一个超级点 ‘0’，向每一个点建一条边权为 a 的边，这样就可以避免反向优惠的情况啦~

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+114514;
int a,n,ans=0;
int sum=0,fa[N];
struct node{int u,v,w;
}k[N];
bool cmp(node aa,node bb){return aa.w<bb.w;
}
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);
}
void kruskal(){sort(k+1,k+1+sum+n+1,cmp);for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=sum+n+1;i++){if(find(k[i].u)!=find(k[i].v)){ans+=k[i].w;merge(k[i].u,k[i].v);}}
}
int main(){cin>>a>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int w;cin>>w;if(w==0)continue;sum++;k[sum].u=i;k[sum].v=j;k[sum].w=w;}}for(int i=sum+1;i<=sum+n;i++){k[i].u=0;k[i].v=i-sum;k[i].w=a;}kruskal();cout<<ans<<endl;return 0;
}