P1194 买礼物

题目描述

又到了一年一度的明明生日了，明明想要买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：

输入样例#2：

输出样例#2：

说明

样例解释2

先买第2样东西，花费3元，接下来因为优惠，买1，3样都只要2元，共7元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用4元买剩下那件，而选择用2元。）

数据规模

对于30%的数据,1<=B<=10。

对于100%的数据,1<=B<=500，0<=A,K[I,J]<=1000。

Solution：

　　本题其实很简单（结果被小错误卡了好久～～手动滑稽～～）。

　　建边跑最小生成树，注意建边时应该取边权和$a$的最小值，最后由于第一次选点要花费$a$，所以输出时加上$a$就$OK$了。

代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Min(a,b) ((a)>(b)?(b):(a))
#define il inline
using namespace std;
const int N=505;
int a,b,fa[N],ans,x,cnt;
struct node{
    int fr,to,w;
    void add(int x,int y,int z){fr=x,to=y,w=z;}
    bool operator<(const node a)const {return w<a.w;}
}e[N*N];
bool vis[N][N];
il int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
int main(){
    ios::sync_with_stdio(0);
    cin>>a>>b;
    For(i,1,b)fa[i]=i;
    For(i,1,b) For(j,1,b) {cin>>x;if(x&&!vis[i][j])e[++cnt].add(i,j,Min(x,a)),vis[i][j]=vis[j][i]=1;}
    sort(e+1,e+cnt+1);
    int x,y,p=0;
    For(i,1,cnt){
        x=find(e[i].fr),y=find(e[i].to);
        if(fa[x]!=y)ans+=e[i].w,fa[x]=y,p++;
        if(p==b-1)break;
    }
    cout<<ans+a;
    return 0;
}