首页 > 代码库 > UVA1151
UVA1151
//感觉刘汝佳老师的思维真的太厉害了orz/*摘录书上的一段话: 只需一个小小的优化即可降低时间复杂度:先求一次原图(不购买任何套餐)的最小生成树,得到n-1条边,然后每次枚举完套餐后只考虑套餐中的边和这n-1条边,则枚举套餐之后再求最小生成树时,图上的边已经寥寥无几。为什么可以这样呢?首先回顾一下,在Kruskal算法中,哪些边不会进入最小生成树。答案是:两端已经属于同一个连通分量的边。买了套餐以后,相当于一些边的权变为0,而对于不在套餐中的每条边e,排序在e之前的边一个都没少,反而可能多了一些权值为0的边,所以在原图Kruskal时被“扔掉”的边,在后面的Kruskal中也一样会被扔掉。*/// UVa1151 Buy or Build// Rujia Liu#include<cstdio>#include<cmath>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int maxn = 1000 + 10;const int maxq = 8;int n;int x[maxn], y[maxn], cost[maxq];vector<int> subn[maxq];int pa[maxn];int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } struct Edge { int u, v, d; Edge(int u, int v, int d):u(u),v(v),d(d) {} bool operator < (const Edge& rhs) const { return d < rhs.d; }};// initialize pa and sort e before calling this method// cnt is the current number of componentsint MST(int cnt, const vector<Edge>& e, vector<Edge>& used) { //找出原图跑一边kruskal之后用过的边 if(cnt == 1) return 0; int m = e.size(); int ans = 0; used.clear(); for(int i = 0; i < m; i++) { int u = findset(e[i].u), v = findset(e[i].v); int d = e[i].d; if(u != v) { pa[u] = v; ans += d; used.push_back(e[i]); if(--cnt == 1) break; } } return ans;}int main() { int T, q; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &q); for(int i = 0; i < q; i++) { int cnt; scanf("%d%d", &cnt, &cost[i]); subn[i].clear(); while(cnt--) { int u; scanf("%d", &u); subn[i].push_back(u-1); } } for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]); vector<Edge> e, need; for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) { int c = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]); e.push_back(Edge(i, j, c)); } for(int i = 0; i < n; i++) pa[i] = i; sort(e.begin(), e.end()); int ans = MST(n, e, need); for(int mask = 0; mask < (1<<q); mask++) { //枚举套餐,二进制法 // union cities in the same sub-network for(int i = 0; i < n; i++) pa[i] = i; int cnt = n, c = 0; for(int i = 0; i < q; i++) if(mask & (1<<i)) { c += cost[i]; for(int j = 1; j < subn[i].size(); j++) { int u = findset(subn[i][j]), v = findset(subn[i][0]); if(u != v) { pa[u] = v; cnt--; } } } vector<Edge> dummy; ans = min(ans, c + MST(cnt, need, dummy)); } printf("%d\n", ans); if(T) printf("\n"); } return 0;}
UVA1151
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。