洛谷题解-P1194 买礼物

https://www.luogu.com.cn/problem/P1194

题目描述

又到了一年一度的明明生日了，明明想要买 BBB 样东西，巧的是，这 BBB 样东西价格都是 AAA 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 III 样东西，再买第 JJJ 样，那么就可以只花 KI,JK_{I,J}KI,J​ 元，更巧的是，KI,JK_{I,J}KI,J​ 竟然等于 KJ,IK_{J,I}KJ,I​。

现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数，A,BA,BA,B。

接下来 BBB 行，每行 BBB 个数，第 III 行第 JJJ 个为 KI,JK_{I,J}KI,J​。

我们保证 KI,J=KJ,IK_{I,J}=K_{J,I}KI,J​=KJ,I​ 并且 KI,I=0K_{I,I}=0KI,I​=0。

特别的，如果 KI,J=0K_{I,J}=0KI,J​=0，那么表示这两样东西之间不会导致优惠。

注意 KI,JK_{I,J}KI,J​ 可能大于 AAA。

输出格式

一个整数，为最小要花的钱数。

输入输出样例

1 1
0

1

3 3
0 2 4
2 0 2
4 2 0

7

说明/提示

样例解释 222。

先买第 222 样东西，花费 333 元，接下来因为优惠，买 1,31,31,3 样都只要 222 元，共 777 元。

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

数据规模

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

对于 100%100\%100% 的数据，1≤B≤500,0≤A,KI,J≤10001\le B\le500,0\le A,K_{I,J}\le10001≤B≤500,0≤A,KI,J​≤1000。

2018.7.25新添数据一组

又是“最小”，可以考虑最小生成树

超级源点是0点向每个点连边，可以用在此题

（因为题目要求要买b件礼物，但是所有礼物都是通过一个礼物去买另外一个礼物，却不能买自身的这个礼物）

所以要能选到这个礼物，建一个点，但是总不可能礼物自己和自己连边，因为最小生成树肯定不会有自环

所以要考虑从0号点去选，通过0号店到这个点，就能选到这个礼物了

但是退出条件的n记得+1，因为总节点数+1了

#include <bits/stdc++.h>
using namespace std;

const int N=500005;
struct node
{
	int u, v, w;
}a[N];
int x, n, w1, dis[N], vis[N], ans=0, e=0, f[N], cnt=0;
bool cmp(node a, node b)
{
	return a.w<b.w;
}
int find(int x)
{
	if (f[x]==x) return x;
	return f[x]=find(f[x]);
}
void kru()
{
	sort(a+1, a+1+e, cmp);
	for (int i=1; i<=n; i++) f[i]=i;
	
	for (int i=1; i<=e; i++)
	{
		int u=a[i].u, v=a[i].v, w=a[i].w;
		int x=find(u), y=find(v);
		
		if (x!=y)
		{
			ans+=w;
			f[x]=y;
			cnt++;
		}
		if (cnt==n-1) return ;
	}
}
int main()
{
	scanf("%d%d", &x, &n);
	for (int i=1; i<=n; i++) //超级源点
	{
		a[++e]={0, i, x};
		a[++e]={i, 0, x};
	}
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			scanf("%d", &w1);
			if (i==j) continue;
			if (w1==0 || w1>x) w1=x;
			a[++e]={i, j, w1};
		}
	}
	n++; //总节点数+1
	kru();
	
	printf("%d", ans);
	return 0;
}