当前位置: 首页 > news >正文

2025.10.10 图论

最短路

P5304 [GXOI/GZOI2019] 旅行者

Hint:考虑从暴力优化. 图论建模,路径最短的两个关键点编号一定不同,按照二进制位划分成两个集合跑最短路.

最暴力的方法我们可以枚举关键点对跑最短路,时间复杂度 \(O(k^2m\log m)\).

显然有很多点对是没有任何意义的,考虑图论建模,一次跑多组最短路. 也就是直接将关键点分为两个集合,建立超级源点 \(S\) 连向其中一个集合的所有点,边权为 \(0\);另一个集合所有点连向超级汇点,边权为 \(0\). 然后跑 \(S\rightarrow T\) 的最短路,当距离最近的两点被分到两个集合时,这样跑就能得到答案. 所以现在的问题就是如何划分关键点.

距离最近的两点编号一定不同,换言之至少有一个二进制位不同. 枚举二进制位,每次将当前二进制位不同的划分成两个集合,跑上面的最短路并更新答案即可. 时间复杂度 \(O(m\log m\log n)\).

P4366 [Code+#4] 最短路

Hint:直接连边边数可以达到 \(O(n^2)\),但是点数是 \(O(n)\),考虑拆位优化建图.

对每个点考虑贡献,发现如果一条新边有若干个二进制位有贡献,那么完全可以拆成若干位贡献再加起来. 也就是说类似于前缀优化建图,我们对于每一个 \(0\le u\le n\) 的点都向改变一位二进制位的点连边,就已经包含了所有可能的新边. 然后跑最短路即可.

P7515 [省选联考 2021 A 卷] 矩阵游戏

Hint:先推出一个不限制值域的答案,然后设出调整的变量,用差分约束求解.

令矩阵 \(A\) 最后一行和最后一列全为 \(0\),可以解出一组符合 \(b_{i,j}\) 限制的解. 现在要尝试修改一个位置上的值,我们需要调整附近位置的值使得仍然满足限制.

进一步观察,发现我们可以对一行或一列进行 \(+x,-x,+x,-x\cdots\) 的操作而仍然满足限制. 设 \(r_i\) 为行上操作的值,\(c_i\) 为列上操作的值,可以列出操作矩阵:

\[\begin{pmatrix} r_1+c_1&-r_1+c_2&r_1+c_3&\cdots\\ r_2-c_1&-r_2-c_2&r_2-c_3&\cdots\\ r_3+c_1&-r_3+c_2&r_3+c_3&\cdots\\ \vdots & \vdots&\vdots&\ddots \\ \end{pmatrix} \]

但是这样的形式分讨稍显复杂,可以考虑对于所有 \(i\) 为偶数的 \(r_i\)\(j\) 为奇数的 \(c_j\) 取相反数. 这仍然是满足限制的.

\[\begin{pmatrix} r_1-c_1&c_2-r_1&r_1-c_3&\cdots\\ c_1-r_2&r_2-c_2&c_3-r_2&\cdots\\ r_3-c_1&c_2-r_3&r_3-c_3&\cdots\\ \vdots & \vdots&\vdots&\ddots \\ \end{pmatrix} \]

现在的形式非常优美了,考虑这个 \(x-y\) 的形式怎么用差分约束. 首先我们求得了一组解 \(a_{i,j}\),所以 \(-a_{i,j}\le x-y\le 10^6-a_{i,j}\),拆成两个不等式分别连边即可.

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long#define gc getwchar_unlocked
#define pc putwchar_unlocked
inline int rd(){int x = 0, f = 1; char ch = gc();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = gc(); }while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = gc(); }return x * f;
}
inline void wt(int x) {static int stk[40],tp=0;if(x<0) pc('-'),x=-x;do{stk[++tp]=x%10;x/=10;}while(x);while(tp) pc((char)(stk[tp--]+'0'));
}const int maxn = 3e2 + 10, maxnm = 9e4 + 10; const ll inff = 0x3f3f3f3f3f3f3f3f;
int T, n, m, a[maxn][maxn], b[maxn][maxn];
int s = 1;vector<array<int, 2> > e[maxn << 1];
ll dis[maxn << 1]; bool inq[maxn << 1]; int cnt[maxn << 1];
bool spfa() {for(int i = 1; i <= n + m; i++) inq[i] = cnt[i] = 0, dis[i] = inff;deque<int> q; q.push_back(s), inq[s] = true, dis[s] = 0, cnt[s] = 1;while(q.size()) {int u = q.front(); q.pop_front(), inq[u] = false;++cnt[u]; if(cnt[u] > n + m) return false;for(auto [v, w] : e[u]) {if(dis[v] > dis[u] + w) {dis[v] = dis[u] + w;if(!inq[v]) {if(q.size() && dis[v] < dis[q[0]]) q.push_front(v);else q.push_back(v);inq[v] = true;}}}} return true;
}void solve() {for(int i = 1; i <= n + m; i++) vector<array<int, 2> >().swap(e[i]);for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = 0;n = rd(), m = rd();for(int i = 1; i < n; i++) for(int j = 1; j < m; j++) b[i][j] = rd();for(int i = n - 1; i >= 1; i--) for(int j = m - 1; j >= 1; j--) {a[i][j] = b[i][j] - a[i + 1][j] - a[i][j + 1] - a[i + 1][j + 1];}for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {int mx = 1e6 - a[i][j], mi = -a[i][j];if((i + j) & 1) e[j + n].push_back({i, -mi}), e[i].push_back({j + n, mx});else e[j + n].push_back({i, mx}), e[i].push_back({j + n, -mi});}if(spfa()) {puts("YES");for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if ((i + j) & 1) a[i][j] -= dis[i];else a[i][j] += dis[i];if ((i + j) & 1) a[i][j] += dis[j + n];else a[i][j] -= dis[j + n];wt(a[i][j]); pc(' ');} puts("");}}else puts("NO");return;
}int main() {// ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);// freopen("P7515_13.in", "r", stdin);// freopen("myout.out", "w", stdout);T = rd(); while(T--) solve();return 0;
}

为啥把链式前向星改成 vector 快了 \(25\) 倍?

http://www.hskmm.com/?act=detail&tid=28782

相关文章:

  • xshell把界面转发到xming
  • 使用AI创建angular项目
  • 大模型在软件研发协同演进
  • NocoBase 走进德国大学课堂
  • 2025青海视频号运营最新推荐:创意内容与高效推广策略的完美
  • 008_函数
  • 内存分析记录
  • 详细介绍:构建生产级多模态数据集:视觉与视频模型(参照LLaVA-OneVision-Data和VideoChat2)
  • 2025 年图书杀菌机生产厂家最新推荐排行榜:聚焦高效杀菌技术与优质服务,优质企业全面盘点自助图书/臭氧图书/消毒图书/图书杀菌机厂家推荐
  • 公网服务器下的dify安装模型插件的相关问题和操作
  • vscode 生成代码片段
  • MySQL根据表生成实体类
  • 2025票务系统最新推荐榜:高效便捷与用户体验俱佳的优质选择
  • 【黑马python】基础 3.Python 判断语句 if-else
  • 有度新版本:反向登录、文件路径自定义、有度极速版…管理更自主,切换更顺畅
  • C#利用委托实现多个窗体间的传值
  • 2025常州微弧氧化批发厂家最新推荐榜:技术领先与优质服务双
  • new操作符的手动实现
  • JS使用Regex校验出现卡顿
  • 2025舒适轮胎厂家最新推荐榜:静音耐磨,驾驶体验再升级!
  • 2025 净化铝型材十大品牌之一优选,推荐龙新铝业,最快24小时内发货
  • 手写Promise
  • 双列集合
  • 二项式反演
  • 2025 权威推荐!净化铝型材品牌 TOP5 排行榜:实力厂家精选,品质之选不容错过
  • 关于HashMap
  • sar(System Activity Reporter 系统活动情况报告)是目前 Linux 上最为全面的系统性能分析工具之一。
  • 车辆主动悬架线性最优控制(LQR)系统
  • 2025环保/植物/净醛/健康/无味腻子粉厂家推荐榜:专注多场景墙面基底解决方案供应!
  • 2025 泰国立体/高位/仓储/托盘/重型/流利式/贯通式/穿梭车/模具货架厂家推荐排行榜:聚焦多场景存储需求,精选优质供应商!