UVa 1151 (枚举 + MST) Buy or Build

时间：2022-10-15 00:08:11

题意：

平面上有n个点，现在要把它们全部连通起来。现在有q个套餐，如果购买了第i个套餐，则这个套餐中的点全部连通起来。也可以自己单独地建一条边，费用为两点欧几里得距离的平方。求使所有点连通的最小费用。

分析：

很明显，如果没有这些套餐的话，就是一个裸的MST。

可以枚举套餐的组合情况，然后把套餐中的边的权值置为0，再求MST。

在求MST的过程中，并不需要把所有的边都加进来。只要把原图的MST的那些边和套餐中的边加进来即可。

因为，对于不在原图的MST的边，购买套餐以后，按照权值排序，排在它之前的边不会减少，反而会因为购买套餐而在前面多出来一些权值为0的边。所以原图中被“淘汰”的边，在购买套餐后也一定会被“淘汰”。

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxq = ;

 int n;

 int x[maxn], y[maxn], cost[maxq];

 vector<int> subn[maxq];

 int pa[maxn];

 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[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; }

 };

 int MST(int cnt, vector<Edge>& e, vector<Edge>& used)

 {

     if(cnt == ) return ;

     int m = e.size();

     int ans = ;

     used.clear();

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

     {

         int u = findset(e[i].u), v = findset(e[i].v);

         if(u != v)

         {

             pa[u] = v;

             ans += e[i].d;

             used.push_back(e[i]);

             if(--cnt == ) break;

         }

     }

     return ans;

 }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int q;

         scanf("%d%d", &n, &q);

         for(int i = ; 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-); //代码中节点的编号是从0开始的

             }

         }

         for(int i = ; i < n; ++i) scanf("%d%d", &x[i], &y[i]);

         vector<Edge> e, need;

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

             for(int j = ; j < i; ++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 = ; i < n; ++i) pa[i] = i;

         sort(e.begin(), e.end());

         int ans = MST(n, e, need);

         for(int S = ; S < (<<q); ++S)

         {//枚举所有套餐的组合情况

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

             int cnt = n, c = ;

             for(int i = ; i < q; ++i) if(S & (<<i))

             {

                 c += cost[i];

                 for(int j = ; j < subn[i].size(); ++j)

                 {

                     int u = findset(subn[i][j]), v = findset(subn[i][]);

                     if(u != v) { --cnt; pa[u] = v; }

                 }

             }

             vector<Edge> hehe;  //这里只是为了调用函数，所以弄了一个无关紧要的参数

             ans = min(ans, c + MST(cnt, need, hehe));

         }

         printf("%d\n", ans);

         if(T) printf("\n");

     }

     return ;

 }

代码君

相关文章