本文共 2299 字，大约阅读时间需要 7 分钟。
题目就是给出一些英文名称， 并且要求源点为park的入度不能超过k
#include #include #include #include #include using namespace std;const int N = 150;const int oo = 0x3f3f3f;#define FILL(a, b) memset(a, b, sizeof(a))#define rep(i, s, t) for(int i = s; i <= t; ++i)map id;int insert(string s) { if(!id.count(s)) id[s] = id.size(); return id[s];}struct Edge { int u, v, w;}p[N];struct Part_Prim { int G[N][N], n, m, limit, fa[N]; int dis[N], vis[N], cnt, used[N][N]; void init() { id.clear(); id["Park"] = 1; cnt = 0; rep(i, 1, N-1) rep(j, 1, N-1) G[i][j] = oo; FILL(vis, 0), FILL(used, 0), FILL(p, 0); } int prim(int s, int ret = 0, int add = oo) { int to_root = 0; ++cnt; rep(i, 0, n) dis[i] = oo; dis[s] = 0; rep(i, 1, n-1) { int k = 0; rep(j, 2, n) if(dis[k] > dis[j] && !vis[j]) k = j; if(!k) break; ret += dis[k]; vis[k] = cnt; if(add > G[k][1]) to_root = k, add = G[k][1]; rep(j, 2, n) if(G[k][j] < dis[j] && !vis[j]) dis[j] = G[k][j], fa[j] = k; if(fa[k]) used[k][fa[k]] = used[fa[k]][k] = 1; } used[1][to_root] = used[to_root][1] = 1; return ret + add; } void dfs(int u, int f) { rep(v, 2, n) if(used[u][v] && v ^ f) { p[v] = p[u]; if(G[u][v] ^ oo && G[u][v] > p[v].w) p[v] = (Edge) {u, v, G[u][v]}; dfs(v, u); } } int parking(int ret = 0, int t = 0) { rep(i, 2, n) if(!vis[i]) ret += prim(i);// cout << ret << endl; while(cnt++ < limit) { dfs(1, 0); rep(i, 2, n) if(G[1][i] ^ oo && !used[1][i] && p[i].w-G[1][i] > p[t].w-G[1][t]) t = i; ret -= p[t].w-G[1][t]; // cout << p[t].w << "!" << endl; used[1][t] = used[t][1] = 1; used[p[t].u][p[t].v] = used[p[t].v][p[t].u] = 0; } return ret; } void solve(int _ = 0) { while(~scanf("%d", &_)) { init(); while(_--) { string s1, s2; int w, u, v; cin >> s1 >> s2 >> w; u = insert(s1), v = insert(s2); G[u][v] = G[v][u] = w; } n = id.size(); scanf("%d", &limit); printf("Total miles driven: %d\n", parking()); } }}WORK;int main() {#ifndef ONLINE_JUDGE freopen("IP.in", "r", stdin); freopen("OP.out", "w", stdout);#endif WORK.solve(); return 0;}
转载于:https://www.cnblogs.com/pbvrvnq/p/8530156.html