\(\text{Solution}\)

一个性质：两个 \(K\) 元组有边相连当且仅当每个点在对应的图中到 \(1\) 有奇偶性相同的路径

那么我们就可以预处理每个图中的点到 \(1\) 的奇偶最短路

再考虑路径长度，显然是 \(\min(\max_{i=1}^k{odd_i}, \max_{i=1}^k{even_i})\)

把它拆开 \(\max_{i=1}^k{odd_i} + \max_{i=1}^k{even_i} - \max_{i=1}^k(\max(odd_i,even_i))\)

那么一个点的信息就成了三个

分别算出这三个 \(\max\) 即可

先枚举 \(\max\) 即最大的是多少，那么 \(K\) 元组其他位置就是其他图中小于 \(\max\) 的点的个数乘起来

可以从大枚举 \(\max\)，把点信息为 \(\max\) 先算了，再删去这个点即可，那么就用线段树维护区间积即可，线段树下标表示第 \(i\) 个图剩余点的个数

好处是线段树中剩余的点信息一定小于等于当前枚举的 \(\max\)，避免既要处理图不同又要处理信息大小关系的困境

\(\text{Code}\)

#include <cstdio>

#include <queue>

#include <vector>

#include <iostream>

#include <cstring>

#define re register

#define LL long long

using namespace std;

const int K = 5e4 + 5, N = 2e5 + 5, INF = 0x3f3f3f3f;

LL MOD = 1e9 + 7;

int mx, k, n, m, h[N], tot, total, dis[N][2], col[N], vis[N][2];

vector<int> g[N][3];

struct node{int x, z;};

queue<node> Q;

struct edge{int to, nxt;}e[N << 1];

inline void add(int x, int y)

{

	e[++tot] = edge{y, h[x]}, h[x] = tot;

	e[++tot] = edge{x, h[y]}, h[y] = tot;

}

inline void read(int &x)

{

	x = 0; char ch = getchar();

	while (!isdigit(ch)) ch = getchar();

	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

}

struct Segment{

	#define ls (p << 1)

	#define rs (ls | 1)

	int tr[K << 2]; LL sum[K << 2];

	void build(int p, int l, int r)

	{

		if (l == r) return void(sum[p] = 0);

		int mid = (l + r) >> 1;

		build(ls, l, mid), build(rs, mid + 1, r);

	}

	void update(int p, int l, int r, int x, int v)

	{

		if (x < l || x > r) return;

		if (l == r) return void(sum[p] += v);

		int mid = (l + r) >> 1;

		if (x <= mid) update(ls, l, mid, x, v);

		else update(rs, mid + 1, r, x, v);

		sum[p] = sum[ls] * sum[rs] % MOD;

	}

	LL query(int p, int l, int r, int tl, int tr)

	{

		if (tl > r || tr < l) return 1;

		if (tl <= l && r <= tr) return sum[p];

		int mid = (l + r) >> 1;

		LL res = 1;

		if (tl <= mid) res = query(ls, l, mid, tl, tr);

		if (tr > mid) res = res * query(rs, mid + 1, r, tl, tr) % MOD;

		return res;

	}

}T;

inline void spfa()

{

	for(re int j = 1; j <= n; j++) dis[j][0] = dis[j][1] = INF, vis[j][0] = vis[j][1] = 0;

	dis[1][0] = 0, vis[1][0] = 1, Q.push(node{1, 0});

	while (!Q.empty())

	{

		node now = Q.front(); Q.pop();

		for(re int j = h[now.x]; j; j = e[j].nxt)

		if (dis[e[j].to][now.z ^ 1] > dis[now.x][now.z] + 1)

		{

			dis[e[j].to][now.z ^ 1] = dis[now.x][now.z] + 1;

			if (!vis[e[j].to][now.z ^ 1])

				vis[e[j].to][now.z ^ 1] = 1, Q.push(node{e[j].to, now.z ^ 1});

		}

		vis[now.x][now.z] = 0;

	}

}

inline LL solve(int z)

{

	T.build(1, 1, k);

	for(re int i = mx; i >= 0; i--)

		for(re int j = 0; j < g[i][z].size(); j++) T.update(1, 1, k, col[g[i][z][j]], 1);

	LL res = 0;

	for(re int i = mx; i; i--)

		for(re int j = 0; j < g[i][z].size(); j++)

		{

			int now = g[i][z][j];

			res = (res + T.query(1, 1, k, 1, col[now] - 1) * T.query(1, 1, k, col[now] + 1, k) % MOD * i % MOD) % MOD;

			T.update(1, 1, k, col[now], -1);

		}

	return res;

}

int main()

{

	read(k);

	for(re int i = 1; i <= k; i++)

	{

		tot = 0;

		read(n), read(m);

		for(re int j = 1, x, y; j <= m; j++) read(x), read(y), add(x, y);

		spfa();

		for(re int j = 1; j <= n; j++)

		{

			col[total + j] = i;

			for(re int l = 0; l <= 1; l++)

			if (dis[j][l] ^ INF) g[dis[j][l]][l].push_back(total + j);

			if (max(dis[j][0], dis[j][1]) ^ INF) g[max(dis[j][0], dis[j][1])][2].push_back(total + j);

			if (dis[j][0] ^ INF) mx = max(mx, dis[j][0]);

			if (dis[j][1] ^ INF) mx = max(mx, dis[j][1]);

		}

		total += n;

		for(re int i = 1; i <= n; i++) h[i] = 0;

	}

	printf("%lld\n", (solve(0) + solve(1) - solve(2) + MOD) % MOD);

}

当然用 \(STL\) 的 \(vector\) 和 \(queue\) 虽然直观但终究是慢了

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define re register

#define LL long long

using namespace std;

const int K = 5e4 + 5, N = 2e5 + 5, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int mx, k, n, m, h[N], tot, total, dis[N][2], col[N], vis[N][2], g[N][3], Tot;

struct node{int x, z;};

node Q[N << 1];

struct edge{int to, nxt;}e[N << 1], E[N << 1];

inline void add(int x, int y)

{

	e[++tot] = edge{y, h[x]}, h[x] = tot;

	e[++tot] = edge{x, h[y]}, h[y] = tot;

}

inline void Add(int x, int z, int y){E[++Tot] = edge{y, g[x][z]}, g[x][z] = Tot;}

inline void read(int &x)

{

	x = 0; char ch = getchar();

	while (!isdigit(ch)) ch = getchar();

	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

}

struct Segment{

	#define ls (p << 1)

	#define rs (ls | 1)

	int tr[K << 2], sum[K << 2];

	void build(int p, int l, int r)

	{

		if (l == r) return void(sum[p] = 0);

		int mid = (l + r) >> 1;

		build(ls, l, mid), build(rs, mid + 1, r);

	}

	void update(int p, int l, int r, int x, int v)

	{

		if (x < l || x > r) return;

		if (l == r) return void(sum[p] += v);

		int mid = (l + r) >> 1;

		if (x <= mid) update(ls, l, mid, x, v);

		else update(rs, mid + 1, r, x, v);

		sum[p] = 1LL * sum[ls] * sum[rs] % MOD;

	}

	int query(int p, int l, int r, int tl, int tr)

	{

		if (tl > r || tr < l) return 1;

		if (tl <= l && r <= tr) return sum[p];

		int mid = (l + r) >> 1;

		int res = 1;

		if (tl <= mid) res = query(ls, l, mid, tl, tr);

		if (tr > mid) res = 1LL * res * query(rs, mid + 1, r, tl, tr) % MOD;

		return res;

	}

}T;

inline void spfa()

{

	int head = 0, tail = 1;

	for(re int j = 1; j <= n; j++) dis[j][0] = dis[j][1] = INF, vis[j][0] = vis[j][1] = 0;

	dis[1][0] = 0, vis[1][0] = 1, Q[1] = node{1, 0};

	while (head < tail)

	{

		node now = Q[++head];

		for(re int j = h[now.x]; j; j = e[j].nxt)

		if (dis[e[j].to][now.z ^ 1] > dis[now.x][now.z] + 1)

		{

			dis[e[j].to][now.z ^ 1] = dis[now.x][now.z] + 1;

			if (!vis[e[j].to][now.z ^ 1])

				vis[e[j].to][now.z ^ 1] = 1, Q[++tail] = node{e[j].to, now.z ^ 1};

		}

		vis[now.x][now.z] = 0;

	}

}

inline int solve(int z)

{

	T.build(1, 1, k);

	for(re int i = mx; i >= 0; i--)

		for(re int j = g[i][z]; j; j = E[j].nxt) T.update(1, 1, k, col[E[j].to], 1);

	int res = 0;

	for(re int i = mx; i; i--)

		for(re int j = g[i][z]; j; j = E[j].nxt)

			res = (res + 1LL * T.query(1, 1, k, 1, col[E[j].to] - 1) * T.query(1, 1, k, col[E[j].to] + 1, k) % MOD * i % MOD) % MOD,

			T.update(1, 1, k, col[E[j].to], -1);

	return res;

}

int main()

{

	read(k);

	for(re int i = 1; i <= k; i++)

	{

		tot = 0;

		read(n), read(m);

		for(re int j = 1, x, y; j <= m; j++) read(x), read(y), add(x, y);

		spfa();

		for(re int j = 1; j <= n; j++)

		{

			col[total + j] = i;

			for(re int l = 0; l <= 1; l++)

			if (dis[j][l] ^ INF) Add(dis[j][l], l, total + j);

			if (max(dis[j][0], dis[j][1]) ^ INF) Add(max(dis[j][0], dis[j][1]), 2, total + j);

			if (dis[j][0] ^ INF) mx = max(mx, dis[j][0]);

			if (dis[j][1] ^ INF) mx = max(mx, dis[j][1]);

		}

		total += n;

		for(re int i = 1; i <= n; i++) h[i] = 0;

	}

	printf("%d\n", (1LL * solve(0) + solve(1) - solve(2) + MOD) % MOD);

}

最新文章

  1. Oracle中添加新用户并赋予权限
  2. 播放视频最好的 HTML 解决方法
  3. cocos2d-lua class 方法解释
  4. Windows环境Mycat数据库分库分表中间件部署
  5. 请教DotNetBar控件中的CalendarView控件如何拖动当前的时间轴
  6. Networking - ARP 协议
  7. light oj 1078 - Integer Divisibility
  8. oracle16 例外
  9. NBUT 1457 Sona
  10. [CSS3] 学习笔记-CSS3选择器详解（一）
  11. 解决Linux下面Firefox无法播放mp3的问题
  12. tyvj4877 组合数
  13. HDU 2079 dp解法
  14. C#常见问题总结（二）
  15. 集腋成裘-11-sql性能优化
  16. Python之celery的简介与使用
  17. 记一次servlet项目启动
  18. Python之PIL库的运用、GIF处理
  19. Django2 SQLite3迁移到MySQL数据库
  20. LOJ #559. 「LibreOJ Round #9」ZQC 的迷宫

热门文章

  1. HCIE Routing&amp;Switching之MPLS基础理论
  2. 处理get请求中文乱码tomcat请求
  3. 重新认识下JVM级别的本地缓存框架Guava Cache(3)——探寻实现细节与核心机制
  4. 【开发必备】单点登录，清除了cookie，页面还保持登录状态？
  5. 【Hadoop学习】中：HDFS、shell操作、客户端API操作、数据流、1NN、2NN原理、DataNode配置
  6. MassTransit 知多少 | 基于MassTransit Courier实现Saga 编排式分布式事务
  7. jmeter websocket 接口测试环境准备
  8. Django之SQL注入漏洞复现(CVE-2021-35042)
  9. 2022年7月13日，第四组，周鹏，JS做计算器代码
  10. 解决MySQL Connector/ODBC驱动无法安装Error1918