专栏首页calmoundHDU 1863 畅通工程

HDU 1863 畅通工程

一道很朴素的最小生成树,不过通过此题知道了,当n已经决定的情况下,若n个点无法构成最小生成树的话,最终得到ans无法得到精确的值,他会将无穷大的路径加入。

#include<stdio.h>
#include<string.h>

const int MAXN=110;
const int INF=9999999;
int mat[MAXN][MAXN];
int vis[MAXN];
int flag;

int Prim(int n)
{
    int lowcost[MAXN];
    int mst[MAXN];
    int i,j,min,minid,sum=0;
    for (i=1;i<=n;i++)
    {
        lowcost[i]=INF;
        vis[i]=0;
        mst[i]=1;
    }
    lowcost[1]=0;
    for (i=1;i<=n;i++)
    {
        min=INF;
        for (j=1;j<=n;j++)
        {
            if(lowcost[j]<min && !vis[j])
            {
                min=lowcost[j];
                minid=j;
            }
        }
        if(min==INF) flag=1;
        sum+=min;
        vis[minid]=1;
        for (j=1;j<=n;j++)
        {
            if(mat[minid][j]<lowcost[j])
            {
                lowcost[j]=mat[minid][j];
                mst[j]=minid;
            }
        }
    }
    return sum;
}

int main()
{
    int n,m,i,j,a,b,c;
    int cas;
    while(scanf("%d%d",&m,&n) && m)
    {
        flag=0;
        cas=0;
        memset(vis,0,sizeof(vis));
        for(i=0;i<=n;i++)
            for (j=0;j<=n;j++)
                mat[i][j]=INF;
            for (i=0;i<m;i++)
            {
                scanf("%d%d%d",&a,&b,&c);
                if(c<mat[a][b]) mat[a][b]=mat[b][a]=c;
            }
        //    printf("%d\n",cas);
            int ans=Prim(n); 
            if(flag) printf("?\n");
            else printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Merge Sorted Array

    问题:将B按顺序合并到A上 分析:插入排序,注意A数组为空 class Solution { public: void merge(int A[], i...

    用户1624346
  • zoj 2521 LED Display

    题意:开灯,每个数字都由好几个灯组成,其中一些数字灭掉某些灯可以成为另一个数字,如0灭掉3个灯可以变成7,         现给你一组数字,如何组合可以形成最少...

    用户1624346
  • CSU 1326: The contest(分组背包)

    http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326 题意:       n个题目,每个题目都有一个价值P...

    用户1624346
  • 计算矩阵中全1子矩阵的个数

    最近被我大哥安利了一道算法题, 这道题说难, 还不至于我做不出来, 说简单吧, 我还想不到最优解, 等把最优解告诉我之后, 我还正好能理解. 我甚至曾经怯怯的认...

    烟草的香味
  • Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

    题目链接:http://codeforces.com/contest/1077/problem/D

    Ch_Zaqdt
  • ZR18提高5解题报告

    设$f[i][j]$表示前$i$个位置,前缀和为$j$的方案数,转移的时候该位置放了什么,以及该位置之前的和是多少。

    attack
  • 1048 石子归并

    1048 石子归并 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有n堆石子...

    attack
  • 2017.5.26暴力赛解题报告

    预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • 3117 高精度乘法

    3117 高精度练习之乘法  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给出...

    attack

扫码关注云+社区

领取腾讯云代金券