HDU - 3072 Intelligence System(强连通分量+类最小 - 公司荣誉 - 长春市隆兴伟业物流有限公司
现在的位置: 主页 > 公司荣誉 > 文章正文
HDU - 3072 Intelligence System(强连通分量+类最小
作者:长春市隆兴伟业物流有限公司 来源:www.lxwywl.com 发布时间:2018-04-07 09:43:46
HDU - 3072 Intelligence System(强连通分量+类最小生成树)

题目大意:有一个人想要将消息告诉给所有人(在同一个强连通分量里面的人可以相互转告,费用为0),问所有人都知道消息的最小花费是多少

解题思路:求出所有的强连通分量,然后将其缩点,桥就是连接其中的边
因为是张连通图,所以只要求出每个强连通分量被通知的最小价值,然后累加即可
刚开始以为可以用最小生成树,但发现错了,假设求出了三个强连通分量了,分别标号为1,2,3
再给出桥 1-2,权值1,1-3权值5,3-2权值4
按最小生成树的话,得到的结果是5,然而并不是这样的,因为是有向边,所以3这个点是不会被通知到的。

#include #include #include using namespace std; #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define N 50010 #define INF 0x3f3f3f3f #define M 100010 struct Edge{ int to, from, next, val; }E[M]; int head[N], pre[N], lowlink[N], sccno[N], stack[N], d[N]; int n, m, tot, scc_cnt, top, dfs_clock; void AddEdge(int from, int to, int val) { E[tot].from = from; E[tot].to = to; E[tot].next = head[from]; E[tot].val = val; head[from] = tot++; } void init() { memset(head, -1, sizeof(head)); tot = 0; int u, v, val; for (int i = 0; i < m; i++) { scanf(%d%d%d, &u, &v, &val); AddEdge(u, v, val); } } void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; stack[++top] = u; for (int i = head[u]; i != -1; i = E[i].next) { int v = E[i].to; if (!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if (!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } int x; if (pre[u] == lowlink[u]) { scc_cnt++; while (1) { x = stack[top--]; sccno[x] = scc_cnt; if (x == u) break; } } } void solve() { memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); dfs_clock = top = scc_cnt = 0; for (int i = 0; i < n; i++) if (!pre[i]) dfs(i); int u, v; memset(d, 0x3f, sizeof(d)); for (int i = 0; i < tot; i++) { u = sccno[E[i].from], v = sccno[E[i].to]; if (u != v) { d[v] = min(d[v], E[i].val); } } int ans = 0; for (int i = 1; i <= scc_cnt; i++) if (d[i] != INF) ans += d[i]; printf(%d , ans); } int main() { while (scanf(%d%d, &n, &m) != EOF) { init(); solve(); } return 0; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:黄陂网站建设 http://www.Hpwzjs.cn


  • 上一篇:python实现QQ机器人(自动登录,获取群消息,发送群消
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 长春市隆兴伟业物流有限公司 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100