题目描述
题目描述
又到了一年一度的明明生日了,明明想要买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
0
输出样例#1:
1
输入样例#2:
3 3
0 2 4
2 0 2
4 2 0
输出样例#2:
7
算法1
(Kruskal)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f,M=1010;
int f[N],A,B,cnt;
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
struct Edge
{
int a,b,w;
}edges[N];
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int main()
{
cin>>A>>B;
for(int i=1;i<=B;i++)
{
for(int j=1;j<=B;j++)
{
int temp;
cin>>temp;
if(j<=i&&temp!=0)//依题意特判,同时为了减少循环次数,因为K_{i,j}=K_{j,i},可用是否j<=i或是否i<=j来判断处理.
{
edges[++cnt].a=i;
edges[cnt].b=j;
edges[cnt].w=temp;
}
}
}
sort(edges+1,edges+cnt+1,cmp);
int res=0;
for(int i=1;i<=B;i++) f[i]=i;
for(int i=1;i<=cnt;i++)
{
int f1=find(edges[i].a),f2=find(edges[i].b);
if(f1!=f2)
{
f[f1]=f2;
if(edges[i].w<A)//如果优惠价大于原价,那就按原价购买(虽然现实中基本不可能出现这种情况)
res+=edges[i].w;
else
res+=A;
}
}
for(int i=1;i<=B;i++) if(f[i]==i) res+=A;//可能有些东西明明要买但是没有优惠,此时需要用并查集判断哪个点没连上,再加上相应的价格.
printf("%d\n",res);
return 0;
}