P1194 买礼物题解

扬皓2006 · 2019-10-04 11:58:43 · 题解

本题可以用Kruskal算法实现（理解简单码起来较难）

有一些坑点

1.有优惠才建图

2.在加的时候如果优惠价比原价高就加原价（这也是很多人90分的原因）

3.最后输出还要加A

上代码！

#include<bits/stdc++.h>//万能头
using namespace std;
int a,b,tot,ans=0,x,fa[500001];
struct Edge{
    int from,to,dis;
}edge[500001];//邻接表
void add(int x,int y,int z)
{
    edge[++tot].from=x;
    edge[tot].to=y;
    edge[tot].dis=z;
}//存边
bool operator <(Edge A,Edge B)
{
    return A.dis<B.dis;
}//重载运算符
int get(int x)
{
    if(fa[x]==x)  return x;
    return fa[x]=get(fa[x]);
}//并查集查询祖先
int main()
{
    scanf("%d%d",&a,&b);
    for(int i=1;i<=b;i++)
    {
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&x);
            if(i<=j&&x!=0)
            add(i,j,x); //坑点1
        }
    }
    for(int i=1;i<=b;i++)  fa[i]=i;//把所有人的祖先都重置为自己
    sort(edge,edge+tot+1);//边权排序一下
    for(int i=1;i<=tot;i++)
    {
        int x=get(edge[i].from);
        int y=get(edge[i].to);
        if(x==y)  continue;
        fa[x]=y;
        if(edge[i].dis<a)//坑点2
        ans+=edge[i].dis;
        else ans+=a;
    }//Kruskal
    printf("%d",ans+a);//坑点3
    return 0;
}

最后，希望所有同学都能A掉这道题（不要抄题解），也希望管理大大能够通过这篇题解！

P1194 买礼物 题解

P1194 买礼物题解