首页 > 代码库 > HDU4966 GGS-DDU(最小树形图)
HDU4966 GGS-DDU(最小树形图)
之前几天想着补些算法的知识,学了一下最小树形图的朱刘算法,不是特别理解,备了份模板以备不时之需,想不到多校冷不丁的出了个最小树形图,没看出来只能表示对算法不太理解吧,用模板写了一下,然后就过了。- -0
之前听到是最小树形图的时候觉得恍然大悟,非常裸,但是后来想想也不是特别裸,其实关键就是要想清楚要加回流的边,贴一份代码吧- -0
#pragma warning(disable:4996)#include<cstdio>#include<set>#include<cstring>#include<iostream>#include<stdlib.h>#include<vector>#include<map>#include<algorithm>#include<queue>#include<cmath>#include<functional>#include<string>using namespace std;#define maxn 550int n, m;int a[55];struct Edge{ int u, v, w; Edge(int ui, int vi, int wi) :u(ui), v(vi), w(wi){} Edge(){}};vector<Edge> E;vector<int> vid[55];int in[maxn]; // minimum pre edge weightint pre[maxn]; // pre vertexint vis[maxn]; // vis arrayint id[maxn]; // mark down the idint nv; // nv is the number of vertex after shrinkingint directed_mst(int root,int vertex_num){ int ret = 0; int nv = vertex_num; while (1){ for (int i = 0; i < nv; ++i) in[i] = 1e9; for (int i = 0; i < E.size(); ++i){ int u = E[i].u, v = E[i].v; if (E[i].w < in[v] && u != v){ in[v] = E[i].w; pre[v] = u; } } for (int i = 0; i < nv; ++i){ if (i == root) continue; if (in[i]>1e8) return -1; } int cnt = 0; memset(id, -1, sizeof(id)); memset(vis, -1, sizeof(vis)); in[root] = 0; for (int i = 0; i < nv; ++i){ ret += in[i]; int v = i; while (vis[v] != i&&id[v] == -1 && v != root){ vis[v] = i; v = pre[v]; } // v!=root means we find a circle,id[v]==-1 guarantee that it‘s not shrinked. if (v != root&&id[v] == -1){ for (int u = pre[v]; u != v; u = pre[u]){ id[u] = cnt; } id[v] = cnt++; } } if (cnt == 0) break; for (int i = 0; i < nv; ++i){ if (id[i] == -1) id[i] = cnt++; } // change the cost of edge for each (u,v,w)->(u,v,w-in[v]) for (int i = 0; i < E.size(); ++i){ int v = E[i].v; E[i].u = id[E[i].u]; E[i].v = id[E[i].v]; if (E[i].u != E[i].v) E[i].w -= in[v]; } // mark down the new root root = id[root]; // mark down the new vertex number nv = cnt; } return ret;}int main(){ while (cin >> n >> m){ if (n == 0 && m == 0) break; int tot = 0; for (int i = 1; i <= n; ++i) { vid[i].clear(); scanf("%d", a + i); for (int j = 0; j <= a[i]; ++j){ vid[i].push_back(++tot); } } ++tot; E.clear(); for (int i = 1; i <= n; ++i){ for (int j = 0; j < vid[i].size(); ++j){ for (int k = j + 1; k < vid[i].size(); ++k){ E.push_back(Edge(vid[i][k], vid[i][j], 0)); } } } int ci, l1, di, l2, wi; for (int i = 0; i < m; ++i){ scanf("%d%d%d%d%d", &ci, &l1, &di, &l2, &wi); E.push_back(Edge(vid[ci][l1], vid[di][l2], wi)); } for (int i = 1; i <= n; ++i){ E.push_back(Edge(0, vid[i][0], 0)); } int ans = directed_mst(0,tot); printf("%d\n", ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。