UVa 1151 - Buy or Build（最小生成树）

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3592

题意：

平面上有n个点（1≤n≤1000），你的任务是让所有n个点连通。
为此，你可以新建一些边，费用等于两个端点的欧几里德距离的平方。
另外还有q（0≤q≤8）个“套餐”可以购买，如果你购买了第i个套餐，该套餐中的所有结点将变得相互连通。
第i个套餐的花费为Ci。求最小的花费。

分析：

最容易想到的算法是：先枚举购买哪些套餐，把套餐中包含的边的权值设为0，然后求最小生成树。
由于枚举量为O(2^q)，给边排序的时间复杂度为O(n*nlogn)，而排序之后每次Kruskal算法的时间复杂度为O(n*n)，
因此总时间复杂度为O((2^q)*(n*n)+n*nlogn)，对于题目的规模来说太大了。
只需一个小小的优化即可降低时间复杂度：先求一次原图（不购买任何套餐）的最小生成树，
得到n-1条边，然后每次枚举完套餐后只考虑套餐中的边和这n-1条边，
则枚举套餐之后再求最小生成树时，图上的边已经寥寥无几。
为什么可以这样呢？首先回顾一下，在Kruskal算法中，哪些边不会进入最小生成树。
答案是：两端已经属于同一个连通分量的边。买了套餐以后，相当于一些边的权变为0，
而对于不在套餐中的每条边e，排序在e之前的边一个都没少，反而可能多了一些权值为0的边，
所以在原图Kruskal时被“扔掉”的边，在后面的Kruskal中也一样会被扔掉。

代码：

 import java.io.*;

 import java.util.*;

 import static java.lang.Math.*;

 public class Main {

     Scanner cin = new Scanner(new BufferedInputStream(System.in));

     final int UP = 1000 + 5;

     int pre[] = new int[UP];

     int x[] = new int[UP], y[] = new int[UP], cost[] = new int[UP];

     class Edge implements Comparable<Edge> {

         int f, b, v;

         @Override

         public int compareTo(Edge that) {

             return v - that.v;

         }

     }

     int seek(int v) {

         return pre[v] == v ? v : (pre[v] = seek(pre[v]));

     }

     int MST(int n, ArrayList<Edge> e, ArrayList<Edge> res) {

         if(n <= 1) return 0;

         int m = e.size(), ans = 0;

         for(int i = 0; i < m; i++) {

             int pf = seek(e.get(i).f), pb = seek(e.get(i).b);

             if(pf == pb) continue;

             pre[pf] = pre[pb];

             ans += e.get(i).v;

             if(res != null) res.add(e.get(i));

             if(--n == 1) break;

         }

         return ans;

     }

     void MAIN() {

         int T;

         T = cin.nextInt();

         while(T --> 0) {

             @SuppressWarnings("unchecked")

             ArrayList<Integer> subn[] = new ArrayList[8];

             for(int i = 0; i < 8; i++) subn[i] = new ArrayList<Integer>();

             int n = cin.nextInt();

             int q = cin.nextInt();

             for(int m, i = 0; i < q; i++) {

                 m = cin.nextInt();

                 cost[i] = cin.nextInt();

                 for(int t = 0; t < m; t++) subn[i].add(cin.nextInt()-1);

             }

             for(int i = 0; i < n; i++) {

                 x[i] = cin.nextInt();

                 y[i] = cin.nextInt();

             }

             ArrayList<Edge> edge = new ArrayList<Edge>();

             for(int i = 0; i < n; i++) {

                 for(int t = i+1; t < n; t++) {

                     Edge e = new Edge();

                     e.f = i;  e.b = t;

                     e.v = (x[i]-x[t])*(x[i]-x[t]) + (y[i]-y[t])*(y[i]-y[t]);

                     edge.add(e);

                 }

             }

             ArrayList<Edge> used = new ArrayList<Edge>();

             for(int i = 0; i < n; i++) pre[i] = i;

             Collections.sort(edge);

             int ans = MST(n, edge, used);

             for(int s = 1; s < (1<<q); s++) {

                 for(int i = 0; i < n; i++) pre[i] = i; // 初始化并查集

                 int remain = n, c = 0;

                 for(int i = 0; i < q; i++) if((s&(1<<i)) > 0) {

                     c += cost[i];

                     for(int t = 1; t < subn[i].size(); t++) {

                         int pf = seek(subn[i].get(0)), pb = seek(subn[i].get(t));

                         if(pf == pb) continue;

                         pre[pf] = pb;

                         remain--;

                     }

                 }

                 ans = min(ans, c + MST(remain, used, null));

             }

             System.out.println(ans);

             if(T > 0) System.out.println();

         }

     }

     public static void main(String args[]) { new Main().MAIN(); }

 }

巴特西

UVa 1151 - Buy or Build（最小生成树）

最新文章

热门文章