2014
03-16

# Connect the Cities

In 2100, since the sea level rise, most of the cities disappear. Though some survived cities are still connected with others, but most of them become disconnected. The government wants to build some roads to connect all of these cities again, but they don’t want to take too much money.

The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

1
6 4 3
1 4 2
2 6 1
2 3 5
3 4 33
2 1 2
2 1 3
3 4 5 6

1

HDU_STEPS 6.1 最小生成树

6.1.1 HDU 1102 Constructing Roads 裸的最小生成树

6.1.2 HDU 1162 Eddy’s picture 最小生成树,每两点直接连线建图

6.1.3 HDU 1232 畅通工程 用并查集将图分块,然后修N-1条路即可

6.1.4 HDU 1233 还是畅通工程 还是最小生成树

6.1.5 HDU 1879 继续畅通工程 在已生成部分图的情况下生成最小生成树,输入的时候用并查集合并已经连接的端点

6.1.6 HDU 1301 Jungle Roads 将字母转换成数字建图即可,还是最小生成树

6.1.7 HDU 3371 Connect the Cities

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
struct edge{
int u,v,w;
bool operator <(const edge& ee)const{return w<ee.w;}
}e[25005];
int p[505],cas,n,m,k,hash[505];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&n,&m,&k);

for(int i=1;i<=n;i++)p[i]=i;
memset(hash,0,sizeof hash);

for(int i=0;i<m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i=0;i<k;i++){
int t,st,en;
scanf("%d%d",&t,&st);t--;
while(t--){
scanf("%d",&en);
p[find(st)]=find(en);
}
}
int tot=0,cnt=0;
for(int i=1;i<=n;i++)
if(!hash[find(i)])tot++,hash[find(i)]=1;
tot--;//需要增加的边的条数

sort(e,e+m);

int res=0;
for(int i=0;i<m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x==y)continue;
res+=e[i].w;
p[x]=y;
cnt++;
if(cnt==tot)break;//已经连通了
}

if(cnt<tot)printf("-1\n");
else printf("%d\n",res);
}
}

6.1.8 HDU 3367 Pseudoforest

#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 10001
using namespace std;
struct edge{
int u,v,w,us;
edge(){};
edge(int a,int b,int c){u=a,v=b,w=c,us=0;}
bool operator<(const edge& e)const{return w>e.w;}
}e[MAXN*10];
int p[MAXN],n,m,cir[MAXN];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int main(){
while(scanf("%d%d",&n,&m),n||m){
for(int i=0;i<n;i++)p[i]=i;
memset(cir,0,sizeof cir);

for(int i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

sort(e,e+m);
int res=0;
for(int i=0;i<m;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x==y&&cir[x]==0){//如果两点在同一个块且无环
cir[x]=1;
res+=e[i].w;
}
if(cir[x]&&cir[y])continue;//如果都有环就不能连了
if(cir[x])p[y]=x;//如果x有环,将y并入x中
else p[x]=y;	//否则将x并入y中
res+=e[i].w;
}

printf("%d\n",res);
}
}