题目内容

P1194

大意:小明买B件价格都为A的礼物,商店有促销,说如果买了I再买J,价格可优惠为K_{I,J}元,保证K_{I,J}=K_{J,I}K_{I,I}=0

给定上述数据,求小明花费的最小值

解题思路

嗯,我们可以将这些礼物抽象成图的节点,优惠价格抽象成边,于是这道题就是让我们求这张图的最小生成树。

最小生成树的权值之和再加上一个物品的价格就是小明需要花的总价格

我使用的是Kruskal算法,但是:

坑点:

  • 读入时给出的是邻接矩阵,读入时记得去掉重边(不去好像没关系,但去掉之后可以优化排序时的常数,时间快了一倍(亲测))
  • 记得定义edge结构体的cmp函数
  • 最重要的:优惠后的价格可能比原价还要贵妈的就是因为这个第一次WA了#11,输出时要判断。

代码:

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct unionset//并查集维护kruskal
{
    int bin[505];
    unionset()
    {
        for(int i=1;i<=505;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(x==bin[x])
            return x;
        else return bin[x]=anc(bin[x]);
    }
    bool query(int x,int y)
    {
        return anc(x)==anc(y);
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
}u;

struct edge//边的结构体
{
    int from,to,dist;
    edge(){}
    edge(int _from,int _to,int _dist)
    {
        this->from=_from;
        this->to=_to;
        this->dist=_dist;
    }
};

bool cmp(edge a,edge b)//edge定义的比较函数
{
    return a.dist<b.dist;
}

int a,b;
vector<edge> q;//存储边用的

int kruskal()
{
    int ans=0;
    sort(q.begin(),q.end(),cmp);//排序时用迭代器不会错
    for(auto &e:q)//我爱C++11
    {
        int from=e.from,to=e.to,dist=e.dist;
        if(!u.query(from,to))
        {
            u.uni(from,to);
            ans+=dist;
        }
    }
    return ans;
}

int main()
{
    scanf("%d %d",&a,&b);
    for(int i=1;i<=b;i++)
    {
        for(int j=1;j<=b;j++)
        {
            int k;
            scanf("%d",&k);
            if(k&&j<=i)//j<=i可以去掉邻接矩阵的重边
                q.push_back(edge(i,j,k));
        }
    }
    int ans=kruskal();
    printf("%d\n",a+ans<a*b?a+ans:a*b);//输出时特判
    return 0;
}
最后修改日期:2020年2月2日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。