【図論・練習問題】最小生成木:Buy or Build
25069 ワード
Problem
World Wide Networks (WWN) is a leading company that operates large telecommunication networks. WWN would like to setup a new network in Borduria, a nice country that recently managed to get rid of its military dictator Kurvi-Tasch and which is now seeking for investments of international companies (for a complete description of Borduria, have a look to the following Tintin albums\King Ottokar’s Sceptre",\The Calculus Affair"and\Tintin and the Picaros"). You are requested to help WWN todecide how to setup its network for a minimal total cost. There are several local companies running small networks (called subnetworks in the following) that partially cover the n largest cities of Borduria. WWN would like to setup a network that connects all n cities. To achieve this, it can either build edges between cities from scratch or it can buy one or several subnetworks from local companies. You are requested to help WWN to decide how to setup its network for a minimal total cost. • All n cities are located by their two-dimensional Cartesian coordinates. • There are q existing subnetworks. If q 1 then each subnetwork c (1 c q) is de ned by a set of interconnected cities (the exact shape of a subnetwork is not relevant to our problem). • A subnetwork c can be bought for a total cost wc and it cannot be split (i.e., the network cannot be fractioned). • To connect two cities that are not connected through the subnetworks bought, WWN has to build an edge whose cost is exactly the square of the Euclidean distance between the cities. You have to decide which existing networks you buy and which edges you setup so that the total cost is minimal. Note that the number of existing networks is always very small (typically smaller than 8).
日语原文:平面にはn個の点があります.あなたの任務はすべてのn個の点を連通させることです.そのため、いくつかの辺を新築することができます.費用は2つの端点のユークリッド距離の平方に等しいです.またq個のコースもあり、購入できますが、i個目のコースを購入すると、このコースのすべてのノードが相互に接続され、i個目のコースの費用はciになります.最小費用を求める.1 ≤ n ≤ 1000 ; 0 ≤ q ≤ 8 . 1≤n≤1000; 0≤q≤8. 1≤n≤1000;0≤q≤8.
Solution
まず知識点を補足すると,任意の2点(a,b),(c,d)のユークリッド距離は,d i s＝(a−c)2＋(b−d)2 dis＝(a−c)^2＋(b−d)^2 dis＝(a−c)2＋(b−d)2である.
コースを買わなければ、テーマは簡単だと信じています.これらの点を直接つなぎ、ユークリッド距離で、最小生成木を走ればいいと思います.
コースを購入する場合、具体的にどのコースを購入する必要があるか分かりません.このとき,データを観察すると,qの取値範囲は小さく,直接素朴な列挙は各選択情をタイムアウトさせない.複雑度O(2 q)O(2^q)O(2 q)
各列挙では、次の操作が必要です.
そして操作後,最小生成木MSTのことである.
各ケースを列挙するには、dfsではなくバイナリ状態で列挙を圧縮する必要があります.そうしないと、タイムアウトのリスクがあります.
#include
",a);
#define Mp make_pair
#define Mem(a,b) memset(a,b,sizeof(a))
#define dis(a,b) ((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))
#define father for(int i=0;i<=n;++i)fa[i]=i
using namespace std;
int n,q,h;
int temp;
int tot=0;
int Count=0;
int x[3000];
int y[3000];
int fa[3000];
int cost[3000];
struct edge
{
int u;
int v;
int val;
};
edge a[2000 * 2000];
vector<int>c[3000];
int get(int x)
{
if (fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
int Kruscal(void)
{
int sum=0,cnt=0;
for (int i=1;i<=tot;++i)
{
int fu=get(a[i].u);
int fv=get(a[i].v);
int val=a[i].val;
if (fu==fv) continue;
sum+=val;
fa[fu]=fv;
if (++cnt==n-1) break;
}
return sum;
}
//
inline bool cmp(edge p1,edge p2) {
return p1.val<p2.val;
}
void work(void)
{
Mem(x,0);
Mem(y,0);
Mem(cost,0);
Sc2(n,q);
for (int i=0;i<3000;++i)
c[i].clear();
for (int i=0;i<q;++i)
{
int m;
Sc2(m,cost[i]);
for (int j=1;j<=m;++j)
{
Sc(temp);
c[i].push_back(temp);
}
}
for (int i=1;i<=n;++i) Sc2(x[i],y[i]);
//input
tot=0;
for (int i=1;i<=n;++i)
for (int j=i+1;j<=n;++j)
a[++tot]=edge{i,j,dis(i,j)};
sort(a+1,a+tot+1,cmp);
father;
int ans=Kruscal();
for (int i=0;i<(1<<q);++i)
//
{
father;
int spend=0;
for (int j=0;j<q;++j)
//
{
if (((i>>j)&1)==0) continue;
// j 0
spend+=cost[j];
//
for (int k=1;k<c[j].size();++k)
{
int point1=get(c[j][0]);
int point2=get(c[j][k]);
fa[point1]=point2;
}
// &
}
ans=min(ans,spend+Kruscal());
}
printf("%d",ans);
}
int main(void)
{
int T;
h=T;
Sc(T);
while (T--)
{
work();
if (T) printf("
");
else printf("
");
}
return 0;
}
主な考え方は、データを観察し、列挙し、ツリー計算を生成することです.
しかし、この問題の最も主要な難点はコード量が大きいことです.