专栏首页Zaqdt_ACMHDU 2121 Ice_cream’s world II(最小树形图+虚根)

HDU 2121 Ice_cream’s world II(最小树形图+虚根)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2121

       题意是有n个点(0--n-1),m条有向边,问以那个点作为起点使得最小生成树的权值最小,如果可以构成输出权值和顶点编号,否则输出impossible。

       对于这种不定根的题,在不知道虚根这个东西前我是暴力去写的,就是以每一个点都为顶点跑一遍朱刘算法求最小值,按理说因该是TLE才对,然后被我写WA了....然后来说一下用虚根的写法,很巧妙...对于已经建好的图的基础上再额外的加一个点,让这个点与其他的n个点都连一条边,边的权值为前n个点的权值之和再+1,所以现在是有n+1个点,m+n条边。

       例如题中的第二个样例,以新加的这个4这个点为根,会得到如下图的图。

       然后我们以编号为4的点为根,跑朱刘算法,用橙色线标记出来的就是一个最小生成树,所以最后的生成树的权值就是ans-sum(sum是前m条边的权值之和+1)。对于找最小根的情况,我们需要在寻找最小弧的时候判断一下就好了,因为存的边是先存的前m条边,再存的后n条边,所以对于前m条边都进行完入边操作后就剩下0这个结点还没有入边,所以在后n条边中更新了0这个点的入边,而且此时0点的最小入边的权值就是71,所以就可以判断出0就是我们要找的最小根了,所以标记一下当前的边的编号,然后减去m即为所求。如果最后跑出来的结果是大于等于2*sum,就说明权值为71的边选了两条,所以不能构成最小生成树,这种情况判断一下就好了。虚根的写法不难理解,结合代码想一下就好了。


AC代码:

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 10005;
struct Edge{
    int u, v, cost;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN];
int n,m,root,pos,num;

void add(int u,int v,int w){
  edge[num].u = u;
  edge[num].v = v;
  edge[num++].cost = w;
}

int solve()
{
    int res = 0;
    while (1){
        for(int i=0;i<n;i++) in[i] = INF;
        for(int i=0;i<num;++i){
    			int u = edge[i].u, v = edge[i].v;
    			if(edge[i].cost < in[v] && u != v){
    				pre[v] = u;
						in[v] = edge[i].cost;
            if(u == root) pos = i;      // 标记最小根
    			}
    		}
        for (int i = 0; i < n; i++){
            if (i != root && in[i] == INF) return -1;
        }
        int tn = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;
        for(int i = 0; i < n; i++){
            res += in[i];
            int v = i;
            while(vis[v] != i && id[v] == -1 && v != root){
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && id[v] == -1){
                for(int u = pre[v]; u != v ; u = pre[u]) id[u] = tn;
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++){
            if(id[i] == -1) id[i] = tn++;
        }
        for (int i = 0; i < num; i++){
            int v = edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if (edge[i].u != edge[i].v) edge[i].cost -= in[v];
        }
        n = tn;
        root = id[root];
    }
    return res;
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    int sum = 0;
    num = 0;
    for(int i=0;i<m;i++){
      int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
      sum += w;
      add(u, v, w);
		}
    sum ++;
    for(int i=0;i<n;i++){
      add(n, i, sum);
    }
    n ++;
    root = n - 1;
    int ans = solve();
    if(ans == -1 || ans >= 2 * sum){
      puts("impossible");
    }
    else printf("%d %d\n", ans - sum, pos - m);
    puts("");
  }
  return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深度解析用户画像的标签体系

    用户画像已经是作为一个数据从业者来说家常便饭的内容,围绕自然人的年龄、性别、职业、收入、风险、兴趣等各个维度去建立和完善相关的标签体系,重复重复再重复的优化。 ...

    宇相
  • JVM系列第9讲:JVM垃圾回收器

    前面文章中,我们介绍了 Java 虚拟机的内存结构,Java 虚拟机的垃圾回收机制,那么这篇文章我们说说具体执行垃圾回收的垃圾回收器。

    陈树义
  • 限流的简单使用及学习

    整个系统间的调用都是采用spring cloud这一套去实现的。我所负责的为业务服务端,专门为web端和pc端提供接口调用。在服务刚上线的一段时间,出现了一次雪...

    一枝花算不算浪漫
  • 循序渐进带你学习时间复杂度和空间复杂度。

    写了这么久的算法文章,可以说凡是算法的文章都会涉及到时间复杂度和空间复杂度,可能有些读者对时间复杂度和空间复杂度还有点迷糊,今天特地找了一篇关于时间复杂度和空间...

    帅地
  • AI性别歧视有救,MIT研究人员给出减少AI预测偏差新方法

    在社交媒体的应用场景中,人工智能算法模型的偏差导致搜索结果或用户体验不佳常常出现,甚至可以说是无法规避,如人们熟知的大数据杀熟等。可以预见,当AI应用到医疗保健...

    镁客网
  • 程序员到底有多赚钱,你确定要转学计算机吗?

    最近有一种感觉,好像全世界所有的人在转学计算机,大家熟悉的呆博,本科学电子的,来哈工大之后转了计算机的研究生,他的那些没读计算机研究生的同学,现在也在刷Java...

    谭庆波
  • 编程小知识之 Random接口返回值

    平日工作中,(伪)随机数的使用一定是避不开的,拿 C# 为例,System 命名空间下的 Random 类型一般都是我们生成(伪)随机数的第一选择:

    用户2615200
  • 数学,原来可以这么美!

    导读:法国著名艺术家罗丹曾说:世界中从不缺少美,而是缺少发现美的眼睛。对于我们的眼睛,不是缺少美,而是缺少发现。如果我们能够用数学的眼光来观察世界,又将会是怎样...

    华章科技
  • 算法笔记(九):希尔排序和桶排序

    先将整个待排记录序列分割成若干个子序列,然后分别进行直接插入排序,待整个序列中的数据基本有序时,再对全体记录进行一次直接插入排序。具体做法是:

    free赖权华
  • 8.26头条/字节跳动数据分析面试面经

    笔试简单聊一下吧~我记得好像是4部分,第一部分是简答题,一共3题,都是业务分析,第一题是数学计算,好像是一款app,给了第一天日活,目标是30天后日活达到D30...

    牛客网

扫码关注云+社区

领取腾讯云代金券