首页 > 其他分享 >缩点 P2812 校园网络【[USACO]Network of Schools加强版】

缩点 P2812 校园网络【[USACO]Network of Schools加强版】

时间:2023-02-02 09:58:57浏览次数:49  
标签:缩点 连通 Network int 入度 USACO dfn low

首先找出图中的强连通分量,用tarjan算法。强连通分量内部强联通,所以将其看成一个点是不影响的。

进行缩点之后,整张图变成了一个有向无环图。

首先对于每一条边进行检测,如果这一条边是连接两个团的,那么更新这两个团的出入度。这里我们知道,出度总和等于入度总和。

接下来再对于每个团遍历,如果这个团出度为0或入度为0,就需要统计,最后需要添加的母机个数就是入度为0的个数,因为入度为零的团没有别的团连接,无法使用母机;需要加的边数就是整个图出度为0和入度为0的较大值,这一问其实是让缩成的DAG变成一个强连通图,强连通图的性质是没有出度为0或入度为0。这个问题想的还不是很透彻,悬而未决。

#include <bits/stdc++.h>

using namespace std;

const int N = 10005;
vector<int>e[N];
bitset<N>instk;
stack<int>stk;
int dfn[N], low[N], tot;
int scc[N], cnt;
int deg_in[N], deg_out[N];
int n;
void tarjan(int u)
{
	dfn[u] = low[u] = ++tot;
	stk.push(u);
	instk[u] = 1;
	for (int v : e[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (instk[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		cnt++;
		int v;
		do {
			v = stk.top();
			stk.pop();
			instk[v] = 0;
			scc[v] = cnt;
		} while (v != u);
	}
}
int main()
{
	scanf("%d", &n);
	for (int i = 1, a; i <= n; i++) {
		while (scanf("%d", &a) && a != 0) {
			e[i].push_back(a);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int v : e[i]) {
			if (scc[v] != scc[i]) {
				deg_out[scc[i]] ++;
				deg_in[scc[v]] ++;
			}
		}
	}
	int a = 0, b = 0;
	for (int i = 1; i <= cnt; i++) {
		if (!deg_in[i]) a++;
		if (!deg_out[i]) b++;
	}
	printf("%d\n", a);
	if (cnt == 1) {
		printf("0\n");
	} else {
		printf("%d\n", max(a, b));
	}
	return 0;
}

标签:缩点,连通,Network,int,入度,USACO,dfn,low
From: https://www.cnblogs.com/CYLSY/p/17084954.html

相关文章

  • USACO2023 一月月赛 Platinum 3
    Platinum3分析树上的最优化问题先不动脑子DP一波。用\(f[i]\)表示将以\(i\)为根的子树中,所有子树都满足题设开灭条件所需要的最少次数。现在把这个子树画成下图这样,假......
  • USACO2023 一月月赛 Platinum 2
    受到样例的第四个询问启发,我们可以发现一个性质:一开始先让魔力积累,然后肯定是在最晚的那个时候,我们去把魔力池里该取的魔力取走,而不是一开始就和一个无头苍蝇一样在图上乱......
  • 题解 【[USACO23JAN] Lights Off G】
    problem给两个长为\(n\)的0/1字符串\(S,T\),进行如下操作\(cnt\)次:自行选定\(0\leqx<n\),使得\(T_x\)异或一。将\(S\)异或上\(T\)。将\(T\)的最后一位......
  • 题解 【[USACO23JAN] Find and Replace G】
    problem有一个字符串\(S\),初始时为\(\tt'a'\),现在进行\(n\)次操作,第\(i\)次操作形如:将\(S\)中的所有的字符\(ch_i\)替换为字符串\(T_i\)。然后输出\(S[l......
  • 【计算机网络】Stanford CS144 Lab0 : networking warmup 学习记录
    CS144官方镜像:https://cs144.github.io/kangyupl备份的镜像:https://kangyupl.gitee.io/cs144.github.io/实验准备Ubuntu18.04.6LTSx86_64(实验提供)gcc8......
  • 【题解】USACO 2023 January Sliver
    因为Glod打寄了,就来写写Sliver的题解吧,现在应该比赛结束了吧。A.FindAndReplace题目分析:我们可以对给定的串建出一种关系,也就是如果在上面的字符串中是字符\(c_1......
  • USACO2023Jan游记
    由于学校要求,过来打USACO。似乎要求起码升到白金?由于是第一次打,只有从铜组开始了。Brouze简单题,就给核心代码。30minAK。Leadershttp://usaco.org/current/index.......
  • IMPROVED TRAINING OF PHYSICS-INFORMED NEURAL NETWORKS WITH MODEL ENSEMBLES
      未发表本篇文献的思路比较简单,类似于一种蔓延式的学习,但是本文不同的是利用了多个PINN进行辅助选点。类似的工作以前看过几篇,但本片文献一个显著的缺点是计算力非常......
  • USACO2023 Bronze 题解
    Problem1.Leaders\(\mathcal{Farmer\John}\)共有\(n\)头奶牛,品种用字符\(\mathsf{G}\)或\(\mathsf{H}\)表示。每一头牛有一个管辖区间\([i,E_i]\)称一头......
  • Theory-guided physics-informed neural networks for boundary layer problems with
    JCP2023  这篇文章聚焦了PINN在处理奇异摄动问题时所面临的困难。(用不同的分支网络去表示内部区域和外部区域中边界层问题的不同阶数的近似)。但本文所提出的方法计算......