USACO 5.3.3 Network of Schools 校园网 schlnet
这是一道收缩强连通分量的题。
该题描述的是一个有向图。我们都知道，在一个有向图强连通分量中从任意一个顶点开始，可以到达强连通分量的每个顶点。由此可以把该题中所有强连通分量收缩成分别一个顶点，则入度为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