题解 P1194 【买礼物】

[博客](http://teafrog26.lofter.com/) 这个题是一个模型转换题。~~也是我第一个独立想模型转换A掉还手打一遍过的题~~ 题目中说明买两个东西有优惠，而且还贴心地把商品价格固定，则我们可以~~根据输入的格式~~想到，把每两个点之间连边。 发现题目说明买全部商品并求价格最小值，那么可以用最小生成树求解。 我个人用的Prim堆优化（因为最近在复习）~~以及pbds大法好~~，特判一下第一个点加一下A就可以了。 我好像**没判图不连通的情况**也过了ORZ 记得一开始确定初始生成树节点~~虽然好像图都连通所以直接1就可以了没关系~~ 上代码。 ```cpp #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(); } ```