一、P2812 校园网络【[USACO]Network of Schools加强版】
P2812 校园网络【[USACO]Network of Schools加强版】
1、算法简析
首先，建立一张有向图——学校是节点，学校间的单向线路是有向边。 Q 1 Q_1 Q1：选出若干个节点，从这些节点出发可以到达其它的任意节点（即不考虑选出的节点），求这些节点数量的最小值。 Q 2 Q_2 Q2：添加若干条有向边，使有向图中任意两点可以相互到达，求这些边数量的最小值。
我们知道，在强连通分量中，任意两点可以相互到达，所以对于一个强连通分量，只要有一个节点作为代表即可。因此，我们可以通过 T a r j a n Tarjan Tarjan 算法求 S C C SCC SCC，用 S C C SCC SCC 的编号建立新的节点，代替相应的强连通分量。然后建立新图，对原图进行了简化。这就是 S C C SCC SCC 缩点问题。
接下来，在缩点后的新图（无环图 D A G DAG DAG）上讨论问题。
对于 Q 1 Q_1 Q1，若一个节点的入度为 0 0 0，则其它节点不可能到达它，所以该点必须作为起点。因此，入度为 0 0 0 的节点个数即所求。
对于 Q 2 Q_2 Q2，要使任意两点可以相互到达，那么任意节点的出入度都不能为 0 0 0。又要使添加的边数最少，可以令出度为 0 0 0 的节点指向入度为 0 0 0 的节点。若两种节点的数量相等，则该数即所求。若数量不等，则取二者的最大值。因此出入度为 0 0 0 的节点数的最大值即所求。
2、Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e4 + 3;
int N;
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], cnt;
int din[MAX], dout[MAX]; // din[x] -- 缩点i的入度; dout[x] -- 缩点i的出度
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
S.push(u), instk[u] = true;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int t;
++cnt;
do
{
t = S.top();
S.pop(), instk[t] = false;
scc[t] = cnt;
} while (t != u);
}
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
cin >> N;
for (int i = 1; i <= N; ++i)
{
int a;
while (cin >> a && a)
G[i].push_back(a);
}
// scc缩点处理
for (int i = 1; i <= N; ++i)
if (!dfn[i])
tarjan(i);
// 计算出入度
for (int i = 1; i <= N; ++i)
{
for (int j = 0; j < G[i].size(); ++j)
{
int v = G[i][j];
if (scc[i] != scc[v])
{
++din[scc[v]];
++dout[scc[i]];
}
}
}
// 计算出入度为零的节点个数
int a = 0, b = 0;
for (int i = 1; i <= cnt; ++i)
{
if (!din[i]) ++a;
if (!dout[i]) ++b;
}
// 问1：入度为0的节点即所求
cout << a << endl;
// 问2：要满足题意，则所有节点的出入度都不为0。
// 要使使用的边最少，则将出度为0的节点指向入度为0的节点。
// 两种节点的个数相等的情况下，两者的个数即所求。
// 若不相等，取二者的max。
if (cnt == 1) cout << 0 << endl; // 特判，此时原图就是连通的，不需要添边
else cout << max(a, b) << endl;
return 0;
}
二、P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
1、算法简析
建立有向图模型：奶牛是节点，“喜欢”是有向边。因为强连通分量的定义，所以一个强连通分量中的奶牛都可能是“明星”。因此，我们进行 S C C SCC SCC 缩点处理，使原图变成 D A G DAG DAG 图。此时，若我们选择一个入度为 0 0 0 的节点作为根节点，向上拉直，就形成了一棵树（当然，原图可能是不连通的，所以也可能形成森林）。显然，树（森林）的叶子节点就是所求。换句话说，也就是出度为 0 0 0 的 S C C SCC SCC 中的节点即所求。
需要注意的是，若出度为 0 0 0 的 S C C SCC SCC 的个数大于 1 1 1，则满足条件的节点个数为 0 0 0。因为“明星奶牛”需要能被所有节点访问，若存在其它节点的出度为 0 0 0，显然就不能满足要求。也就是说，形成的树（森林）的叶子节点只能有一个。或者，出度为 0 0 0 的 S C C SCC SCC 的个数只能为 1 1 1。
2、Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickin(void)
{
ll ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
const int MAX = 1e4 + 3;
int N, M;
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], siz[MAX], cnt;
int dout[MAX];
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
S.push(u), instk[u] = true;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int t;
++cnt;
do
{
t = S.top();
S.pop(), instk[t] = false;
scc[t] = cnt;
++siz[cnt];
} while (t != u);
}
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
N = quickin(), M = quickin();
for (int i = 0; i < M; ++i)
{
int a, b;
a = quickin(), b = quickin();
G[a].push_back(b);
}
for (int i = 1; i <= N; ++i)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= N; ++i)
{
for (int j = 0; j < G[i].size(); ++j)
{
int v = G[i][j];
if (scc[i] != scc[v])
{
++dout[scc[i]];
}
}
}
int sum = 0, zeros = 0; // sum -- 出度为0的SCC包含的节点个数; zeors -- 出度为0的SCC个数
for (int i = 1; i <= cnt; ++i)
{
if (!dout[i])
{
sum += siz[i];
++zeros;
}
}
if (zeros > 1) sum = 0; // 特判：若存在两个及以上的SCC出度为0，它们肯定无法相互访问，都不满足要求
cout << sum << endl;
return 0;
}
三、P3387 【模板】缩点
P3387 【模板】缩点
1、算法简析
对于本题，我们可以先进行缩点，建立一张新的 D A G DAG DAG 图，然后在新图上寻找最大的权值之和。
注意， S C C SCC SCC 缩点后，新节点的编号满足拓扑序列。因此，可以用动态规划求最大值。
2、Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickin(void)
{
ll ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
const int MAX = 1e4 + 3;
int N, M, worth[MAX];
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], cnt;
int nworth[MAX]; // 新图中各节点的权值
vector<int> nG[MAX]; // 新图中的边
int dp[MAX]; // dp[u] -- 以u为起点的路径的最大值
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
S.push(u), instk[u] = true;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int t;
++cnt;
do
{
t = S.top();
S.pop(), instk[t] = false;
scc[t] = cnt;
} while (t != u);
}
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
N = quickin(), M = quickin();
for (int i = 1; i <= N; ++i)
worth[i] = quickin();
for (int i = 0; i < M; ++i)
{
int a, b;
a = quickin(), b = quickin();
G[a].push_back(b);
}
for (int i = 1; i <= N; ++i)
if (!dfn[i])
tarjan(i);
for (int u = 1; u <= N; ++u)
{
nworth[scc[u]] += worth[u]; // 新节点的权值
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (scc[u] != scc[v]) // 存新边
nG[scc[u]].push_back(scc[v]);
}
}
// SCC缩点后的新节点的编号按降序满足拓扑序列
for (int u = 1; u <= N; ++u)
{
if (dp[u] == 0) dp[u] = nworth[u];
for (int i = 0; i < nG[u].size(); ++i)
{
int v = nG[u][i];
dp[u] = max(dp[u], dp[v] + nworth[u]);
}
}
int ans = 0;
for (int i = 1; i <= cnt; ++i)
ans = max(ans, dp[i]);
cout << ans << endl;
return 0;
}
完
![【C语言】路漫漫其修远兮，深入[指针]正当下](https://img-blog.csdnimg.cn/direct/cf2d2f9ff0d64f81893671aadc8cb46a.gif)
