kuangbin八A:POJ 1679 The Unique MST(次小生成树)

Description:

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V’, E’), with the following properties:
1. V’ = V.
2. T is connected and acyclic.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string ‘Not Unique!’.

Sample Input

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!

次小生成树求一波,判断其总权值是否与最小生成树总权值一致,不一致就Unique,一致就Not Unique!。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 111;
const int inf = 0x3f3f3f3f;
int Map[maxn][maxn];//邻接矩阵存图
int Max[maxn][maxn];//表示最小生成树中i到j的最大边权
bool used[maxn][maxn];//判断该边是否加入最小生成树
int pre[maxn];
int dis[maxn];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) Map[i][j] = 0;
            else Map[i][j] = inf;
}
void read(int m)
{
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        Map[u][v] = Map[v][u] = w;
    }
}
int prim(int n)
{
    int ans = 0;
    bool vis[maxn];
    memset(vis, false, sizeof(vis));
    memset(used, false, sizeof(used));
    memset(Max, 0, sizeof(Max));
    for (int i = 2; i <= n; i++) 
    {
        dis[i] = Map[1][i];
        pre[i] = 1;
    }
    pre[1] = 0;
    dis[1] = 0;
    vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        int min_dis = inf, k;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && min_dis > dis[j])
            {
                min_dis = dis[j];
                k = j;
            }
        }
        if (min_dis == inf) return -1;//如果不存在最小生成树
        ans += min_dis;
        vis[k] = true;
        used[k][pre[k]] = used[pre[k]][k] = true;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j]) Max[j][k] = Max[k][j] = max(Max[j][pre[k]], dis[k]);
            if (!vis[j] && dis[j] > Map[k][j])
            {
                dis[j] = Map[k][j];
                pre[j] = k;
            }
        }
    }
    return ans;//最小生成树的权值之和
}
int smst(int n, int min_ans)//min_ans 是最小生成树的权值和
{
    int ans = inf;
    for (int i = 1; i <= n; i++)//枚举最小生成树之外的边
        for (int j = i + 1; j <= n; j++)
            if (Map[i][j] != inf && !used[i][j])
                ans = min(ans, min_ans + Map[i][j] - Max[i][j]);
    if (ans == inf) return -1;
    return ans;
}
void solve(int n)
{
    int ans = prim(n);
    if (ans == -1)
    {
        puts("Not Unique!");
        return;
    }
    if (smst(n, ans) == ans)
    printf("Not Unique!\n");
    else
    printf("%d\n", ans);
}

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &m);
        init(n);
        read(m);
        solve(n);
    }
    return 0;
}
全部评论

相关推荐

来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 12:26
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务