.glyphicon:before{
font-family:'Glyphicons Halflings';
font-style:normal;
font-weight:400;
line-height:1;
vertical-align:-11%;
letter-spacing:2px;
-webkit-font-smoothing:antialiased
}
2012年10月19日 星期五
uva 10801 - Lift Hopping
Lift Hopping
Time Limit: 1 second
| Ted the bellhop: "I'm coming up and if there isn't a dead body by the time I get there, I'll make one myself. You!" |
A skyscraper has no more than 100 floors, numbered from 0 to 99. It has n (1<=n<=5) elevators which travel up and down at (possibly) different speeds. For each i in {1, 2,... n}, elevator number i takes Ti (1<=Ti<=100) seconds to travel between any two adjacent floors (going up or down). Elevators do not necessarily stop at every floor. What's worse, not every floor is necessarily accessible by an elevator.
You are on floor 0 and would like to get to floor k as quickly as possible. Assume that you do not need to wait to board the first elevator you step into and (for simplicity) the operation of switching an elevator on some floor always takes exactly a minute. Of course, both elevators have to stop at that floor. You are forbiden from using the staircase. No one else is in the elevator with you, so you don't have to stop if you don't want to. Calculate the minimum number of seconds required to get from floor 0 to floor k (passing floor k while inside an elevator that does not stop there does not count as "getting to floork").
Input
The input will consist of a number of test cases. Each test case will begin with two numbers, n and k, on a line. The next line will contain the numbers T1, T2,... Tn. Finally, the next n lines will contain sorted lists of integers - the first line will list the floors visited by elevator number 1, the next one will list the floors visited by elevator number 2, etc.
The input will consist of a number of test cases. Each test case will begin with two numbers, n and k, on a line. The next line will contain the numbers T1, T2,... Tn. Finally, the next n lines will contain sorted lists of integers - the first line will list the floors visited by elevator number 1, the next one will list the floors visited by elevator number 2, etc.
Output
For each test case, output one number on a line by itself - the minimum number of seconds required to get to floor k from floor 0. If it is impossible to do, print "IMPOSSIBLE" instead.| Sample Input | Sample Output |
2 30 10 5 0 1 3 5 7 9 11 13 15 20 99 4 13 15 19 20 25 30 2 30 10 1 0 5 10 12 14 20 25 30 2 4 6 8 10 12 14 22 25 28 29 3 50 10 50 100 0 10 30 40 0 20 30 0 20 50 1 1 2 0 2 4 6 8 10 | 275 285 3920 IMPOSSIBLE |
Explanation of examples
In the first example, take elevator 1 to floor 13 (130 seconds), wait 60 seconds to switch to elevator 2 and ride it to floor 30 (85 seconds) for a total of 275 seconds.In the second example, take elevator 1 to floor 10, switch to elevator 2 and ride it until floor 25. There, switch back to elevator 1 and get off at the 30'th floor. The total time is
10*10 + 60 + 15*1 + 60 + 5*10 = 285 seconds.
In example 3, take elevator 1 to floor 30, then elevator 2 to floor 20 and then elevator 3 to floor 50.
In the last example, the one elevator does not stop at floor 1.
Problemsetter: Igor Naverniouk
Alternate solutions: Stefan Pochmann, Frank Pok Man Chu
shortest path - bfs
#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<sstream>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define MAXN 5
#define MAXF 100
#define DBG 0
using namespace std;
int N,M,next[MAXN][MAXF],pre[MAXN][MAXF],spd[MAXN];
bool dps[MAXN][MAXF],isc[MAXN][MAXF];
vector<int>eg[MAXF];
struct Node{
Node(int a,int b,int c):ele(a),flr(b),min(c){}
bool operator < (const Node b)const{return min>b.min;}
int ele,flr,min;
};
void ans(){
int a,b,c,na,nb[2];
bool ok=0;
memset(dps,0,sizeof(dps));
priority_queue<Node>q;
rep(i,N)if(isc[i][0])dps[i][0]=1,q.push(Node(i,0,0));
while(q.size()){
a=q.top().ele,b=q.top().flr,c=q.top().min,q.pop();
if(DBG)printf("bfs %d %d %d\n",a,b,c);
if(b==M){ok=1;break;}
dps[a][b]=1;
nb[0]=next[a][b],nb[1]=pre[a][b]; //switch floor
rep(i,2)
if(nb[i]>0&&!dps[a][nb[i]]){
q.push(Node(a,nb[i],c+spd[a]*abs(nb[i]-b))); //original ele
}
rep(i,eg[b].size()){ //switch elevator
na=eg[b][i];
if(na!=a){
if(DBG)printf("switch flr: %d %d\n",na,c+60);
if(!dps[na][b])q.push(Node(na,b,c+60));}
}
}
if(ok)printf("%d\n",c);
else printf("IMPOSSIBLE\n");
}
int main(){
int a,b,c,pa;
char chs[400];
stringstream buf;
while(scanf("%d%d",&N,&M)==2){
if(DBG)printf("N M %d %d\n",N,M);
rep(i,MAXF)eg[i].clear();memset(isc,0,sizeof(isc));
memset(pre,0,sizeof(pre)),memset(next,0,sizeof(next));
rep(i,N)scanf("%d ",&spd[i]);
rep(i,N){
fgets(chs,400,stdin);pa=-1;
if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
buf.clear(),buf.str(chs);
while(!buf.eof()){
buf>>a;
if(pa>=0)pre[i][a]=pa,next[i][pa]=a;
eg[a].push_back(i);isc[i][a]=1;
pa=a;
}
}
ans();
}
return 0;
}
uva 11101 - Mall Mania
Problem B: Mall Mania
Waterloo has two giant shopping malls, each enclosing several city blocks. Kim and Pat like to shop and to walk within the malls but they don't like walking between the malls because such walking does not contribute directly to the task at hand: shopping. They would therefore like to know the minimum crossing distance between the malls.Each city block is a unit square delimited by streets and avenues. Streets run east-west and avenues run north-south. Both are identified by consecutive integers between 0 and 2000. (Lower numbered avenues are west of higher numbered avenues and lower numbered streets are south of higher numbered streets.) Streets and avenues are narrow so their thickness may be assumed to be 0.Each mall is a contiguous set of complete city blocks. By contiguous we mean that any two blocks are connected by some sequence of blocks such that consecutive pairs of blocks in the sequence share a side. The malls do not intersect and do not surround any empty blocks; that is, the blocks not in any mall are themselves contiguous.
Standard input contains several test cases. Each test case contains the description of the two malls. Each mall's description consists of an integer p ≥ 4, the perimeter of the mall, followed by one or more lines containing p pairs (a,s) giving the coordinates of the avenue-street intersections contained in the perimeter, in clockwise order. A line containing 0 follows the last test case.
For each case, output a single integer d -- the minimum walking distance between the malls, assuming that Kim and Pat always walk along streets and avenues.
Sample Input
4 0 0 0 1 1 1 1 0 6 4 3 4 2 3 2 2 2 2 3 3 3 0
Output for Sample Input
2
Gordon V. Cormack
shortest path - BFS
#include<stdio.h>
#include<cstring>
#include<vector>
#include<queue>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define MAXN 2001
#define DBG 0
using namespace std;
int N,M,cases=1,dir[4][2];
bool dps[MAXN][MAXN],m1[MAXN][MAXN],m2[MAXN][MAXN];
vector<pair<int,int> >seq;
struct Node{
Node(int a,int b,int c):x(a),y(b),dis(c){}
int x,y,dis;
};
void init(){
dir[0][0]=-1,dir[1][1]=-1,dir[2][0]=1,dir[3][1]=1;
}
bool valid(int a,int b){return a>=0&&a<2000&&b>=0&&b<2000;}
void ans(){
int x,y,a,b,d;
bool ok=0;
memset(dps,0,sizeof(dps));
queue<Node>q;
rep(i,seq.size())q.push(Node(seq[i].first,seq[i].second,0));
while(q.size()){
a=q.front().x,b=q.front().y,d=q.front().dis,q.pop();
if(DBG)printf("bfs %d %d\n",a,b);
dps[a][b]=1;
rep(i,4){
x=a+dir[i][0],y=b+dir[i][1];
if(valid(x,y)&&!m1[x][y]&&!dps[x][y]){ //don't walk in mall and previous pos
dps[x][y]=1;
if(m2[x][y]){if(DBG)printf("find %d %d\n",x,y);d++,ok=1;break;}
q.push(Node(x,y,d+1));
}
}
if(ok)break;
}
printf("%d\n",d);
}
int main(){
int a,b,c;
bool ll=0;
init();
while(scanf("%d",&N)==1){
memset(m1,0,sizeof(m1));memset(m2,0,sizeof(m2));
seq.clear();
if(N==0)break;
rep(i,N)scanf("%d%d",&a,&b),m1[a][b]=1,seq.push_back(make_pair(a,b));;
scanf("%d",&N);
rep(i,N)scanf("%d%d",&a,&b),m2[a][b]=1;
ans();
}
return 0;
}
uva 10047 - The Monocycle
Problem A: The Monocycle
A monocycle is a cycle that runs on one wheel and the one we will be considering is a bit more special. It has a solid wheel colored with five different colors as shown in the figure:| Problem A: The Monocycle |
grid of square tiles. The tiles have such size that moving forward from the center of one tile to that of the next one makes the wheel rotate exactly 72o around its own center. The effect is shown in the above figure. When the wheel is at the center of square 1, the midpoint of the periphery of its blue segment is in touch with the ground. But when the wheel moves forward to the center of the next square (square 2) the midpoint of its white segment touches the ground.
Before he starts his ride, please help him find out whether the destination is reachable and if so the minimum amount of time he will require to reach it.
Input
The input may contain multiple test cases.The first line of each test case contains two integers M and N (
, 
) giving the dimensions of the grid. Then follows the description of the grid in M lines of N characters each. The character `#' will indicate a blocked square, all other squares are free. The starting location of the cyclist is marked by `S' and the target is marked by `T'. The input terminates with two zeros for M and N.Output
For each test case in the input first print the test case number on a separate line as shown in the sample output. If the target location can be reached by the cyclist print the minimum amount of time (in seconds) required to reach it exactly in the format shown in the sample output, otherwise, print ``destination not reachable".Print a blank line between two successive test cases.
Sample Input
1 3 S#T 10 10 #S.......# #..#.##.## #.##.##.## .#....##.# ##.##..#.# #..#.##... #......##. ..##.##... #.###...#. #.....###T 0 0
Sample Output
Case #1 destination not reachable Case #2 minimum time = 49 sec
Miguel Revilla
2000-12-26
shortest path, BFS
#include<stdio.h>
#include<cstring>
#include<queue>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define MAXN 25
#define DBG 0
using namespace std;
int N,M,cases=1,dir[4][2];
char maz[MAXN][MAXN+1];
bool dps[MAXN][MAXN][4][5];
struct Node{
Node(int a,int b,int c,int d,int e):x(a),y(b),face(c),wheel(d),dis(e){}
int face,x,y,dis,wheel;
};
void init(){
dir[0][0]=-1,dir[1][1]=-1,dir[2][0]=1,dir[3][1]=1;
}
bool valid(int a,int b){return a>=0&&a<N&&b>=0&&b<M;}
void ans(){
int a,b,c,d,x,y,e,w,si,sj,ei,ej,nw,nd[2];
bool ok=0;
memset(dps,0,sizeof(dps));
rep(i,N)rep(j,M){
if(maz[i][j]=='S')si=i,sj=j;
if(maz[i][j]=='T')ei=i,ej=j;}
queue<Node>q;
q.push(Node(si,sj,0,0,0)); //face north, wheel zero
while(q.size()){
a=q.front().x,b=q.front().y,c=q.front().face,w=q.front().wheel,
d=q.front().dis,q.pop();
if(DBG)printf("bfs a b face wheel dis %d %d %d %d %d\n",a,b,c,w,d);
dps[a][b][c][w]=1;
if(a==ei&&b==ej&&w==0){ok=1;break;}
nd[0]=(c+1)%4,nd[1]=(c-1)<0?3:c-1;
rep(i,2) //direction
if(!dps[a][b][nd[i]][w]){
dps[a][b][nd[i]][w]=1;
q.push(Node(a,b,nd[i],w,d+1));}
x=a+dir[c][0],y=b+dir[c][1],nw=(w+1)%5; //walk
if(valid(x,y)&&maz[x][y]!='#'&&!dps[x][y][c][nw]){
dps[x][y][c][nw]=1;
q.push(Node(x,y,c,nw,d+1));}
}
printf("Case #%d\n",cases++);
if(ok)printf("minimum time = %d sec\n",d);
else printf("destination not reachable\n");
}
int main(){
int a,b,c;
bool ll=0;
init();
while(scanf("%d%d",&N,&M)==2){
if(DBG)printf("N M %d %d\n",N,M);
if(N+M==0)break;
rep(i,N)scanf("%s",maz[i]);
if(ll)printf("\n");ll=1;ans();
}
return 0;
}
uva 321 - The New Villa
The New Villa
Mr. Black recently bought a villa in the countryside. Only one thing bothers him: although there are light switches in most rooms, the lights they control are often in other rooms than the switches themselves. While his estate agent saw this as a feature, Mr. Black has come to believe that the electricians were a bit absent-minded (to put it mildly) when they connected the switches to the outlets.| The New Villa |
One night, Mr. Black came home late. While standing in the hallway, he noted that the lights in all other rooms were switched off. Unfortunately, Mr. Black was afraid of the dark, so he never dared to enter a room that had its lights out and would never switch off the lights of the room he was in.
After some thought, Mr. Black was able to use the incorrectly wired light switches to his advantage. He managed to get to his bedroom and to switch off all lights except for the one in the bedroom.
You are to write a program that, given a description of a villa, determines how to get from the hallway to the bedroom if only the hallway light is initially switched on. You may never enter a dark room, and after the last move, all lights except for the one in the bedroom must be switched off. If there are several paths to the bedroom, you have to find the one which uses the smallest number of steps, where ``move from one room to another'', ``switch on a light'' and ``switch off a light'' each count as one step.
Input
The input file contains several villa descriptions. Each villa starts with a line containing three integers r, d, and s. r is the number of rooms in the villa, which will be at most 10. d is the number of doors/connections between the rooms and s is the number of light switches in the villa. The rooms are numbered from 1 to r; room number 1 is the hallway, room number r is the bedroom.This line is followed by d lines containing two integers i and j each, specifying that room i is connected to room j by a door. Then follow s lines containing two integers k and l each, indicating that there is a light switch in room k that controls the light in room l.
A blank line separates the villa description from the next one. The input file ends with a villa having r = d = s = 0, which should not be processed.
Output
For each villa, first output the number of the test case (`Villa #1', `Villa #2', etc.) in a line of its own.If there is a solution to Mr. Black's problem, output the shortest possible sequence of steps that leads him to his bedroom and only leaves the bedroom light switched on. (Output only one shortest sequence if you find more than one.) Adhere to the output format shown in the sample below.
If there is no solution, output a line containing the statement `The problem cannot be solved.'
Output a blank line after each test case.
Sample Input
3 3 4 1 2 1 3 3 2 1 2 1 3 2 1 3 2 2 1 2 2 1 1 1 1 2 0 0 0
Sample Output
Villa #1 The problem can be solved in 6 steps: - Switch on light in room 2. - Switch on light in room 3. - Move to room 2. - Switch off light in room 1. - Move to room 3. - Switch off light in room 2. Villa #2 The problem cannot be solved.
shortest path + bitmask
#include<stdio.h>
#include<cstring>
#include<queue>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define MAXN 10
#define DBG 0
using namespace std;
int N,M,cases=1;
int pre[MAXN][1024][2],child[MAXN][1024][2];
bool on[MAXN],isc[MAXN][MAXN],dps[MAXN][1024];
vector<int>eg[MAXN],ctl[MAXN],seq[MAXN];
struct Node{
Node(int a,int b,int c):status(a),v(b),steps(c){}
int status,v,steps;
};
void setSP(int &s,int pos,int v){
if(v)s|=1<<(N-1-pos); //set to 1
else s&=~(1<<(N-1-pos)); //set to 0
}
bool getSP(int s,int pos){
return s&1<<(N-1-pos);
}
void init(){
memset(isc,0,sizeof(isc));
rep(i,MAXN)seq[i].clear();
rep(i,N)rep(j,ctl[i].size())isc[i][ctl[i][j]]=1;
}
int getLight(int a,int b){
int c=a^b,d=0,e=0;
while(c>0){if(c%2)return N-1-e;e++,c/=2;}
}
void print(int s,int steps){
int c=N-1,pc=-1,c2,s2,d=steps,cnt=0,l;
bool used[MAXN],on[MAXN];
memset(on,0,sizeof(on));on[0]=1;
while(d){
if(DBG)printf("%d %d\n",c,s);
c2=pre[c][s][0],s2=pre[c][s][1];
child[c2][s2][0]=c,child[c2][s2][1]=s;
c=c2,s=s2,d--;
}
c=0,s=1<<N-1,d=steps-1;
printf("The problem can be solved in %d steps:\n",steps-1);
while(d){
if(DBG)printf("%d %d\n",c,s);
if(d<steps-1&&pc!=c)printf("- Move to room %d.\n",c+1);
c2=child[c][s][0],s2=child[c][s][1];
l=getLight(s,s2);
if(c==c2) //switch
if(!on[l])printf("- Switch on light in room %d.\n",l+1),on[l]=1;
else printf("- Switch off light in room %d.\n",l+1),on[l]=0;
pc=c,c=c2,s=s2,d--;
}
}
void ans(){
int a,b,c,d,e,t,s,dis=0;
bool ok=0;
queue<Node>q;
memset(dps,0,sizeof(dps));
t=1<<N-1; //turn on 1
q.push(Node(t,0,1));
while(q.size()){
b=q.front().v,t=q.front().status,dis=q.front().steps,q.pop();
if(DBG)printf("bfs %d %d %d\n",b,t,dis);
if(b==N-1&&t==1){if(DBG)printf("ok\n");ok=1;break;}
dps[b][t]=1;
rep(i,N){
s=t;
if(isc[b][i]){ //turn on/off
a=b;
setSP(s,i,1);
if((getSP(s,a)&&getSP(s,b))&&!dps[a][s]){ //two room must be turned on
dps[a][s]=1,pre[a][s][0]=b,pre[a][s][1]=t;
q.push(Node(s,a,dis+1));}
setSP(s,i,0);
if((getSP(s,a)&&getSP(s,b))&&!dps[a][s]){ //two room must be turned on
dps[a][s]=1,pre[a][s][0]=b,pre[a][s][1]=t;
q.push(Node(s,a,dis+1));}
}
}
s=t;
rep(j,eg[b].size()){ //change room
a=eg[b][j];
if((getSP(s,a)&&getSP(s,b))&&!dps[a][s]){
dps[a][s]=1,pre[a][s][0]=b,pre[a][s][1]=t;
q.push(Node(s,a,dis+1));}
}
}
printf("Villa #%d\n",cases++);
if(N==1)printf("The problem can be solved in 0 steps:\n");
else if(ok)print(t,dis);
else printf("The problem cannot be solved.\n");
}
int main(){
int a,b,c;
while(scanf("%d%d%d",&N,&M,&c)==3){
if(N+M+c==0)break;
rep(i,MAXN)eg[i].clear(),ctl[i].clear();
rep(i,N)eg[i].push_back(i); //self room
rep(i,M)scanf("%d%d",&a,&b),a--,b--,eg[a].push_back(b),eg[b].push_back(a);
rep(i,c)scanf("%d%d",&a,&b),a--,b--,ctl[a].push_back(b);
init();
ans();
printf("\n");
}
return 0;
}
2012年10月17日 星期三
uva 10600 - ACM CONTEST AND BLACKOUT
In order to prepare the “The First National ACM School Contest”(in 20??) the major of the city decided to provide all the schools with a reliable source of power. (The major is really afraid of blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one) must be connected; in addition, some schools must be connected as well.
You may assume that a school has a reliable source of power if it’s connected directly to “Future”, or to any other school that has a reliable source of power. You are given the cost of connection between some schools. The major has decided to pick out two the cheapest connection plans – the cost of the connection is equal to the sum of the connections between the schools. Your task is to help the major – find the cost of the two cheapest connection plans.
Input
The Input starts with the number of test cases, T (1£T£15) on a line. Then T test cases follow. The first line of every test case contains two numbers, which are separated by a space, N (3£N£100) the number of schools in the city, and M the number of possible connections among them. Next M lines contain three numbers Ai, Bi, Ci , where Ci is the cost of the connection (1£Ci£300) between schools Ai and Bi. The schools are numbered with integers in the range 1 to N.
Output
For every test case print only one line of output. This line should contain two numbers separated by a single space - the cost of two the cheapest connection plans. Let S1 be the cheapest cost and S2 the next cheapest cost. It’s important, that S1=S2 if and only if there are two cheapest plans, otherwise S1£S2. You can assume that it is always possible to find the costs S1 and S2..
Sample Input
|
Sample Output
|
2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
|
110 121
37 37
|
Problem source: Ukrainian National Olympiad in Informatics 2001
Problem author: Shamil Yagiyayev
Problem submitter: Dmytro Chernysh
Problem solution: Shamil Yagiyayev, Dmytro Chernysh, K M Hasan
minimum spanning tree, second minimum spanning tree -find alternative path by replacing any existing edge with sub-optimal one.
#include<stdio.h>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#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 100
#define MAXM 5000
#define INF int(1e9)
using namespace std;
int N,M,e;
int v1[MAXM],v2[MAXM],w[MAXM],p[MAXN],inv[MAXM];
struct Node{
Node(int ed,int a,int b,int c):e(ed),v1(a),v2(b),dis(c){}
bool operator <(const Node b)const {return dis>b.dis;}
int e,v1,v2,dis;
};
void addedge(int a,int b,int c){
v1[e]=a,v2[e]=b,w[e]=c,e++;
}
int find(int v,int p[]){
if(p[v]==v)return v;
return p[v]=find(p[v],p);
}
void unit(int from,int to,int p[]){
p[find(from,p)]=p[find(to,p)];
}
void ans(){
int a,b,c,d=0,ce,s1=0,s2=0,m=INF;
priority_queue<Node>q,q2;
vector<int>ed;
rep(i,e)q.push(Node(i,v1[i],v2[i],w[i]));
q2=q;
rep(i,N)p[i]=i;
while(d<N-1){
ce=q.top().e,a=q.top().v1,b=q.top().v2,c=q.top().dis,q.pop();
if(DBG)printf("a b %d %d %d\n",a,b,c);
if(find(a,p)!=find(b,p))unit(a,b,p),ed.push_back(ce),s1+=c,d++;
}
rep(i,ed.size()){
inv[ed[i]]=1;
q=q2,d=0,s2=0;
rep(j,N)p[j]=j;
while(q.size()&&d<N-1){
ce=q.top().e,a=q.top().v1,b=q.top().v2,c=q.top().dis,q.pop();
if(!inv[ce]){
//if(DBG)printf("a b %d %d %d\n",a,b,c);
if(find(a,p)!=find(b,p))unit(a,b,p),s2+=c,d++;
}
}
if(d==N-1&&s2<m)m=s2;
inv[ed[i]]=0;
}
printf("%d %d\n",s1,m);
}
int main(){
int a,b,c,n;
bool ll=0;
scanf("%d",&n);
rep(i,n){
e=0;
scanf("%d%d",&N,&M);
rep(i,M)scanf("%d%d%d",&a,&b,&c),a--,b--,addedge(a,b,c);
ans();
}
return 0;
}
uva 10369 - Arctic Network
Problem C: Arctic Network
The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.
The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000). For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.
Sample Input
1 2 4 0 100 0 300 0 600 150 750
Sample Output
212.13
#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 500
using namespace std;
int N,S;
int p[MAXN],cor[MAXN][2];
struct Node{
Node(int a,int b,double c):v1(a),v2(b),dis(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 ans(){
double m=0,c;
int a,b,d=0;
priority_queue<Node>q;
rep(i,N)REP(j,i+1,N){c=getD(i,j),q.push(Node(i,j,c));if(DBG)printf("a b %d %d %f\n",i,j,c);}
rep(i,N)p[i]=i;
while(d<N-S){
a=q.top().v1,b=q.top().v2,c=q.top().dis,q.pop();
if(DBG)printf("a b %d %d %f\n",a,b,c);
if(find(a)!=find(b))unit(a,b),m=max(m,c),d++;
}
printf("%.2f\n",m);
}
int main(){
int n;
bool ll=0;
scanf("%d",&n);
rep(i,n){
scanf("%d%d",&S,&N);
rep(i,N)scanf("%d%d",&cor[i][0],&cor[i][1]);
ans();
}
return 0;
}
訂閱：
文章 (Atom)