洛谷 P1194 买礼物

题目描述

又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这B样东西价格都是A元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第II样东西，再买第J样，那么就可以只花KI,J元，更巧的是，KI,J竟然等于KJ,I。

现在明明想知道，他最少要花多少钱。

输入输出格式

输入格式：

第一行两个整数，A,B。

接下来BB行，每行B个数，第I行第J个为KI,J。

我们保证KI,J=KJ,I并且KI,I=0。

特别的，如果KI,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,KI,J≤1000。

思路：直接求一边最小生成树，然后加上买第一件物品所花的费用，即A

注意：在原价比优惠价便宜时，应取优惠价

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<ctime>

using namespace std;

const int M = ;

int n, m, k, tot, sum;

int fa[M];

struct nond {

    int u, v, w;

}e[M];

int find(int x) {

    return fa[x] == x ? x : fa[x] = find(fa[x]);

}

bool cmp(nond x, nond y) {

    return x.w < y.w;

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) fa[i] = i;

    for(int i = ; i <= m; i++)

        for(int j = ; j <= m; j++) {

            int a;

            scanf("%d", &a);

            if(a !=  && i < j) {

                e[++k].u = i;

                e[k].v = j;

                e[k].w = a;

            }

        }

    sort(e+, e+k+, cmp);

    for(int i = ; i <= k; i++) {

        int x = find(e[i].u),  y = find(e[i].v);

        if(x == y) continue;

        srand(time() + );

        if(rand()%) fa[x] = y;

        else fa[y] = x;

        tot++;

        sum += e[i].w;

        if(tot == n-) break;

    }

    sum += n;

    printf("%d\n", sum);

    return ;

}

90分，没有考虑原价低于优惠价的情况

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

const int M = ;

int n, m, tot, sum, k;

int fa[M], f[M];

struct nond {

    int u, v, w;

}e[M];

int find(int x) {

    return fa[x] == x ? x : fa[x] = find(fa[x]);

}

bool cmp(nond x, nond y) {

    return x.w < y.w;

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) fa[i] = i;

    for(int i = ; i <= m; i++)

        for(int j = ; j <= m; j++) {

            int a;

            scanf("%d", &a);

            if(a !=  && i < j) {

                e[++k].u = i;

                e[k].v = j;

                e[k].w = a;

            }

        }

    sort(e+, e+k+, cmp);

    for(int i = ; i <= k; i++) {

        int x = find(e[i].u), y = find(e[i].v);

        if(x == y) continue;

        fa[x] = y;

        tot++;

        sum += min(n, e[i].w);

        if(tot == n-) break;

    }

    sum += n;

    printf("%d\n", sum);

    return ;

}

AC代码

巴特西

洛谷 P1194 买礼物

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章