Algorithm

HackerRank/Algorithm/Graph Theory/Roads and Libraries

Problem Summary

Given a map of N cities with M bidirectional roads, along with the cost to repair a road and the cost to build a new library, find the minimal cost to build some libraries and repair some roads such that every city would have access to at least one library.

Solution

We use c_lib to denote the cost of building a library, and c_road to denote the cost of repairing a road.

If we repair R roads and then the cities are now divided into C groups of connected componants. Since we want to spend least money, we only need to repair R = N − C roads.
We can see the minimal cost now is c_road × (N − C) + c_lib × C.

Apparently, if c_lib ≤ c_road, then there is no need to repair any roads. The answer is c_lib × N.

If c_lib > c_road, we want to build as few libraries as possible. So we use DFS to find out how many components there can be, and denote the number with D. Then the answer is c_lib × D + c_road × (N − D).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstring>
const int maxn = 100002;
int tot,head[maxn<<1],next[maxn<<1],v[maxn<<1];
int colors, co[maxn];
void add(int x,int y)
{
	tot++; next[tot]=head[x]; head[x]=tot; v[tot]=y;
}
void dfs(int x)
{
	co[x]=colors;
	for(int i=head[x];i!=0;i=next[i])
	{
		int y=v[i];
		if(co[y]!=0) continue;
		dfs(y);
	}
}
int main()
{
	long long ans;
	int n,m,a,b,Q,c_lib,c_road;
	scanf("%d",&Q);
while(Q)
{
	Q--;
	scanf("%d%d%d%d",&n,&m,&c_lib,&c_road);
	if(c_lib<=c_road)
	{
		ans=(long long)c_lib * n;
		printf("%lld\n",ans);
		if(Q)
			for(int i=0;i<m;i++)
				scanf("%d%d",&a,&b);
		continue;
	}
	tot=0;
	memset(head,0,sizeof(head));
	memset(next,0,sizeof(next));
	memset(co,0,sizeof(co));
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	colors=0;
	for(int i=1;i<=n;i++)
		if(co[i]==0)
		{
			colors++;
			dfs(i);
		}
	ans=(long long)colors * c_lib + (long long) (n-colors) * c_road;
	printf("%lld\n",ans);
}
	return 0;
}