星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1194 【买礼物】

posted on 2017-10-17 20:46:44 | under 题解 |

博客

这个题是一个模型转换题。也是我第一个独立想模型转换A掉还手打一遍过的题

题目中说明买两个东西有优惠,而且还贴心地把商品价格固定,则我们可以根据输入的格式想到,把每两个点之间连边。

发现题目说明买全部商品并求价格最小值,那么可以用最小生成树求解。

我个人用的Prim堆优化(因为最近在复习)以及pbds大法好,特判一下第一个点加一下A就可以了。

我好像没判图不连通的情况也过了ORZ

记得一开始确定初始生成树节点虽然好像图都连通所以直接1就可以了没关系

上代码。

#include<cstdio>
#include<ext/pb_ds/priority_queue.hpp>
#define neko 5010
#define meko 200010
#define f(i,a,b) for(register int i=a;i<=b;++i)
struct node
{
    int u,v,w,next;
}e[meko<<1];
int n,m,t,root,ans,side,book[neko],head[neko];
struct cmp
{
    bool operator()(const int &x,const int &y)const
    {return e[x].w>e[y].w;}
};
__gnu_pbds::priority_queue<int,cmp>q;
void add(int x,int y,int z)
{
    e[++t].u=x;
    e[t].v=y;
    e[t].w=z;
    e[t].next=head[x];
    head[x]=t;
}
void prim()
{
    int ans=0;
    book[root]=1;
    for(int i=head[root];i;i=e[i].next)q.push(i);//存下标
    while(!q.empty()&&side<m)
    {
        int x=q.top(),v;
        q.pop(),v=e[x].v;
        //printf("%d ",x);//check MST
        if(!book[v])
        {
            ans+=e[x].w,++side;
            book[v]=1;
            for(int i=head[v];i;i=e[i].next)if(!book[e[i].v])q.push(i);
        }
    }printf("%d\n",ans+n);//A
}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    f(i,1,m)
     f(j,1,m)
     {
         scanf("%d",&x);
         if(x){add(i,j,x);if(!root)root=i;}
     }prim();
}