洛谷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\)，那么表示这两样东西之间不会导致优惠。

注意 \(K_{I,J}\) 可能大于 \(A\)。

输出格式

一个整数，为最小要花的钱数。

样例 #1

样例输入 #1

1 1
0

样例输出 #1

1

样例 #2

样例输入 #2

3 3
0 2 4
2 0 2
4 2 0

样例输出 #2

7

提示

样例解释 \(2\)。

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

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

数据规模

对于 \(30\%\) 的数据，\(1\le B\le 10\)。

对于 \(100\%\) 的数据，\(1\le B\le500,0\le A,K_{I,J}\le1000\)。

2018.7.25新添数据一组

此题看似不难，实则确实不难，可说是板子。但敲完后，窝整整调了一个多小时，这样例太水了结果发现读入挂了TNT。

正片开始

1.审题

1. 注意到\(k_{i,j}=k_{j,i}\),显然这是一个无向图，每个东西买一次求最小价值，更显然是最小生成树。
2. 还需注意：\(k_{i,j}=0\)时的特殊情况。
3. 还有\(k_{i,j}\)可能大于\(A\)。需要我们取下\(min\)。

读入部分：

code：

cin>>a>>n;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        ll w;cin>>w;
        if(i!=j&&w!=0) w=min(w,a);
        else w=a;
        g[i].push_back(make_pair(j,w));
        g[j].push_back(make_pair(i,w));
    }

2.prim模板

将所有点分成已选点和待选点两个集合，每次遍历待选点的集合，选择边权最小的边，再更新与此次选择的点相接的点的距离，直到待选点集合为零即可。

code：

void prim()
{
    for(int i=0;i<=n;i++) d[i]=a;//初始化距离
    d[1]=0;//第一个点的距离为零
    ans+=a;//第一个必须以原价进入
    while(1)
    {
        int u=-1;
        for(int i=1;i<=n;i++){if(!vis[i]&&(u==-1||d[u]>d[i]))u=i;}//寻找最小的点
        if(u==-1) break;//待选点集合为空
        vis[u]=1;ans+=d[u];//加入被选择的点
        for(auto each:g[u])
        {
            ll v=each.first,w=each.second;
            if(vis[v]) continue;
            d[v]=min(d[v],w);
        }//更新距离
    }
    cout<<ans<<endl;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n,a,ans=0,d[N],vis[N];
vector<pair<ll,ll> >g[N];
void prim()
{
    for(int i=0;i<=n;i++) d[i]=a;
    d[1]=0;
    ans+=a;
    while(1)
    {
        int u=-1;
        for(int i=1;i<=n;i++){if(!vis[i]&&(u==-1||d[u]>d[i]))u=i;}
        if(u==-1) break;
        vis[u]=1;ans+=d[u];
        for(auto each:g[u])
        {
            ll v=each.first,w=each.second;
            if(vis[v]) continue;
            d[v]=min(d[v],w);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    cin>>a>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            ll w;cin>>w;
            if(i!=j&&w!=0) w=min(w,a);
            else w=a;
            g[i].push_back(make_pair(j,w));
            g[j].push_back(make_pair(i,w));
        }
    prim();
    return 0;
}

审题不规范，oi两行泪。

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)