Connect the Cities
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7269 Accepted Submission(s): 2076
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.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int father[100000],n,m,k,sum,rank[100000];
struct edg
{
int start,end,money;
} e[100000];
bool cmp(edg a,edg b)
{
return a.money<b.money;
}
void makeset(int x)
{
int i;
for(i=1; i<=x; i++)
{
father[i]=i;
rank[i]=1;
}
}
int find(int x)
{
return x==father[x]?x:father[x]=find(father[x]);
}
void uon(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
{
if(rank[x]>=rank[y])
{
father[y]=x;
rank[x]+=rank[y];
rank[y]=0;
}
else
{
father[x]=y;
rank[y]+=rank[x];
rank[x]=0;
}
}
}
int main()
{
int N,i,t,a[100000],j,len;
scanf("%d",&N);
while(N--)
{
scanf("%d%d%d",&n,&m,&k);
makeset(n);
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&e[i].start,&e[i].end,&e[i].money);
}
for(i=1; i<=k; i++)
{
scanf("%d",&t);
scanf("%d",&a[1]);
for(j=2; j<=t; j++)
{
scanf("%d",&a[j]);
uon(a[j-1],a[j]);
}
}
sort(e+1,e+m+1,cmp);
sum=len=0;
for(i=1; i<=m; i++)
{
if(find(e[i].start)!=find(e[i].end))
{
uon(e[i].start,e[i].end);
sum+=e[i].money;
}
}
for(i=1; i<=n; i++)
{
if(rank[i]>0)
len++;
}
if(len==1)
printf("%d
",sum);
else
printf("-1
");
}
}
方法二:prime算法
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#define N 503
using namespace std;
int map[N][N];
bool visit[N];
int n;
void prim()
{
memset(visit,0,sizeof(visit));
visit[1]=1;
int i,j,t=n,min,sum=0;
while(--t)
{
min=1000;
for(i=2; i<=n; i++)
if(!visit[i]&&map[1][i]<min)
min=map[1][i],j=i;
if(min==1000)
break;
visit[j]=1;
sum+=min;
for(i=2; i<=n; i++)
if(!visit[i]&&map[1][i]>map[j][i])
map[1][i]=map[j][i];
}
if(min==1000)
printf("-1
");
else
printf("%d
",sum);
}
int main()
{
int m,l,k,t,T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&l);
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
map[i][j]=1000;
while(m--)
{
scanf("%d%d%d",&i,&j,&k);
map[i][j]=map[i][j]>k?k:map[i][j];
map[j][i]=map[i][j];
}
while(l--)
{
scanf("%d%d",&t,&i);
while(--t)
{
scanf("%d",&j);
map[i][j]=map[j][i]=0;
i=j;
}
}
prim();
}
return 0;
}