题解 P1194 【买礼物】

Wenxiang_MCL · 2017-07-21 09:23:59 · 题解

一道十分简单的最小生成树的问题

主要问题是将初始条件设置好

如果两个不同商品间没有优惠，那么这条路径就设为A

构造好最小生成树后，只需要把所有路径累积即可

注意：不要忘了在最后答案加上一个A（第一个东西还是没优惠的）

上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 501;
const int INF = 0x7fffffff;
int f[maxn][maxn];
int dis[maxn];
bool s[maxn];
int main ()
{
    //freopen("present.in","r",stdin);
    int cost,n;
    cin >> cost >> n;
    for (int i = 1;i <= n;i ++)
    for (int j = 1;j <= n;j ++)
    {
        cin >> f[i][j];
        if(i == j) {
            f[i][j] = INF;//自己和自己直接就直接赋极大值
            continue;
        }
        if(!f[i][j]) f[i][j] = cost;
        f[j][i] = f[i][j];//无向图
    }
    for(int i = 1;i <= n;i ++) dis[i] = INF;
    dis[1] = 0;
    for(int i = 1;i <= n;i ++)//prim算法求最小生成树
    {
        int cmin = INF,p;
        for(int j = 1;j <= n;j ++)
            if(dis[j] < cmin&&!s[j]){
                cmin = dis[j];
                p = j;
            }
        s[p] = true;
        for(int j = 1;j <= n;j ++){
            if(f[p][j] < dis[j]&&!s[j]) dis[j] = f[p][j];
        }
    }
    int sum = 0;
    for(int i = 1;i <= n;i ++) sum += dis[i];
    cout << sum + cost;//不要忘了加一个基本价值
}