POJ 1639 k渡限制生成树

POJ 1639 k度限制生成树

题意就是求最小生成树  但是有一个顶点的度必须不大于k

具体的方法网上都有，但是代码写起来之复杂难以令人想象，我由于代码能力还太弱，导致只能看着别人的代码重写一遍，优化了一些部分。

#include <iostream>#include <map>#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 505#define MAXM 100005#define INF 1000000000using namespace std;struct node{ int v, w, next;}edge[MAXM];int n, m, k, sum;int e, head[MAXN], vis[MAXN], dis[MAXN], use[MAXN][MAXN];int blocks, size[MAXN], belong[MAXN], pre[MAXN], mx[MAXN];int point[MAXN], link[MAXN];map<string, int>mp;void init(){ e = 0, n = 1; blocks = 0, sum = 0; memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); memset(size, 0, sizeof(size)); memset(use, 0, sizeof(use)); memset(mx, 0, sizeof(mx)); memset(pre, 0, sizeof(pre)); mp.clear();}void insert(int x, int y, int w){ edge[e].v = y; edge[e].w = w; edge[e].next = head[x]; head[x] = e++;}int getId(char s[]){ if(mp.find(s) == mp.end()) mp[s] = ++n; else return mp[s]; return n;}void dfs(int v){ vis[v] = 1; size[blocks]++; belong[v] = blocks; for(int i = head[v]; i != -1; i = edge[i].next) if(!vis[edge[i].v]) dfs(edge[i].v);}void prim(int cur){ for(int i = 1; i <= n; i++) dis[i] = INF; for(int i = 1; i <= n; i++) if(belong[i] == cur) { dis[i] = 0; break; } for(int i = 1; i <= size[cur]; i++) { int mi = INF, pos; for(int j = 1; j <= n; j++) if(!vis[j] && mi > dis[j]) mi = dis[j], pos = j; sum += mi; vis[pos] = 1; for(int j = head[pos]; j != -1; j = edge[j].next) if(!vis[edge[j].v] && dis[edge[j].v] > edge[j].w) { dis[edge[j].v] = edge[j].w; pre[edge[j].v] = pos; } }}void getMax(int v, int fa, int w){ pre[v] = fa; mx[v] = max(mx[fa], w); for(int i = head[v]; i != -1; i = edge[i].next) if(use[v][edge[i].v] && edge[i].v != fa) getMax(edge[i].v, v, edge[i].w);}int main(){ char s1[55], s2[55]; int w; scanf("%d", &m); init(); mp["Park"] = 1; for(int i = 0; i < m; i++) { scanf("%s%s%d", s1, s2, &w); insert(getId(s1), getId(s2), w); insert(getId(s2), getId(s1), w); } scanf("%d", &k); vis[1] = 1; for(int i = 2; i <= n; i++) if(!vis[i]) { blocks++; dfs(i); } memset(vis, 0, sizeof(vis)); vis[1] = 1; for(int i = 1; i <= blocks; i++) prim(i); for(int i = 2; i <= n; i++) use[i][pre[i]] = use[pre[i]][i] = 1; for(int i = 1; i <= n; i++) link[i] = INF; for(int i = head[1]; i != -1; i = edge[i].next) if(link[belong[edge[i].v]] > edge[i].w) { link[belong[edge[i].v]] = edge[i].w; point[belong[edge[i].v]] = edge[i].v; } for(int i = 1; i <= blocks; i++) { sum += link[i]; use[1][point[i]] = use[point[i]][1] = 1; } int degree = blocks; getMax(1, 0, 0); while(degree < k) { int maxval = 0, pos = 0, w; for(int i = head[1]; i != -1; i = edge[i].next) if(!use[1][edge[i].v] && mx[edge[i].v] - edge[i].w > maxval) { maxval = mx[edge[i].v] - edge[i].w, pos = edge[i].v; w = edge[i].w; } if(!pos) break; sum -= maxval; degree++; int temp = pos, j; while(true) { for(j = head[temp]; j != -1; j = edge[j].next) if(edge[j].v == pre[temp]) break; if(edge[j].w == mx[pos]) break; else temp = pre[temp]; } use[temp][pre[temp]] = use[pre[temp]][temp] = 0; pre[pos] = 1; getMax(pos, 1, w); } printf("Total miles driven: %d\n", sum); return 0;}