uva 11228 - Transportation system

J. Transportation system

Time limit: 2s

In the country of Graphland, there are many cities but no roads. The federal government wants to change this situation and plans to build roads and railroads such that all the cities in the country are connected through this new transportation system. To make the new system more efficient, Graphland will build only roads between cities within the same state and will use railroads to connect cities that are in different states. For the purposes of this problem, consider that if the distance between any two cities is at most $r$ then they are in the same state. To minimize the costs of building the roads and railroads, the government also wants to build only the minimum necessary extension of roads and railroads such that there is a path between any pair of cities in the entire country. You've been hired to determine what's the optimum transportation network system that Graphland must build.
The first line of the input contains the number of test cases that follow. On the first line of each test case, there will be two integers, $n$ ($1\; \le \; n\; \le \; 1000$), the number of cities that comprise Graphland, and $r$ ($0\; \le \; r\; \le \; 40000$), the threshold value to determine if two cities are in the same state. On the following $n$ lines, there will be a list of $x-y$ ($-10000\; \le \; x,\; y\; \le \; 10000$) integer coordinates in the plan for each city in Graphland. Your program must output the number of states in Graphland and the minimum extension (rounded to the nearest integer) of both roads and railroads that must be built to satisfy the conditions of the project.

Input

The first line of input gives the number of cases, $T$ ($1\; \le \; T\; \le \; 20$). $T$ test cases follow. On the first line of each test case, there will be two integers, $n$ ($1\; \le \; n\; \le \; 1000$), the number of cities that comprise Graphland, and $r$ ($0\; \le \; r\; \le \; 40000$), the threshold value to determine if two cities are in the same state. On the following $n$ lines, there will be a list of $x-y$ ($-10000\; \le \; x,\; y\; \le \; 10000$) integer coordinates in the plan for each city in Graphland.

Output

The output is comprised of one line for each input data set. The line identifies the data set with a number (starting from one and incrementing at each new data set), followed by the number of states in Graphland and the minimum extension (rounded to the nearest integer) of both roads and railroads that must be built to satisfy the conditions of the project.

Sample input

3
3 100
0 0
1 0
2 0
3 1
0 0
100 0
200 0
4 20
0 0
40 30
30 30
10 10

Sample output

Case #1: 1 2 0
Case #2: 3 0 200
Case #3: 2 24 28

---

Problem setter: Herbert de Melo Duarte.
Universidade Federal do Rio Grande do Norte Qualifying Contest IV, June 9th, 2007.

minimum spanning tree - Kruskal

#include<stdio.h>
#include<cstring>
#include<queue>
#include<cmath>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
#define MAXN 1000
using namespace std;

int N,cases=1,C,R;
int cor[MAXN][2],p[MAXN];
double dis[MAXN][MAXN];
bool isp[MAXN];
vector<int>group[MAXN],sn;
struct Node{
    Node(double a,int b,int c):dis(a),v1(b),v2(c){}
    bool operator <(const Node b)const {return dis>b.dis;}
    int v1,v2;
    double dis;
};
int find(int v){
    if(p[v]==v)return v;
    return p[v]=find(p[v]);
}
void unit(int from,int to){
    p[find(from)]=p[find(to)];
}
double getD(int a,int b){
    return sqrt(pow(double(cor[a][0]-cor[b][0]),2)+pow(double(cor[a][1]-cor[b][1]),2));
}
void getSts(){
    sn.clear();rep(i,N)group[i].clear();memset(isp,0,sizeof(isp));
    rep(i,N)p[i]=i;
    rep(i,N)REP(j,i+1,N){
        dis[i][j]=dis[j][i]=getD(i,j);
        if(find(i)!=find(j)&&dis[i][j]<R)unit(i,j),C--;
    }
    int a;
    rep(i,N){
        a=find(i);
        group[a].push_back(i);
        if(!isp[a])isp[a]=1,sn.push_back(a);
    }
}
void add(int a,int b,double &c){
    c=1e300;
    rep(i,group[a].size())
        rep(j,group[b].size())
            if(c>dis[group[a][i]][group[b][j]])
                c=dis[group[a][i]][group[b][j]];
}
void ans(){
    int a,b,c;
    C=N,getSts();
    if(DBG)printf("state: %d\n",C);
    priority_queue<Node>q2;
    double d,s1=0,s2=0;
    int cnt;
    rep(i,N)p[i]=i;
    rep(k,N){       //same state
        if(group[k].size()){
            cnt=0;
            priority_queue<Node>q;
            rep(i,group[k].size())REP(j,i+1,group[k].size()){
                a=group[k][i],b=group[k][j],cnt++;
                if(DBG&&!cnt%100)printf("push %d %d: %f\n",a,b,dis[a][b]);
                q.push(Node(dis[a][b],a,b));
            }
            if(DBG)printf("done: size %d\n",group[k].size());
            c=0;
            while(c<group[k].size()-1){
                a=q.top().v1,b=q.top().v2,d=q.top().dis,q.pop();
                //if(DBG)printf("edge %d %d: %f\n",a,b,dis);
                if(find(a)!=find(b)){
                    unit(a,b),s1+=d,c++;
                    if(DBG)printf("c %d\n",c);}
            }
        }
    }
    rep(i,N)p[i]=i;
    if(DBG)printf("dis: %f\n",s1);
    rep(i,sn.size())REP(j,i+1,sn.size()){           //diff state
        add(sn[i],sn[j],d);
        q2.push(Node(d,i,j));
    }
    c=0;
    while(c<C-1){
        a=q2.top().v1,b=q2.top().v2,d=q2.top().dis,q2.pop();
        if(DBG)printf("set %d %d: %f\n",a,b,dis);
        if(find(a)!=find(b))unit(a,b),s2+=d,c++;
    }
    printf("Case #%d: %d %d %d\n",cases++,C,int(s1+0.5),int(s2+0.5));
}
int main(){
   int n;
   scanf("%d",&n);
   rep(i,n){
        scanf("%d%d",&N,&R);
        rep(i,N)scanf("%d%d",&cor[i][0],&cor[i][1]);
        ans();
    }
   return 0;
}