[题目链接]
http://poj.org/problem?id=1639
[算法]
首先，我们可以用深度优先遍历求出1号节点去除后有几个联通块
设共有T个联通块，若T > K则无解，否则 ：
求出这些联通块的最小生成树，得到一棵最小T度生成树，我们尝试改动(K - T)条边，使得答案变得更小，具体过程如下 :
枚举所有与1相连的边，若这条边不在当前的生成树中，我们用广度优先搜索求出生成树上1号节点到该条边的节点中最长的边，用这条边的权值减去枚举边的权值即为生成树权值和变小了多少，求出这个变小的最大值
如果这个最大值大于0，将这个最大值对应的边从生成树中删除，并加入新的边，否则退出
重复以上过程(K - T)次，即可
[代码]
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 1010 struct Edge { int u,v,w; } e[MAXN],edge[MAXN][MAXN]; int i,j,n,w,k,tot,block,ans,mx; int val[MAXN],size[MAXN],fa[MAXN],p[MAXN],belong[MAXN]; bool visited[MAXN],flag[MAXN]; int mst[MAXN][MAXN]; map<string,int> mp; string u,v; vector< int > a[MAXN]; pair<int,int> ps,new_e,tmp; inline bool cmp(Edge a,Edge b) { return a.w < b.w; } inline int get_root(int x) { if (fa[x] == x) return x; return fa[x] = get_root(fa[x]); } inline void dfs(int u) { int i,v; visited[u] = true; belong[u] = block; for (i = 0; i < a[u].size(); i++) { v = a[u][i]; if (e[v].u == u && e[v].v != 1 && !flag[v]) { flag[v] = true; edge[block][++size[block]] = e[v]; dfs(e[v].v); } else if (e[v].v == u && e[v].u != 1 && !flag[v]) { flag[v] = true; edge[block][++size[block]] = e[v]; dfs(e[v].u); } } } inline void kruskal(int id) { int i,su,sv; static int s[MAXN]; for (i = 1; i <= n; i++) fa[i] = i; sort(edge[id] + 1,edge[id] + size[id] + 1,cmp); for (i = 1; i <= size[id]; i++) { su = get_root(edge[id][i].u); sv = get_root(edge[id][i].v); if (su != sv) { ans += edge[id][i].w; mst[edge[id][i].u][edge[id][i].v] = edge[id][i].w; mst[edge[id][i].v][edge[id][i].u] = edge[id][i].w; fa[su] = sv; } } } inline pair<int,int> bfs(int s) { int i,cur,l,r,now,mx; static bool visited[MAXN]; static pair<int,int> q[MAXN]; static int pre[MAXN]; bool found = false; pair<int,int> res; memset(visited,false,sizeof(visited)); q[l = r = 1] = make_pair(s,0); visited[s] = true; pre[1] = -1; while (l <= r) { cur = q[l].first; for (i = 1; i <= n; i++) { if (visited[i]) continue; if (!mst[cur][i]) continue; visited[i] = true; q[++r] = make_pair(i,mst[cur][i]); pre[r] = l; if (i == 1) { found = true; break; } } if (found) break; l++; } if (!found) return make_pair(0,0); now = r; mx = 0; while (pre[now] != -1) { if (q[now].second > mx) { mx = q[now].second; res = make_pair(q[pre[now]].first,q[now].first); } now = pre[now]; } return res; } int main() {
cin.tie(0); cin >> n; mp["Park"] = 1; tot = 1; for (i = 1; i <= n; i++) { cin >> u >> v >> w; if (!mp[u]) mp[u] = ++tot; if (!mp[v]) mp[v] = ++tot; e[i] = (Edge){mp[u],mp[v],w}; a[mp[u]].push_back(i); a[mp[v]].push_back(i); } scanf("%d",&k); visited[1] = true; for (i = 1; i <= n; i++) { if (e[i].u == 1 && !visited[e[i].v]) { block++; dfs(e[i].v); } if (e[i].v == 1 && !visited[e[i].u]) { block++; dfs(e[i].u); } } if (block > k) { printf("-1 "); return 0; } for (i = 1; i <= block; i++) kruskal(i); memset(val,0x3f,sizeof(val)); for (i = 1; i <= n; i++) { if (e[i].u == 1 && e[i].w < val[belong[e[i].v]]) { val[belong[e[i].v]] = e[i].w; p[belong[e[i].v]] = e[i].v; } else if (e[i].v == 1 && e[i].w < val[belong[e[i].u]]) { val[belong[e[i].u]] = e[i].w; p[belong[e[i].u]] = e[i].u; } } for (i = 1; i <= block; i++) { ans += val[i]; mst[1][p[i]] = val[i]; mst[p[i]][1] = val[i]; } for (i = 1; i <= k - block; i++) { mx = 0; ps = new_e = make_pair(0,0); for (j = 1; j <= n; j++) { if (e[j].u == 1 && !mst[1][e[j].v]) { tmp = bfs(e[j].v); if (mst[tmp.first][tmp.second] - e[j].w > mx) { ps = tmp; new_e = make_pair(e[j].v,e[j].w); mx = mst[tmp.first][tmp.second] - e[j].w; } } if (e[j].v == 1 && !mst[1][e[j].u]) { tmp = bfs(e[j].u); if (mst[tmp.first][tmp.second] - e[j].w > mx) { ps = tmp; new_e = make_pair(e[j].u,e[j].w); mx = mst[tmp.first][tmp.second] - e[j].w; } } } if (mx == 0) break; ans -= mx; mst[1][new_e.first] = new_e.second; mst[ps.first][ps.second] = 0; } printf("Total miles driven: %d ",ans); return 0; }