07月
08

POJ_1236 Network of Schools

发表于 • 本文总阅读数 次
字数统计: 714

题目

  http://poj.org/problem?id=1236

题意

  有N个学校用一些单向的网络连接一起，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。
  问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
  问题2：至少需要添加几条传输线路，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

题目解析

  将学校当做点，网络线路当做边，得到一个有向图，算出这个图里所有的强连通分量。因为同一个强连通分量之间的任意两点可以互相连通，所以向一个点发送软件后，与这个点同属于一个强连通分量的点都能收到软件。可以将每个强连通分量都假设为一个点，然后算出所有强连通分量的入度和出度，假设入度为0的强连通分量的个数为d_in0，出度为0的强连通分量的个数为d_out0。问题1的答案等于d_in0；当强连通分量的个数为1时，问题2的答案等于0，当强连通分量的个数大于1时，问题2的答案等于max(d_in0, d_out0)。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* AC 0MS 356K */
#include <stdio.h>
#include <string.h>

const int MAX_N = 100 + 10;

int n;
int mp[MAX_N][MAX_N];
int vis[MAX_N], vis_t;
int st[MAX_N], st_top;
int in_st[MAX_N];
int low[MAX_N];
int belong[MAX_N], ccn;

int tarjan(int v)
{
	int i, k;

	vis[v] = vis_t;
	low[v] = vis_t;
	vis_t++;
	st_top++;
	st[st_top] = v;
	in_st[v] = 1;
	for(i = 0; i < n; i++)
	{
		if(mp[v][i] == 0)
		{
			continue;
		}
		if(vis[i] == 0)
		{
			tarjan(i);
			if(low[v] > low[i])
			{
				low[v] = low[i];
			}
		}
		else if(in_st[i] == 1 && low[v] > vis[i])
		{
			low[v] = vis[i];
		}
	}
	if(low[v] == vis[v])
	{
		k = -1;
		while(k != v)
		{
			k = st[st_top];
			st_top--;
			in_st[k] = 0;
			belong[k] = ccn;
		}
		ccn++;
	}
}

int main()
{
	int i, j, k;
	int d_in0, d_out0;
	int d_in[MAX_N], d_out[MAX_N];

	scanf("%d", &n);
	memset(mp, 0, sizeof(mp));
	for(i = 0; i < n; i++)
	{
		while(scanf("%d", &k) != EOF && k !=0)
		{
			mp[i][k - 1] = 1;
		}
	}

	/* 计算强连通分量 */
	memset(vis, 0, sizeof(vis));
	memset(in_st, 0, sizeof(in_st));
	ccn = 0;
	for(i = 0; i < n; i++)
	{
		if(vis[i] == 0)
		{
			st_top = -1;
			vis_t = 1;
			tarjan(i);
		}
	}

	/* 计算每个强连通分量的入度和出度 */
	memset(d_in, 0, sizeof(d_in));
	memset(d_out, 0, sizeof(d_out));
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(mp[i][j] == 1 && belong[i] != belong[j])
			{
				d_in[belong[j]]++;
				d_out[belong[i]]++;
			}
		}
	}

	d_in0 = 0;
	d_out0 = 0;
	for(i = 0; i < ccn; i++)
	{
		if(d_in[i] == 0)
		{
			d_in0++;
		}
		if(d_out[i] == 0)
		{
			d_out0++;
		}
	}
	if(ccn == 1)
	{
		printf("1\n0\n");
	}
	else
	{
		printf("%d\n%d\n", d_in0, (d_in0 > d_out0) ? d_in0 : d_out0);
	}

	return 0;
}
分享到：
0%