programming challenges chapter 8 example 4: servicing stations using c language:
ID: 657159 • Letter: P
Question
programming challenges chapter 8 example 4: servicing stations using c language:
A company offers personal computers for sale in N towns (3 ? N ? 35), denoted by 1, 2, . . . , N.
There are direct routes connecting M pairs among these towns. The company decides to build
servicing stations to ensure that for any town X, there will be a station located either in X or in some
immediately neighboring town of X.
Write a program to find the minimum number of stations the company has to build.
Input
The input consists of multiple problem descriptions. Every description starts with number of towns
N and number of town-pairs M, separated by a space. Each of the next M lines contains a pair of
integers representing connected towns, at one pair per line with each pair separated by a space. The
input ends with N = 0 and M = 0.
Output
For each input case, print a line reporting the minimum number of servicing stations needed.
Sample Input
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0
Sample Output
2
Explanation / Answer
#include <stdio.h>
void station_allocation(int[][],int);
int main()
{
int stations[15][15]; // increase the size as per your need
int i,j, M, N;
for(i=0;i<15;i++)
for(j=0;j<15;j++)
stations[i][j]=0;
int numberOfTowns,numberOfTownpairs;
printf(" Enter the number of Towns & Number of town pairs");
scanf("%d %d",& numberOfTowns,&numberOfTownpairs);
printf(" Enter the values of connected Towns ");
scanf("%d%d", &M,&N);
while(M!=0 && N!=0)
{
stations[M][N]=1;
scanf("%d%d", &M,&N);
}
station_allocation(stations,numberOfTowns);
return 0;
}
void station_allocation(int stations[][], int n)
{
int i,j,k, n, m;
int countStation=0;
int countVertice=0;
int arr[50], p=0,t,f=0;
while(countVertice<=n)
{
for(i=0;i<15;i++)
{
for(j=0;j<15;j++)
{
if(stations[i][j]==1)
{
n=i;
m=j;
arr[p++]=n;
countStation=1;
countVertice++;
for(k=0;k<n;k++)
{
if(stations[n][k]==1 && countVertice!=8)
{
for(t=0;t<p;t++)
{
if(arr[t]==k)
f=1;
break;
}
if(f==0){
arr[p++]=k;
countVertice++;
}
}
countStation++;
}
}
}
}
}
printf("Number of service stations possible:%d",countStation);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.