名字灵感来源于楼天城男人九题:joy:
Luogu2746 [USACO5.3]校园网Network of Schools
题解
作为Tarjan入门题还是很不错的。
依据题意，可以把学校看成点，关系看成边，建图。显然，在同一个协议内的学校（点之间可以互相到达）我们可以看成一个点，这里就用到了Tarjan缩点。
由于缩点以后的图是不可能存在环的，因此只有可能有链。对于一条链，如果我们想从一个点到另外所有点，只需要找到那个入度为0的点即可。
因此任务A就是缩点以后找到入度为0的点。
对于任务B，需要加入协议的学校一定是入度为0的点和出度为0的点，在它们之间连一条边即可解决问题。当这两者的数量不相等时，就需要再找点配对。所以任务B的答案就是入度为0的点和出度为0的点的最大值。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100 + 5;
int n, num, ind, tot;
int head[SIZE], low[SIZE], dfn[SIZE], in[SIZE], deg[SIZE], inDegree[SIZE];
std::stack < int > st;
std::set < int > G[SIZE];
struct node {
int to, Next;
} edge[SIZE * SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
st.push(x); in[x] = 1;
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v]) {
low[x] = std::min(low[x], dfn[v]);
}
}
if (dfn[x] == low[x]) {
++tot;
while (st.top() != x) {
deg[st.top()] = tot;
in[st.top()] = 0;
st.pop();
}
deg[st.top()] = tot;
in[st.top()] = 0;
st.pop();
}
}
int main()
{
int u, v;
n = read();
for (u = 1; u <= n; u++) {
while (scanf("%d", &v) && v)
Addedge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) DFS(i);
}
for (u = 1; u <= n; u++) {
for (int i = head[u]; i; i = edge[i].Next) {
if (deg[edge[i].to] != deg[u] && G[deg[u]].find(deg[edge[i].to]) == G[deg[u]].end()) {
G[deg[u]].insert(deg[edge[i].to]);
inDegree[deg[edge[i].to]]++;
}
}
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= tot; i++) {
if (!inDegree[i]) ans1++;
if (!G[i].size()) ans2++;
}
if (tot == 1)
printf("1\n0");
else printf("%d\n%d\n", ans1, std::max(ans1, ans2));
return 0;
}
Luogu2812 [USACO5.3]校园网Network of Schools（加强版）
吐槽
实在不晓得哪里加强了，上面的代码改一下数组大小就可以AC
Luogu2341 [HAOI2006]受欢迎的牛|【模板】强连通分量
题解
不难发现，如果一些奶牛在一个连通块中，那么他们肯定互相喜欢，因此如果这个图都在一个强连通分量中，则不存在明星奶牛。根据这个分析，我们可以得出，如果一头奶牛是明星，那么它肯定是一个出度为1入度为0的点，如果有两个这样的点，那么他们两个肯定互相不喜欢，因此又不存在明星。
Code
有点Bug，建议不要对抄。
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 10000 + 5;
const int SIZE_EDGE = 50000 + 5;
int n, m, num, tot, ind;
int head[SIZE], in[SIZE], deg[SIZE], scc[SIZE], dfn[SIZE], low[SIZE], pail[SIZE];
std::stack < int > s;
struct node {
int to, Next;
} edge[SIZE_EDGE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
in[x] = 1;
s.push(x);
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v]) low[x] = std::min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++tot;
while (s.top() != x) {
in[s.top()] = 0;
scc[s.top()] = tot;
pail[tot]++;
s.pop();
}
in[s.top()] = 0;
scc[s.top()] = tot;
pail[tot]++;
s.pop();
}
}
int main()
{
int u, v;
n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read(), v = read();
Addedge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[v]) DFS(i);
}
for (u = 1; u <= n; u++) {
for (int i = head[u]; i; i = edge[i].Next) {
v = edge[i].to;
if (scc[u] != scc[v]) deg[scc[u]]++;
}
}
int flag = 0;
for (int i = 1; i <= tot; i++) {
if (!deg[i]) {
if (flag) { puts("0"); return 0; }
flag = i;
}
}
printf("%d", pail[flag]);
return 0;
}
Luogu2002 消息扩散
题解
这个题跟校园网那个第一个子任务差不多，只是需要判断一下自环，直接Tarjan缩点，记录入度为0的点即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100000 + 5;
const int SIZE_EDGE = 500000 + 5;
int n, m, num, top, ind, ans, point;
int head[SIZE], low[SIZE], dfn[SIZE], belong[SIZE], deg[SIZE], Stack[SIZE], in[SIZE];
struct node {
int to, Next;
} edge[SIZE_EDGE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
Stack[++top] = x, deg[x] = 1;
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (deg[v]) low[x] = std::min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++point;
int j = -1;
while (j != x) {
j = Stack[top--];
belong[j] = point;
deg[j] = 0;
}
}
}
int main()
{
int u, v;
n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read(), v = read();
if (u != v) Addedge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) DFS(i);
}
for (int k = 1; k <= n; k++) {
for (int i = head[k]; i; i = edge[i].Next) {
if (belong[k] != belong[edge[i].to])
in[belong[edge[i].to]]++;
}
}
for (int i = 1; i <= point; i++)
if (!in[i]) ++ans;
printf("%d\n", ans);
return 0;
}
Luogu2169 正则表达式
题解
题面提示很明显了：
存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0
意思就是告诉我们，在一个强连通分量的所有点距离都为0，所以我们可以直接缩点，把这些在同一强连通分量中距离为0的点看成一个点，中途重新建图，跑一遍SPFA求最短路即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 200000 + 5;
const int SIZE_EDGE = 1000000 + 5;
const int inf = 0x7f7f7f7f;
int n, m, num, tot;
int head[SIZE], dfn[SIZE], low[SIZE], deg[SIZE], in[SIZE], dis[SIZE], vis[SIZE];
std::stack < int > s;
struct node {
int to, v, Next;
} edge[SIZE_EDGE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y, int z)
{
edge[++num].to = y;
edge[num].v = z;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++tot;
in[x] = 1; s.push(x);
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v]) low[x] = std::min(low[x], dfn[v]);
}
if (dfn[x] == low[x]) {
++tot;
while (s.top() != x) {
deg[s.top()] = tot;
in[s.top()] = 0;
s.pop();
}
deg[s.top()] = tot;
in[s.top()] = 0;
s.pop();
}
}
inline void SPFA()
{
queue < int > Q;
memset(dis, inf, sizeof(dis));
dis[1] = 0, vis[1] = 1;
Q.push(1);
while (!Q.empty()) {
int u = Q.front(), v, d;
vis[u] = 0;
Q.pop();
for (int i = head[u]; i; i = edge[i].Next) {
v = edge[i].to, d = edge[i].v;
if (deg[u] == deg[v]) d = 0;
if (dis[v] > dis[u] + d) {
dis[v] = dis[u] + d;
if (!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
}
int main()
{
int u, v, d;
n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read(), v = read(), d = read();
Addedge(u, v, d);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) DFS(i);
}
SPFA();
printf("%d\n", dis[n]);
return 0;
}
Luogu2194 HXY烧情侣
题解
这道题有一次CJ模拟赛中好像出了一个类似的，当时没切(TCL)。
首先HXY一次性能走一遍的电影院是一个强连通分量，可以先缩一下点。
之后可以发现，我们只要烧完所有的联通块就可以了。因为烧一个连通块的最小代价就是那一个连通块中最小的点权，所以总共最小的代价就是每一个联通块中最小点权之和。
至于方案数，根据乘法原理，只要记录每个联通块中最小点权的个数最后算乘积即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100000 + 5;
const int SIZE_EDGE = 300000 + 5;
const int Mod = 1e9 + 7;
int n, m, num, tot, ind;
int head[SIZE], low[SIZE], dfn[SIZE], a[SIZE], in[SIZE], scc[SIZE];
std::stack < int > s;
std::vector < int > g[SIZE];
struct node {
int to, Next;
} edge[SIZE_EDGE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
in[x] = 1; s.push(x);
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v])
low[x] = std::min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++tot;
while (s.top() != x) {
scc[s.top()] = tot;
in[s.top()] = 0;
g[tot].push_back(s.top());
s.pop();
}
scc[s.top()] = tot;
in[s.top()] = 0;
g[tot].push_back(s.top());
s.pop();
}
}
int main()
{
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
m = read();
int u, v;
for (int i = 1; i <= m; i++) {
u = read(), v = read();
Addedge(u, v);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) DFS(i);
}
// std::cout << tot << endl;
int ans1 = 0, ans2 = 1;
for (int i = 1; i <= tot; i++) {
int cnt = 0, Min = Mod;
for (int j = 0; j < g[i].size(); j++) {
if (a[g[i][j]] < Min) {
Min = a[g[i][j]];
cnt = 1;
}
else if (Min == a[g[i][j]]) ++cnt;
}
ans1 += Min;
ans2 = (ans2 % Mod * cnt % Mod) % Mod;
}
printf("%d %d\n", ans1, ans2);
return 0;
}
Luogu2656 采蘑菇
题解
很显然，一条路径如果是一个环，我们便可以不停地走，直到取完这个环中所有的蘑菇为止。
因此我们先Tarjan缩点找环，因为我们希望取得蘑菇越多越好，所以我们缩点后跑一遍最长路，便可以解决。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 80000 + 5;
const int SIZE_EDGE = 200000 + 5;
int n, m, s, num1, num2, tot, ind;
int head1[SIZE], head2[SIZE], low[SIZE], dfn[SIZE], in[SIZE], scc[SIZE], w[SIZE], dis[SIZE], vis[SIZE];
double coe[SIZE_EDGE];
std::stack < int > st;
struct node {
int from, to, v, Next;
} edge1[SIZE_EDGE], edge2[SIZE_EDGE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge1(int x, int y, int z)
{
edge1[++num1].to = y;
edge1[num1].from = x;
edge1[num1].v = z;
edge1[num1].Next = head1[x];
head1[x] = num1;
}
inline void Addedge2(int x, int y, int z)
{
edge2[++num2].to = y;
edge2[num2].from = x;
edge2[num2].v = z;
edge2[num2].Next = head2[x];
head2[x] = num2;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
in[x] = 1; st.push(x);
for (int i = head1[x]; i; i = edge1[i].Next) {
int v = edge1[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v]) low[x] = std::min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++tot;
while (st.top() != x) {
scc[st.top()] = tot;
in[st.top()] = 0;
st.pop();
}
scc[st.top()] = tot;
in[st.top()] = 0;
st.pop();
}
}
inline void SPFA()
{
queue < int > Q;
memset(dis, -1, sizeof(dis));
dis[s] = w[s], vis[s] = 1;
Q.push(s);
while (!Q.empty()) {
int u = Q.front(), v;
Q.pop();
vis[u] = 0;
for (int i = head2[u]; i; i = edge2[i].Next) {
v = edge2[i].to;
if (dis[v] < dis[u] + edge2[i].v + w[v]) {
dis[v] = dis[u] + edge2[i].v + w[v];
if (!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
}
int main()
{
int u, v, d;
n = read(), m = read();
for (int i = 1; i <= m; i++) {
u = read(), v = read(), d = read(); scanf("%lf", &coe[i]);
Addedge1(u, v, d);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) DFS(i);
}
for (int i = 1; i <= m; i++) {
u = edge1[i].from, v = edge1[i].to;
if (scc[u] == scc[v]) {
int id = scc[v];
d = edge1[i].v;
while (d) {
w[id] += d;
d = (int) d * coe[i];
}
}
else Addedge2(scc[u], scc[v], edge1[i].v);
}
s = read(), s = scc[s];
// for (int i = 1; i <= m; i++) printf("%d ", scc[i]);
SPFA();
int ans = 0;
for (int i = 1; i <= n; i++)
ans = std::max(ans, dis[i]);
printf("%d\n", ans);
return 0;
}
Luogu1407 [国家集训队]稳定婚姻
题解
这道题的题面对于广大单纯的中学生还是有点难理解的。
把所有交往过的男女连线，会发现出现了环。那么在环里的男女就是不稳定婚姻（暗示马蓉王宝强）
所以想到可以使用Tarjan找环。
然而Tarjan是适用于有向图的，这是个无向图。
然后就不会做了，题解说男女交替连边建图可以跑，那我就照做了。
详情看代码。
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 8000 + 5;
const int SIZE_EDGE = 20000 + 5;
int n, m, ind, tot, num;
int head[SIZE], low[SIZE], dfn[SIZE], in[SIZE], scc[SIZE];
std::map < string, int > M;
std::stack < int > s;
struct node {
int to, Next;
} edge[SIZE_EDGE * 5];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void Addedge(int x, int y)
{
edge[++num].to = y;
edge[num].Next = head[x];
head[x] = num;
}
inline void DFS(int x)
{
low[x] = dfn[x] = ++ind;
in[x] = 1; s.push(x);
for (int i = head[x]; i; i = edge[i].Next) {
int v = edge[i].to;
if (!dfn[v]) {
DFS(v);
low[x] = std::min(low[x], low[v]);
}
else if (in[v]) low[x] = std::min(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++tot;
while (s.top() != x) {
scc[s.top()] = tot;
in[s.top()] = 0;
s.pop();
}
scc[s.top()] = tot;
in[s.top()] = 0;
s.pop();
}
}
int main()
{
string Boy, Girl;
n = read();
for (int i = 1; i <= n; i++) {
std::cin >> Girl >> Boy;
M[Girl] = i;
M[Boy] = i + n;
Addedge(i, i + n);
}
m = read();
for (int i = 1; i <= m; i++) {
std::cin >> Girl >> Boy;
Addedge(M[Boy], M[Girl]);
}
for (int i = 1; i <= n << 1; i++) {
if (!dfn[i]) DFS(i);
}
for (int i = 1; i <= n; i++) {
if (scc[i] == scc[i + n]) puts("Unsafe");
else puts("Safe");
}
return 0;
}
Comments | 1 条评论
很不错，点赞