2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II）

93 阅读 0 评论 62 点赞

我是靠谱客的博主飘逸嚓茶，最近开发中收集的这篇文章主要介绍2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

D：AtCoder Grand Contest 012 Splatter Painting

题目描述

Squid喜欢在图中为一些顶点染色(毕竟是鱿鱼 )

现在有一张由 N 个顶点和 M 条边组成的简单无向图，其中顶点编号为1到 N。我们用数字来编号各种颜
色。
一开始，所有的顶点都会被染成颜色0 。第 i 条双向边连接着两个端点a[i] 和 b[i]。每条边的长度都是单位1。

Squid 会在这张图上进行Q 次操作。其中对于第 i次操作，他(它？？？)会将与顶点 v[i] 相距 d[i] (包括v[i] )的所有点重新染色成颜色c[i].

请问 Q 次操作后，每个顶点的颜色各是什么。

输入格式

N M
a₁ b₁
:
a_M b_M
Q
v₁ d₁ c₁
:
v_Q d_Q c_Q

输出格式

答案一共 N 行。在第 i 行中，在Q 操作之后输出顶点 i 的颜色。

因为已染色的点不再重复染色，所以从第 Q 次操作往前模拟，每次操作如果找到的点已被染色就不再重复染，并考虑若已经处理过从v点出发而d更大的染色操作，则这一次操作必定无效，可以return掉。

code：

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define pr(x) printf("%dn", x)
#define lowbit(x) (x & -x)
#define ll long long
#define N 100010
using namespace std;
int n, m, col[N], tot = 0, head[N], maxx[N], q;
struct Xiao
{
	int next, to;
}e[N * 2];
struct Wang
{
	int v, d, c;
}qvq[N];
inline void add(int x, int y)
{
	e[++tot].next = head[x];
	e[tot].to = y;
	head[x] = tot;
}
inline void dfs(int d, int sc, int x, int fa)
{
	if (d <= maxx[x]) return;
	maxx[x] = d;
	if (col[x] == 0) col[x] = sc;
	for (int i = head[x]; i; i = e[i].next)
	{
		int y = e[i].to;
		if (y == fa) continue;
		dfs(d - 1, sc, y, x);
	}
}
int main()
{
	sc(n);
	sc(m);
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		sc(a);
		sc(b);
		add(a, b);
		add(b, a);
	}
	sc(q);
	for (int i = 1; i <= q; i++)
	{
		sc(qvq[i].v);
		sc(qvq[i].d);
		sc(qvq[i].c);
	}
	memset(maxx, -1, sizeof maxx);
	for (int i = q; i >= 1; i--)
	dfs(qvq[i].d, qvq[i].c, qvq[i].v, 0);
	for (int i = 1; i <= n; i++)
	printf("%dn", col[i]);
	return 0;
}

E：codeforces 567 E President and Roads

题目大意

有 n 个点，m 条边，询问每一条边是否在 S —T 最短路上，如果一定在最短路上，输出 YES ；如果边权减去 x 后一定在最短路上，则输出 CAN x，（边权不能变成非正数）；如果一定无法在最短路上则输出NO

输入格式

第一行给四个数 n, m, S, T 接下来 m 行每行 a, b, l表示 a 和 b 之间有一个长为 l 的边

输出格式

m 行，第 i 行为第 i 条边的情况

dijkstra + tarjan判割边

从起点终点分别出发做一遍最短路，判断一下每一条边是否在最短路上，重新构图，判割边

枚举每一条边，如果为割边，直接输出YES

否则，如果是在最短路上，且边长>1,输出CAN 1

若边长<=1,输出NO

如果不是在最短路上，就让这条边减小，使它在最短路上，如果边权能为正数，输出CAN x，否则输出NO

code

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define pr(x) printf("%dn", x)
#define lowbit(x) (x & -x)
#define ll long long
#define N 200010
using namespace std;
int tot = 0, tott = 0, head[N][3], vis[N], dfn[N], low[N], n, m, s, t;
int num = 0, p[N];
ll d[2][N];
bool br[N];
struct Xiao
{
	int next, to, w;
}e[2][N * 2];
struct Wang
{
	int x, y, z;
}er[N];
inline void add1(int x, int y, int z)
{
	e[0][++tot].next = head[x][0];
	e[0][tot].to = y;
	e[0][tot].w = z;
	head[x][0] = tot;
} 
inline void add2(int x, int y, int z)
{
	e[1][++tott].next = head[x][1];
	e[1][tott].to = y;
	e[1][tott].w = z;
	head[x][1] = tott;
}
inline void dijkstra(int k)
{
	priority_queue < pair <ll, int> > q;
	while (q.size()) q.pop();
	memset(d[k], 0x3f, sizeof d[k]);
	memset(vis, 0, sizeof vis);
	if (k == 0) 
	{
		d[0][s] = 0;
		q.push(make_pair(0, s));
	}
	else
	{
		d[1][t] = 0;
		q.push(make_pair(0, t));
	}
	while (q.size())
	{
		int x = q.top().second;
		q.pop();
		vis[x] = 1;
		for (int i = head[x][k]; i; i = e[k][i].next)
		{
			int y = e[k][i].to;
			int z = e[k][i].w;
			if (vis[y]) continue;
			if (d[k][y] > d[k][x] + z)
			{
				d[k][y] = d[k][x] + z;
				q.push(make_pair(-d[k][y], y));
			}
		}
	}
}
inline void tarjan(int x, int eg)
{
	dfn[x] = low[x] = ++num;
	for (int i = head[x][0]; i; i = e[0][i].next)
	{
		int y = e[0][i].to;
		if (!dfn[y])
		{
			tarjan(y, i);
			low[x] = min(low[x], low[y]);
			if (low[y] > dfn[x]) br[i] = br[i ^ 1] = true;
		}
		else
		{
			if (i != (eg ^ 1)) low[x] = min(low[x], dfn[y]);
		}
	} 
}
int main()
{
	sc(n);
	sc(m);
	sc(s);
	sc(t);
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		sc(x);
		sc(y);
		sc(z);
		er[i].x = x;
		er[i].y = y;
		er[i].z = z;
		add1(x, y, z);
		add2(y, x, z);
	}
	dijkstra(0);
	dijkstra(1);
	tot = 1;
	memset(head, 0, sizeof head);
	for (int i = 1; i <= m; i++)
	{
		if (d[0][er[i].x] + d[1][er[i].y] + er[i].z == d[1][s])
		{
			add1(er[i].x, er[i].y, er[i].z);
			add1(er[i].y, er[i].x, er[i].z);
			p[i] = tot;
		}
	}
	memset(br, false, sizeof br);
	memset(dfn, 0, sizeof dfn);
	for (int i = 1; i <= n; i++)
	if (!dfn[i]) tarjan(i, 0);
	for (int i = 1; i <= m; i++)
	{
		if (br[p[i]]) printf("YESn");
		else
		{
			if (d[0][er[i].x] + d[1][er[i].y] + er[i].z == d[1][s])
			{
				if (er[i].z > 1) printf("CAN 1n");
				else printf("NOn");
			}
			else
			{
				ll dis = d[0][t] - d[0][er[i].x] - d[1][er[i].y] - 1;
                if (dis <= 0) printf("NOn");
                else printf("CAN %lldn", er[i].z - dis);
			}
		}
	}
	return 0;
}

F：codeforces 1205 B Shortest Cycle

已知 n 个整数a₁, a₂,…,a_n 。考虑为图上的 n个节点，其中 i,j (i != j )相互连接仅当a_i & a_j != 0 时，其中& 表示按位与运算。

求出这个图中最短环的长度，如果没有环，输出-1 。

由数据范围可以知道，a_i的二进制最多有64位，那么根据鸽巢原理，如果有>128个数不为0，那么必定有三个数与运算后不等于0，直接输出3

否则建图，用Floyd求最小环

code

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define pr(x) printf("%dn", x)
#define lowbit(x) (x & -x)
#define ll long long
#define N 100010
#define memset(x) memset(x, 0, sizeof(x))
using namespace std;
int minn, cnt, dis[250][250], mp[250][250], n;
ll a[N];
int inf = 1e8 + 10;
inline void build()
{
	for (int i = 1; i <= cnt; i++)
	for (int j = 1; j <= cnt; j++)
	if (i != j) mp[i][j] = dis[i][j] = inf;
	for (int i = 1; i <= cnt; i++)
	for (int j = i + 1; j <= cnt; j++)
	if (a[i] & a[j]) mp[i][j] = mp[j][i] = dis[i][j] = dis[j][i] = 1;
}
inline void floyd()
{
	minn = inf;
	for (int k = 1; k <= cnt; k++)
	{
		for (int i = 1; i < k; i++)
		for (int j = i + 1; j < k; j++)
		minn = min(minn, dis[i][j] + mp[i][k] + mp[k][j]);//更新k点之前枚举ij求经过ijk的最小环
		for (int i = 1; i <= cnt; i++)
		for (int j = 1; j <= cnt; j++)
		dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);//更新k点
	}
}
int main()
{
	sc(n);
	cnt = 0;
	ll x;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &x);
		if (x != 0) a[++cnt] = x;
	}
	if (cnt >= 130) printf("3n");
	else
	{
		build();
		floyd();
		if (minn > n) puts("-1");
		else printf("%dn", minn);
	}
	return 0;
}

G：codeforces gym 101257 F ISlands II

给出一个n*m的地图，上面相同数字的代表一个国家，问对于每个国家有多少个国家在它内部（即被包围）。例如第一个样例，1包围2，2包围3，所以1包围2和3,2包围3。

对于每一个点，如果它下面的那个点和右边的点与它颜色不同，就以颜色为节点连边，在最外面再加一圈0

如果一个点为割点，它的子树中的节点一定在它内部

code

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define pr(x) printf("%dn", x)
#define lowbit(x) (x & -x)
#define ll long long
#define N 1000010
using namespace std;
int tot = 0, head[N], size[N], low[N], dfn[N], n, m; 
int v[N], ans[N], cnt = 0, num = 0, a[1010][1010], v1[N];
struct Xiao
{
	int next, to;
}e[N * 8];
inline void add(int x, int y)
{
	e[++tot].next = head[x];
	e[tot].to = y;
	head[x] = tot;
}
inline void dfs(int x)
{
	size[x] = 1;
	if (x > cnt) cnt = x;
	v[x] = 1;
	for (int i = head[x]; i >= 0; i = e[i].next)
	{
		int y = e[i].to;
		if (v[y]) continue;
		dfs(y);
		size[x] += size[y];
	}
}
inline void tarjan(int x, int fa)
{
	dfn[x] = low[x] = ++num;
	v1[x] = 1;
	for (int i = head[x]; i >= 0; i = e[i].next)
	{
		int y = e[i].to;
		if (y == fa) continue;
		if (!dfn[y])
		{
			tarjan(y, x);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) ans[x] += size[y];
		}
		else if (v1[y]) low[x] = min(low[x], dfn[y]);
	}
}
int main()
{
	sc(n);
	sc(m);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++)
	sc(a[i][j]);
	memset(head, -1, sizeof head);
	for (int i = 0; i <= n; i++)
	for (int j = 0; j <= m; j++)
	{
		if (a[i][j] != a[i + 1][j]) add(a[i][j], a[i + 1][j]), add(a[i + 1][j], a[i][j]);
		if (a[i][j] != a[i][j + 1]) add(a[i][j], a[i][j + 1]), add(a[i][j + 1], a[i][j]);
	}
	dfs(0);
	tarjan(0, -1);
	for (int i = 1; i <= cnt; i++)
	printf("%d ", ans[i]);
	return 0;
}

最后

以上就是飘逸嚓茶为你收集整理的2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II）的全部内容，希望文章能够帮你解决2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：图论
浏览次数：93 次浏览
发布日期：2023-09-03 03:35:49
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_10_fx_13_z_18_4.html

AtCoder刷题记录ARC066C Addition and Subtraction HardAGC033C Removing CoinsAGC014D Black and White TreeARC063F Snuke's Coloring 2ARC068F SolitaireARC078F Mole and Abandoned MineAGC001F Wide SwapAGC003D AnticubeAGC003E Sequential operations on SequenceAGC0

2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II）

概述

D：AtCoder Grand Contest 012 Splatter Painting

题目描述

输入格式

输出格式

code：

E：codeforces 567 E President and Roads

题目大意

输入格式

输出格式

code

F：codeforces 1205 B Shortest Cycle

code

G：codeforces gym 101257 F ISlands II

code

最后

评论列表共有 0 条评论

发表评论取消回复

2019.11.2图论专题（AtCoder Splatter Painting、President and Roads、Shortest Cycle、ISlands II）

概述

D：AtCoder Grand Contest 012 Splatter Painting

题目描述

输入格式

输出格式

code：

E：codeforces 567 E President and Roads

题目大意

输入格式

输出格式

code

F：codeforces 1205 B Shortest Cycle

code

G：codeforces gym 101257 F ISlands II

code

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复