The plan of city rebuild
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 583 Accepted Submission(s): 201
Problem Description
News comes!~City W will be rebuilt with the expectation to become a center city. There are some villages and roads in the city now, however. In order to make the city better, some new villages should be built and some old ones should be destroyed. Then the officers have to make a new plan, now you , as the designer, have the task to judge if the plan is practical, which means there are roads(direct or indirect) between every two villages(of course the village has not be destroyed), if the plan is available, please output the minimum cost, or output"what a pity!".
Input
Input contains an integer T in the first line, which means there are T cases, and then T lines follow.
Each case contains three parts. The first part contains two integers l(0<l<100), e1, representing the original number of villages and roads between villages(the range of village is from 0 to l-1), then follows e1 lines, each line contains three integers a, b, c (0<=a, b<l, 0<=c<=1000), a, b indicating the village numbers and c indicating the road cost of village a and village b . The second part first contains an integer n(0<n<100), e2, representing the number of new villages and roads(the range of village is from l to l+n-1), then follows e2 lines, each line contains three integers x, y, z (0<=x, y<l+n, 0<=z<=1000), x, y indicating the village numbers and z indicating the road cost of village x and village y. The third part contains an integer m(0<m<l+n), representing the number of deserted villages, next line comes m integers, p1,p2,…,pm,(0<=p1,p2,…,pm<l+n) indicating the village number.
Pay attention: if one village is deserted, the roads connected are deserted, too.
Output
For each test case, If all villages can connect with each other(direct or indirect), output the minimum cost, or output "what a pity!".
Sample Input
2
4 5
0 1 10
0 2 20
2 3 40
1 3 10
1 2 70
1 1
4 1 60
2
2 3
3 3
0 1 20
2 1 40
2 0 70
2 3
0 3 10
1 4 90
2 4 100
0
Sample Output
70
160
組隊練習賽的一道最小生成樹題目，看到這就一口氣寫了，不過短了點路，耽誤了些時間。 可以理解為題目分兩次將邊的信息給出，中間再刪去幾個點（即有該點的邊不予考慮）。然後模版最小生成樹。
[cpp]
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 2000005
#define INF 0x7FFFFFFF
# define eps 1e-5
using namespace std;
int par[MAX],n,m,maxedge,cnt,del,A,B;//del要刪去的點，A,B為新加的點和邊
int index[2005];
struct Edge
{
int s,e;
int del;//該邊是否考慮
int value;
}edge[MAX];
bool cmp(Edge a, Edge b)
{
return a.value < b.value;
}
int find(int x)//查
{
while(par[x] != x)
x = par[x];
return x;
}
void connect(int a,int b)//並
{
if(a < b)
{
par[b] = a;
}
else
{
par[a] = b;
}
}
int kruskal()
{
int i;
maxedge = 0;
cnt = 0;
int sum = 0;
for(i=0; i<n+A; i++)
par[i] = i;
for(i=0; i<m+B; i++)
{
int a = find(edge[i].s);
int b = find(edge[i].e);
if(a != b && edge[i].del == 0)
{
connect(a,b);
cnt ++;
sum += edge[i].value;
}
}
if(cnt == n + A - 1 - del)//有總點數-1條邊，則成功
return sum;
else
return -1;
}
int main()
{
int i,t,p;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(index,0,sizeof(index));
for(i=0; i<m; i++)
{
scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].value);
edge[i].del = 0;
}
scanf("%d%d",&A,&B);
for(i=m; i<m+B; i++)//一開始寫成i = 0；i<B; ...傷了很久
{
scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].value);
edge[i].del = 0;
}
scanf("%d",&del);
for(i=0; i<del; i++)
{
scanf("%d",&p);
index[p]++;//記錄要刪的點
}
for(i=0; i<m+B; i++)
{
if(index[edge[i].s] != 0 || index[edge[i].e] != 0 )//該邊有點要刪，邊作廢
{
edge[i].del = 1; www.2cto.com
}
}
sort(edge,edge+m+B,cmp);
int ans = kruskal();
if(ans == -1)
printf("what a pity!\n");
else
printf("%d\n",ans);
}
return 0;
}
