首页 > 其他分享 >2024.3.23 笔记（Tarjan）

2024.3.23 笔记（Tarjan）

时间：2024-03-23 14:12:54浏览次数：20  
标签：Tarjan 2024.3 idx 23 int cnt ++ dfn low

P3469 [POI2008] BLO-Blockade

根据割点的定义，若节点 \(i\) 不是割点，则把节点 \(i\) 关联的所有边去掉之后，只有 \(i\) 与其他 \(n - 1\) 个节点不连通，而其他 \(n - 1\) 个节点之间是连通的。注意：题目求的是有序点对，即 \((x, y)\) 和 \((y, x)\) 算不同的点对，故此时答案是 \(2 * (n - 1)\)

若节点 \(i\) 是割点，则把节点 \(i\) 关联的所有边去掉之后，图会分成若干个连通块，我们应该求出这些连通块的大小，两两相乘再相加。

假设节点 \(i\) 的子节点集合中，有 \(t\) 个子节点 \(s[k]\)，满足 \(dfn[i] <= low[s[k]]\)，那么删除节点 \(i\) 关联的所有边后，无向图最多分成 \(t + 2\) 个连通块，情况一共分为 $ 3$ 类：

    1. 节点 \(i\) 自身单独构成一个连通块
    1. 有 \(t\) 个连通块，分别由搜索树上以 \(s[k]\) 为根节点的子树中的节点构成
    1. 还可能有一个连通块，由除了上述节点之外的所有点构成

因此可以在 \(Tarjan\) 算法求割点的过程中顺便求一下 \(cnt[x]\)，即以节点 \(x\) 为根节点的子树中的节点个数。

因此删掉割点 \(i\) 之后，不连通的有序点对数量为：

\(cnt[s[1]] * (n - cnt[s[1]]) + cnt[s[2]] * (n - cnt[s[2]]) + ... + cnt[s[n]] * (n - cnt[s[n]]) + 1 * (n - 1) + (n - 1 - sum(cnt[s[k]])) * (1 + sum(cnt[s[k]])) (1 <= k <= t)\)

int n, m, num;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], size[N];
int ans[N];
bool cut[N];

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int x) 
{
	dfn[x] = low[x] = ++num;
	size[x] = 1;
	int flag = 0, sum = 0;
	for (rint i = h[x]; i; i = ne[i]) 
	{
		int y = e[i];
		if (!dfn[y]) 
		{
			tarjan(y);
			size[x] += size[y];
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) 
			{
				flag++;
				ans[x] += size[y] * (n - size[y]);
				sum += size[y];
				if (x != 1 || flag > 1) cut[x] = 1;
			}
		} 
		else 
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (cut[x])
		ans[x] += (n - sum - 1) * (sum + 1) + (n - 1);
	else
		ans[x] = 2 * (n - 1);
}

signed main() 
{
	cin >> n >> m;
	idx = 1;
	for (rint i = 1; i <= m; i++) 
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	tarjan(1);
	for (rint i = 1; i <= n; i++)
	{
		cout << ans[i] << endl;
	}
	return 0;
}

AcWing.364 网络

先求出所有边双连通分量，再对每个连通分量进行缩点，得到一颗新的树，最开始，树中边的数量就是桥的数量。

依次考虑每个添加边 \((x, y)\) 的操作，若 \(x, y\) 属于同一个连通分量，桥的数量不变。

设 \(c[x]\) 表示节点 \(x\) 所在的连通分量编号。

若不属于同一个连通分量，则 \(c[x]\) 与 \(c[y]\) 之间的路径上的每条边都不再是桥，因为他们都处在一个环内。

可以求出 \(p = lca(c[x], c[y])\)，从 \(c[x]\) 不断走向父节点，直到 $ p$，把经过的边都标记成不再是桥。同样，从 \(c[y]\) 不断走向父节点，直到 \(p\)，把经过的边都标记成不在是桥。途中若有 \(cnt\) 条边新获得印记，则把途中桥的总数减掉 \(cnt\)

这样这道题的时间复杂度就是 \(O(m + q * n)\)，已经够了。当然这里还能再做一步优化。

用并查集对不在是桥的边进行路径压缩，时间复杂度降为 \(O(m + q * logn)\)

int h[N], e[M], ne[M], idx;
int hc[N], ec[M], nc[M], tc;
int dfn[N], low[N], c[N];
int n, m, q, num, dcc, ans, T;
int fa[N]/*并查集中的父节点*/, d[N], go[N]/*缩点之后的树上的父节点*/;
bool bridge[M];

void add(int a, int b) 
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
void add_c(int a, int b)
{
	ec[++tc] = b, nc[tc] = hc[a], hc[a] = tc;
}

void tarjan(int x, int in_edge) 
{
	dfn[x] = low[x] = ++num;
	for (rint i = h[x]; i; i = ne[i]) 
	{
		int y = e[i];
		if (!dfn[y]) 
		{ // 树边
			tarjan(y, i);
			low[x] = min(low[x], low[y]);
			if (dfn[x] < low[y]) bridge[i] = bridge[i ^ 1] = 1;
		} 
		else if (i != (in_edge ^ 1))
		{
			low[x] = min(low[x], dfn[y]);			
		}
	}
}

void dfs(int x)
 {
	c[x] = dcc;
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (!bridge[i] && !c[y]) 
		{
			dfs(y);
		}
	}
}

void dfs_c(int x)
{
	for (rint i = hc[x]; i; i = nc[i])
	{
		int y = ec[i];
		if (!d[y]) 
		{
			d[y] = d[x] + 1;
			go[y] = x;
			dfs_c(y);
		}
	}
}

int find(int x) 
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void calc(int x, int y) 
{
	x = find(x);
	y = find(y);
	while (x != y) 
	{
		if (d[x] < d[y]) swap(x, y);
		if (x == 1) break;
		// x到go[x]的边从桥边变为非桥边
		fa[x] = find(go[x]);
		ans--;
		x = find(x);
	}
}

signed main() 
{
	while (cin >> n >> m && n) 
	{
		m(h), m(dfn), m(bridge), m(c), m(hc), m(d);
		idx = tc = 1;
		dcc = 0;
		for (rint i = 1; i <= m; i++) 
		{
			int a, b;
			cin >> a >> b;
			add(a, b);
			add(b, a);
		}
		
		tarjan(1, 0);
		for (rint i = 1; i <= n; i++)
		{
			if (!c[i]) 
			{
				++dcc;
				dfs(i);
			}			
		}
			
		for (rint i = 2; i <= idx; i++) 
		{
			int x = e[i ^ 1], y = e[i];
			if (c[x] == c[y]) continue;
			add_c(c[x], c[y]);
			add_c(c[y], c[x]);
		}
		ans = dcc - 1;
		d[1] = 1;
		dfs_c(1);
		for (rint i = 1; i <= dcc; i++) fa[i] = i;
		printf("Case %lld:\n", ++T);
		cin >> q;
		for (rint i = 1; i <= q; i++) 
		{
			int a, b;
			cin >> a >> b;
			a = c[a], b = c[b];
			calc(a, b);
			cout << ans << endl;
		}
		puts("");
	}
	return 0;
}

SP2878 KNIGHTS

建立一个原图的补图，\(n\) 个节点代表 \(n\) 个骑士，若两名骑士没有憎恨关系，则两者之间连一条无向边。

根据题意，若干名骑士可以召开圆桌会议的条件是：他们对应的节点组成一个长度为奇数的简单环(简称奇环)。因此本题就是求多少个点不被任何奇环包含，这些点就是应该被踢掉的骑士。

若两个骑士属于两个不同的点双连通分量，则它们不可能一起出席会议(在同一个奇环中)

若某个点双连通分量中存在奇环，则这个点双连通分量中所有点都被至少一个奇环包含。

用 \(Tarjan\) 算法求出补图中所有的点双连通分量，判定每个点双连通分量中是否存在奇环即可。若存在奇环，则该点双连通分量中的所有骑士都可以参加会议(都在某个奇环中)。

奇环可以用染色法进行判断。一张无向图没有奇环，等价于它是一张二分图。

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], stk[N];
int c[N], v[N], able[N];
int n, m, num, top, cnt, now;
bool hate[N][N], flag;
vector<int> dcc[N];

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int x, int root) 
{
	dfn[x] = low[x] = ++num;
	stk[++top] = x;
	if (x == root && h[x] == 0) 
	{ 
		dcc[++cnt].push_back(x);
		return; 
	}
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y]) 
		{
			tarjan(y, root);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) 
			{
				cnt++;
				int z;
				do 
				{
					z = stk[top--];
					dcc[cnt].push_back(z);
				} while (z != y);
				dcc[cnt].push_back(x);
			}
		} 
		else
		{
			low[x] = min(low[x], dfn[y]);
		} 
	}
}

void dfs(int x, int color) 
{
	c[x] = color;
	for (rint i = h[x]; i; i = ne[i]) 
	{
		int y = e[i];
		if (v[y] != now) continue;
		if (c[y] && c[y] == color) 
		{
			flag = 1;
			return;
		}
		if (!c[y]) dfs(y, 3 - color);
	}
}

signed main()
{
	while (cin >> n >> m && n) 
	{
		m(h), m(dfn), m(able), m(v);
		for (rint i = 1; i <= n; i++) dcc[i].clear();
		idx = 1;
		num = top = cnt = 0;
		for (rint i = 1; i <= n; i++)
			for (rint j = 1; j <= n; j++)
			    hate[i][j] = 0;
		for (rint i = 1; i <= m; i++) 
		{
			int a, b;
			cin >> a >> b;
			if (a == b) continue;
			hate[a][b] = hate[b][a] = 1;
		}
		// 建补图
		for (rint i = 1; i < n; i++)
			for (rint j = i + 1; j <= n; j++)
				if (!hate[i][j]) 
				    add(i, j), add(j, i);
		// 求点双连通分量
		for (rint i = 1; i <= n; i++)
			if (!dfn[i]) 
			    tarjan(i, i);
		// 判断每个点双是否包含奇环
		for (rint i = 1; i <= cnt; i++) 
		{
			now = i;
			for (rint j = 0; j < (int)dcc[i].size(); j++)
			{
				v[dcc[i][j]] = now;
				c[dcc[i][j]] = 0;
			}
			flag = 0;
			dfs(dcc[i][0], 1);
			if (flag)
				for (rint j = 0; j < (int)dcc[i].size(); j++)
					able[dcc[i][j]] = 1;
		}
		int ans = 0;
		for (rint i = 1; i <= n; i++)
			if (!able[i]) 
			    ans++;
		cout << ans << endl;
	}
	return 0;
}

P6066 [USACO05JAN] Watchcow S

本题求的是一条每条边来回走两次的欧拉回路。只需要在求欧拉回路模板的基础上去掉边的判重标记即可。

因为本来就存储了正向边、反向边，判重是为了让一条边不来回走两次，如果不判重，那么就会将所有边都走一遍，即每条边来回走两次

由于欧拉回路的递归层数和边的数量有关，边数过大会造成栈溢出，一般采用另一个栈模拟机器的递归过程

int h[N], e[M], ne[M], idx;
int stk[N], ans[N]; 
bool vis[N];
int n, m, top, cnt;

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void euler() 
{
	stk[++top] = 1;
	while (top > 0) 
	{
		int x = stk[top], i = h[x];
		// 找到一条尚未访问的边
		while (i && vis[i]) i = ne[i];
		// 沿着这条边模拟递归过程，标记该边，并更新表头
		if (i) 
		{
			stk[++top] = e[i];
			h[x] = ne[i];
			// vis[i] = vis[i ^ 1] = true;
		}
		// 与x相连的所有边均已访问，模拟回溯过程，并记录
		else 
		{
			top--;
			ans[++cnt] = x;
		}
	}
}

signed main() 
{
	cin >> n >> m;
	idx = 1;
	for (rint i = 1; i <= m; i++) 
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	euler();
	for (rint i = cnt; i; i--) cout << ans[i] << endl;
	return 0;
}

P2746 [USACO5.3] 校园网

使用 \(Tarjan\) 算法求出所有强连通分量，并统计出所有强连通分量中入度和出度为
\(0\) 的个数，分别为 \(a\) 和 \(b\)。

第一问：入度为 \(0\) 强连通分量就是缩点后拓扑图的起点，有多少个起点就需要至少给多少个学校传递新软件，所以答案就是 \(a\)

第二问：答案为 \(max(a,b)\)。特判图中只有一个强连通分量时不需要加边，答案为 \(0\)

复杂度 \(O(n+m)\)

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], c[N], s[N];
int n, num, top, cnt;
int in[N], out[N];
bool ins[N];

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}

void tarjan(int x) 
{
	low[x] = dfn[x] = ++num;
	s[++top] = x;
	ins[x] = 1;
	for (rint i = h[x]; i; i = ne[i]) 
	{
		int y = e[i];
		if (!dfn[y]) 
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} 
		else if (ins[y])
		{
			low[x] = min(low[x], dfn[y]);			
		}
	}
	if (dfn[x] == low[x]) 
	{
		cnt++; // 找到了一个SCC
		int y;
		do 
		{
			y = s[top--];
			ins[y] = false;
			c[y] = cnt;
			// scc[cnt].push_back(y);
		} while (x != y);
	}
}

signed main() 
{
	cin >> n;
	for (rint i = 1; i <= n; i++) 
	{
		int j;
		while (scanf("%lld", &j), j) add(i, j);
	}
	for (rint i = 1; i <= n; i++)
		if (!dfn[i]) 
		    tarjan(i);
	for (rint x = 1; x <= n; x++)
		for (rint i = h[x]; i; i = ne[i]) 
		{
			int y = e[i];
			if (c[x] == c[y]) continue;
			// 缩点后从c[x]到c[y]的有向边
			in[c[y]]++;
			out[c[x]]++;
		}
	int zero_in = 0;
	int zero_out = 0;
	for (rint i = 1; i <= cnt; i++) 
	{
		if (!in[i]) zero_in++;
		if (!out[i]) zero_out++;
	}
	cout << zero_in << endl;
	cout << (cnt == 1 ? 0 : max(zero_in, zero_out)) << endl;
	return 0;
}

AcWing.368 银河

首先，会想到差分约束系统，这样，就可以在图中方便地表示关系了。

如果使用 \(spfa\)，由于所有点的亮度最小是 \(1\)（需要进行初始化），并且所有的点并不一定连通（要全部添加队列），因此可以整一个“超级原点”，到所有的点都会有边，并且边的权值是 \(1\)

有一个问题就是数据太过于大，并不可以使用 spfa 来进行求解。

拓扑排序，但是拓扑排序是针对有向无环图的。

在题目中有关键的一点，如果要是有一个环，那么环上的一定是相等的，如果有一个不相等，那么就不符合条件。

所以可以采用求出强连通分量，并且缩点。如果强连通分量上的边的权值不是 \(0\)，那么就不合法。

然后进行拓扑排序

复杂度 \(O(n+m)\)

int h[N], w[M], e[M], ne[M], idx;
int hc[N], wc[M], ec[M], nc[M], tc;
int dfn[N], low[N], c[N], stk[N];
int n, m, num, top, cnt;
int in[N], d[N];
bool ins[N];
queue<int> q;

void add(int a, int b, int c)
{
	e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}

void add_c(int a, int b, int c) 
{
	ec[++tc] = b, wc[tc] = c, nc[tc] = hc[a], hc[a] = tc, in[b]++;
}

void tarjan(int x) 
{
	low[x] = dfn[x] = ++num;
	stk[++top] = x;
	ins[x] = 1;
	for (rint i = h[x]; i; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y]) 
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} 
		else if (ins[y])
		{
			low[x] = min(low[x], dfn[y]);			
		}
	}
	if (dfn[x] == low[x]) 
	{
		cnt++; // 找到了一个SCC
		int y;
		do 
		{
			y = stk[top--];
			ins[y] = 0;
			c[y] = cnt;
		} while (x != y);
	}
}

void topsort() 
{
	q.push(c[0]);
	while (!q.empty()) 
	{
		int x = q.front();
		q.pop();
		for (rint i = hc[x]; i; i = nc[i]) 
		{
			int y = ec[i];
			d[y] = max(d[y], d[x] + wc[i]);
			if (--in[y] == 0) q.push(y);
		}
	}
}

signed main() 
{
	cin >> n >> m;
	for (rint i = 1; i <= m; i++) 
	{
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) add(x, y, 0), add(y, x, 0);
		else if (z == 2) add(x, y, 1);
		else if (z == 3) add(y, x, 0);
		else if (z == 4) add(y, x, 1);
		else add(x, y, 0);
	}
	for (rint i = 1; i <= n; i++) add(0, i, 1);
	
	for (rint i = 0; i <= n; i++)
		if (!dfn[i]) 
		    tarjan(i);
		    
	for (rint x = 0; x <= n; x++)
	{
		for (rint i = h[x]; i; i = ne[i]) 
		{
			int y = e[i];
			if (c[x] == c[y]) 
			{
				if (w[i] == 1) 
				{
					puts("-1");
					return 0;
				}
				continue;
			}
			// 缩点后从c[x]到c[y]的有向边
			add_c(c[x], c[y], w[i]);
		}		
	}

	topsort();
	
	int ans = 0;
	for (rint i = 1; i <= n; i++) ans += d[c[i]];
	cout << ans << endl;
	
	return 0;
}

AcWing.369 北大ACM队的远足

本题求的是最小危险程度，即最小步行经过的桥的长度

首先一定会经过的桥就是有向图的必经桥，因此我们要让必经桥的长度和最小。

首先可以求出从 \(S\) 到 \(T\) 的最短路，然后考虑在最短路的什么地方搭车能让危险程度最小。

如果只有一个区间，那么可以用双指针的方式扫描得出最小危险程度，\(ds[i]\) 表示从 \(S\) 到最短路上的第 \(i\) 个节点只搭一次车
的最小危险程度。

然后我们可以反着再求一遍，\(dt[i]\) 表示从最短路上第 \(i\) 个节点到 \(T\) 只搭一次车的最小危险程度。

然后枚举每个点 \(i\)，用 \(ds[i] + dt[i]\) 更新答案。

这里我们还漏了一种情况，就是当两个区间相连成为一个长度为 \(2q\) 的区间，这里可以直接用长度为 \(2q\) 的区间再扫描一遍更新答案。

const int N = 1e5 + 5;
const int M = 2e6 + 5;
const int mod = 1e9 + 7;

int n, m, s, t, bus;
int e[M], w[M], ne[M], h[N], idx;
int f[2][N], deg[2][N], d[N], pre[N];
bool bridge[M];
int a[N], b[N], cnt; // 长度、是不是桥
int sum[N], sum_bri[N], ds[N], dt[N], ds_min[N];
int occur[N], first_occur[N];
queue<int> q;

void add(int a, int b, int c)
{
	e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; 
}

void topsort(int s, int bit) 
{
	if (!bit) 
	{ // 只有正图需要求最短路
		memset(d, 0x3f, sizeof d);
		d[s] = 0;
	}
	f[bit][s] = 1;
	for (rint i = 1; i <= n; i++)
		if (!deg[bit][i]) 
		    q.push(i);
	while (!q.empty()) 
	{
		int x = q.front();
		q.pop();
		for (rint i = h[x]; i; i = ne[i])
		{
			if ((i & 1) == bit) 
			{
				int y = e[i];
				f[bit][y] = (f[bit][y] + f[bit][x]) % mod; // 路径条数
				if (bit == 0 && d[y] > d[x] + w[i]) 
				{  // 最短路
					d[y] = d[x] + w[i];
					pre[y] = i;
				}
				if (--deg[bit][y] == 0) q.push(y);
			}			
		}
	}
}

signed main() 
{
	int T;
	cin >> T;
	while (T--) 
	{
		m(h), m(deg), m(f), m(bridge), m(occur);
		idx = 1;
		cnt = 0;
		cin >> n >> m >> s >> t >> bus;
		s++;
		t++;
		for (rint i = 1; i <= m; i++) 
		{
			int x, y, z;
			cin >> x >> y >> z;
			x++, y++;
			add(x, y, z); // 偶数边是正边（邻接表2, 4, 6,...位置）
			add(y, x, z); // 奇数边是反边
			deg[0][y]++; // 入度
			deg[1][x]++; // 出度
		}
		topsort(s, 0);
		if (!f[0][t]) 
		{
			puts("-1");
			continue;
		}
		topsort(t, 1);
		for (rint i = 2; i <= idx; i += 2) 
		{
			int x = e[i ^ 1], y = e[i];
			if (f[0][x] * f[1][y] % mod == f[0][t]) 
			{
				bridge[i] = 1;
			}
		}
		// O(M)判重边，用map可能超时
		for (rint x = 1; x <= n; x++) 
		{
			for (rint i = h[x]; i; i = ne[i]) 
			{
				if (i & 1) continue; // 只考虑正边
				int y = e[i];
				if (occur[y] == x) 
				{
					bridge[i] = 0;
					bridge[first_occur[y]] = 0;
				} 
				else 
				{
					occur[y] = x;
					first_occur[y] = i;
				}
			}
		}
		while (t != s) 
		{
			a[++cnt] = w[pre[t]];
			b[cnt] = bridge[pre[t]];
			t = e[pre[t] ^ 1];
		}
		// reverse(a + 1, a + cnt + 1); 不反过来也可以
		// reverse(b + 1, b + cnt + 1);
		for (rint i = 1; i <= cnt; i++) 
		{
			sum[i] = sum[i - 1] + a[i]; // 以i这条边为结尾（包含i）的前缀总长度
			sum_bri[i] = sum_bri[i - 1] + (b[i] ? a[i] : 0);
		}
		ds_min[0] = 1 << 30;
		for (rint i = 1, j = 0; i <= cnt; i++) 
		{ // 恰好在i这条边的结尾处下车，前面的最小危险程度：ds[i]
			// 双指针扫描，让j+1~i这些边乘车，j这条边有可能部分乘车
			while (sum[i] - sum[j] > bus) j++;
			ds[i] = sum_bri[j];
			if (j > 0 && b[j]) ds[i] -= min(a[j], bus - (sum[i] - sum[j]));
			ds_min[i] = min(ds[i], ds_min[i - 1] + (b[i] ? a[i] : 0)); // i之前搭一次车：ds_min[i]，即书上的"ds[i]"
		}
		for (rint i = cnt, j = cnt + 1; i; i--) 
		{ // 恰好在i这条边的开头处上车，后面的最小危险程度：ds[i]
			// 双指针扫描，让i~j-1这些边乘车，j这条边有可能部分乘车
			while (sum[j - 1] - sum[i - 1] > bus) j--;
			dt[i] = sum_bri[cnt] - sum_bri[j - 1];
			if (j <= cnt && b[j]) dt[i] -= min(a[j], bus - (sum[j - 1] - sum[i - 1]));
		}
		// 两段乘车分开的情况
		int ans = 1 << 30;
		for (rint i = 1; i <= cnt; i++) ans = min(ans, dt[i] + ds_min[i - 1]);
		// 两段乘车接在一起，2*bus覆盖一次的情况
		for (rint i = 1, j = 0; i <= cnt; i++) 
		{
			while (sum[i] - sum[j] > 2 * bus) j++;
			int temp = sum_bri[j];
			if (j > 0 && b[j]) temp -= min(a[j], 2 * bus - (sum[i] - sum[j]));
			ans = min(ans, temp + sum_bri[cnt] - sum_bri[i]);
		}
		cout << ans << endl;
	}
	return 0;
}

标签：Tarjan,2024.3,idx,23,int,cnt,++,dfn,low
From： https://www.cnblogs.com/spaceswalker/p/18091048

相关文章

  • Linux操作系统学习2024.03.23
    Linux操作系统学习目标2024.03.23一.操作系统1.1作用：主要作用是管理好硬件设备，并为用户和应用程序提供一个简单的接口，以便于使用，作为中间人，连接软件和硬件。1.2不同应用领域的主流操作程序·桌面操作系统：1.Windows系列2.macOS3.Linux·服务器操作系统：1.Linux2.Windows......
  • CrossOver 23 用户可以免费升级到 CrossOver24吗？CrossOver用户如何升级呢？
    也就是上个月（2024年2月底）左右，CrossOver刚刚更新了24版本，CrossOver更新的内容有哪些，大家可以参考这篇文章：CrossOver24.0新功能介绍，这篇文章详细介绍了CrossOver24有哪些新特点，我想也满足了各位大佬的需求了吧，但是身为CrossOver23的用户，该怎么用上CrossOver24呢。难道我要重新......
  • SpringBoot 面向面试学习（2023.03.23更新）
    导语在网上找了很多SpringBoot相关的教程，要么是针对初学者面向实战入门的视频，要么基于面试但存在收费或不全面的问题……因此参考网上博客特此总结了一些可能常见的面试题，循序渐进，以问题为导向，以面试为场景进行学习/复习。JavaGuide提供的Spring常见面试题总结可以去看，里面......
  • 2024年3月23日
    HelloWorld趁着思路清晰写一下log网络平台很多，这些都是财富、资源，很多东西触手可及，但是作为一个参与者，能够真正使用的确实不怎么多的，我的理念是物尽其用，如果闲置浪费，那就是可耻的，如同垃圾，应当被处理的。一个人的精力总是有限的，或许有奇人轶事，真的能够做到一心多用，可以同时把......
  • #17 2023.3.18
    645.loj4038「SNOI2024」树V图646.loj4039「SNOI2024」矩阵647.loj4040「SNOI2024」拉丁方648.loj4041「SNOI2024」平方数649.loj4042「SNOI2024」公交线路650.loj3903「PA2022」Palindrom651.loj3904「PA2022」WielkiZderzaczTermionów652.loj......
  • 2024-03-23 闲话
    突然思考如果我要写论文，那么intro的background怎么写。仔细分析了一下，发现每篇论文的第一段是大同小异的，所以直接粘过来改改措辞就行了。剩下的motivation就可以自己发挥了。practitionern.执业人员，从业者incaseof以防万一inthecaseof在某种情况下frictio......
  • BUPT 2024 Spring Training #3（ICPC2023 杭州站）Ag复盘
    D-OperatorPrecedence求一个长度为\(2n\)的序列\(a_{2n}\)满足条件\((a_1×a_2)+(a_3×a_4)+\ldots+(a_{2n-1}×a_{2n})=a_1×(a_2+a_3)×\ldots×(a_{2n-2}+a_{2n-1})×a_{2n}\)solution构造题显然找特殊规律。考虑到乘法构造难度大于加法，可以从乘法开始考虑。......
  • CF1923E 一个无需 DSU On Tree 的解法（？
    在地铁上口胡了一下。不知道对不对。考虑记录每一个点\(i\)离他最远的一个祖先使得祖先到\(i\)的路径上没有\(a_i\)。设他为\(\text{lst}_i\)。然后如果两个\(u,v\)的\(\text{lst}\)相等，那么这条路径就是好的。每种颜色枚举即可。八成假了（？），欢迎Hack。PS：全对了，确实能......
  • BZOJ5223-有理有据题
    BZOJ5223-有理有据题题目大意给你\(m\)条线段\((a_i,b_i)\)，再给\(n\)个区间\([l_i,r_i]\)，\(q\)次操作，\(\texttt{Axy}\)添加一条线段\((x,y)\)，其编号为最后一条线段加一。\(\texttt{Cx}\)查询\([l_x,r_x]\)和线段有交集（在边界点也算）的最长编号区间。\(\texttt......
  • 机试重点题-2021/2023
    20215：由二叉树前々序列和中々序列得到后々序列列 #include<iostream>#include<unordered_map>usingnamespacestd;constintN=50010;intn;inta[N],b[N];//前序，中序unordered_map<int,int>p;voidbuild(intal,intar,intbl,intbr){if(al......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99