Constructing Roads Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 18744 Accepted: 7755
Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.Sample Input
3 0 990 692 990 0 179 692 179 0 1 1 2
#includeusing namespace std; int a[101][101],n,father[101],m,x,y; int get_father(int p){ return father[p]=(father[p]==p? p:get_father(father[p])); } int main(){ cin>>n; for(int i=0;i >a[i][j]; for(int i=0;i >m; for(int i=0;i >x>>y; father[get_father(x-1)]=get_father(y-1); } int sum=0; for(int k=1;k<=1000;k++) for(int i=0;i