Beyond the Void
BYVoid
USACO 5.3.3 Network of Schools 校園網 schlnet
本文正體字版由OpenCC轉換

這是一道收縮強連通分量的題。

該題描述的是一個有向圖。我們都知道,在一個有向圖強連通分量中從任意一個頂點開始,可以到達強連通分量的每個頂點。由此可以把該題中所有強連通分量收縮成分別一個頂點,則入度爲0的頂點就是最少要接受新軟件副本的學校。

第二問就是,問至少添加多少條邊,才能使原圖強連通。也就問在收縮後的圖至少添加多少條邊,才能使之強連通。

可以知道,當存在一個頂點入度爲0或者出度爲0的時候,該圖一定不是強連通的。爲了使添加的邊最少,則應該把入度爲0頂點和出度爲0的頂點每個頂點添加1條邊,使圖中不存在入度爲0頂點和出度爲0的頂點。

當入度爲0的頂點多於出度爲0的頂點,則應添加的邊數應爲入度爲0的頂點的個數。當出度爲0的頂點多於出入度爲0的頂點,則應添加的邊數應爲出度爲0的頂點的個數。

這樣就可以解決問題了。但是不要忘了還有特殊的情況,當原圖本身就是強連通分量時,收縮成一個頂點,該頂點入度和出度都爲0,但第一問應爲1,第二問應爲0。

求強連通分量,我用的兩遍深搜的Kosaraju算法,時間複雜度爲O(n)。把找到的每個強連通分量收縮爲一的頂點,組成新圖。設r(x)爲x所在的強連同分量的代表節點,如果原圖中存在邊e(x,y),那麼新圖中有邊e(r(x),r(y)) 。然後根據點的鄰接關係統計出度和入度即可。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2936 KB]
   Test 2: TEST OK [0.000 secs, 2940 KB]
   Test 3: TEST OK [0.000 secs, 2936 KB]
   Test 4: TEST OK [0.000 secs, 2936 KB]
   Test 5: TEST OK [0.011 secs, 2936 KB]
   Test 6: TEST OK [0.011 secs, 2940 KB]
   Test 7: TEST OK [0.011 secs, 2940 KB]
   Test 8: TEST OK [0.000 secs, 2936 KB]
   Test 9: TEST OK [0.000 secs, 2940 KB]
   Test 10: TEST OK [0.000 secs, 2940 KB]
   Test 11: TEST OK [0.000 secs, 2940 KB]

All tests OK.

Your program ('schlnet') produced all correct answers! This is your submission #2 for this problem. Congratulations! 
/*
ID: cmykrgb1
PROG: schlnet
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXN 101
#define max(x,y) ((x)>(y)?x:y)

using namespace std;

ifstream fi("schlnet.in");
ofstream fo("schlnet.out");

int N,M;
int adjl[MAXN][MAXN],fdjl[MAXN][MAXN];
bool vis[MAXN],dis[MAXN][MAXN];
int belong[MAXN],ind[MAXN],oud[MAXN],i0,o0;


void init()
{
	int t,i;
	fi >> N;
	for (i=1;i<=N;i++)
	{
		fi >> t;
		while (t)
		{
			adjl[i][ ++adjl[i][0] ]=t;
			fdjl[t][ ++fdjl[t][0] ]=i;
			fi >> t;
		}
	}
}

void dfs(int i)
{
	int j,k;
	vis[i]=true;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!vis[j])
			dfs(j);
	}
}

void fdfs(int i)
{
	int j,k;
	belong[i]=M;
	for (k=1;k<=fdjl[i][0];k++)
	{
		j=fdjl[i][k];
		if (vis[j] && !belong[j])
			fdfs(j);
	}
}

void solve()
{
	int i,j,k;
	for (i=1;i<=N;i++)
	{
		if (!belong[i])
		{
			dfs(i);
			M++;
			fdfs(i);
			memset(vis,0,sizeof(vis));
		}
	}
	for (i=1;i<=N;i++)
	{
		for (k=1;k<=adjl[i][0];k++)
		{
			j=adjl[i][k];
			dis[belong[i]][belong[j]]=true;
		}
	}
	for (i=1;i<=M;i++)
	{
		for (j=1;j<=M;j++)
		{
			if (i!=j && dis[i][j])
			{
				oud[i]++;
				ind[j]++;
			}
		}
	}
	for (i=1;i<=M;i++)
	{
		if (ind[i]==0)
			i0++;
		if (oud[i]==0)
			o0++;
	}
}

void print()
{
	if (M==1)
		fo << 1 << endl << 0 << endl;
	else
	{
		fo << i0 << endl;
		fo << max(i0,o0) << endl;
	}
	fi.close();
	fo.close();
}

int main()
{
	init();
	solve();
	print();
	return 0;
}

上次修改時間 2017-02-03

相關日誌