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

题解:qoj7938 Graph Race

简单题。

题意:给出一张图,边权为 \(1\),每个点有属性 \(a,b\),定义一个点 \(u\) 的权值 \(f(u)\)\(\max _{u\not=v}a_v-b_v\operatorname{dis}(u,v)\),按从小到大的顺序输出与 \(1\) 相连的的点的 \(f\) 值。

做法:

首先观察到只需要输出与 \(1\) 相连的而不是任一点,说明这是有意义的。我们注意到,与 \(1\) 相连的点 \(u\),与其他 \(v\) 的距离 \(\operatorname{dis}(u,v)\)\(\operatorname{dis}(1,v)\) 相差不会超过 \(1\),所以可以直接讨论三者的贡献。

首先对于 \(\operatorname{dis}(1,v)+1\),因为这个是最差的可能,直接全部更新就可以了。

然后对于 \(\operatorname{dis}(1,v) - 1\)\(\operatorname{dis}(1,v)\),前者等于,我令 \(\operatorname{dis}(1,x)+1=\operatorname{dis}(1,y)\) 的这些边在新图上连一条 \(x\rightarrow y\) 的有向边,然后只能走这些有向边到达;后者等于我可以走一条 \(\operatorname{dis}(1,x)=\operatorname{dis}(1,y)\) 的边。

第一种边很好连,关键在于第二种我只能走一条,只能走一条这种限制很分层图,直接拆开就可以了。

记得要求 \(u\not=v\)

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 6e5 + 5;
int n, m, a[maxn], b[maxn], ans[maxn];
vector<int> e[maxn], g[maxn];
int dis[maxn];
void bfs(int s) {memset(dis, 0x3f, sizeof(dis));dis[s] = 0;queue<int> q; q.push(s);while(!q.empty()) {int u = q.front(); q.pop();for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(dis[v] > dis[u] + 1) {dis[v] = dis[u] + 1;q.push(v);}}}
}
int vis[maxn], res[maxn];
struct node {int val, p;friend bool operator<(node x, node y) {return (x.val < y.val ? 1 : 0);}node() {val = -9e18, p = 0;}node(int V, int P) {val = V, p = P;}
} mx, smx;void dfs(int u) {if(vis[u])return ;vis[u] = 1;res[u] = a[u] - b[u] * dis[u];for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];dfs(v);ans[u] = max(ans[u], res[v]);}res[u] = max(res[u], ans[u]);
//	cout << u << " " << ans[u] << " " << res[u] << endl;
}
signed main() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];for (int i = 1; i <= m; i++) {int x, y; cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}bfs(1);memset(ans, -0x3f, sizeof(ans));for (int i = 1; i <= n; i++) {node t = node{a[i] - (dis[i] + 1) * b[i], i};if(smx < t)smx = t;if(mx < smx)swap(smx, mx);}
//	cout << mx.val << " " << mx.p << endl;for (int i = 1; i <= n; i++) {for (int j = 0; j < e[i].size(); j++) {int k = e[i][j];if(dis[i] + 1 == dis[k])g[i].push_back(k), g[i + n].push_back(n + k);else if(dis[i] == dis[k])g[i].push_back(k + n);}}for (int i = 1; i <= n; i++)dis[i + n] = dis[i], dis[i] = max(dis[i] - 1, 0ll),a[i + n] = a[i], b[i + n] = b[i];for (int i = 1; i <= 2 * n; i++)dfs(i);sort(e[1].begin(), e[1].end());for (int i = 0; i < e[1].size(); i++) {if(e[1][i] == mx.p)cout << max(smx.val, ans[e[1][i]]) << endl;elsecout << max(mx.val, ans[e[1][i]]) << endl;}return 0;
}
/*
3 3
1235 123
2152 242
324 31
1 2
2 3
3 1
*/
http://www.hskmm.com/?act=detail&tid=33837

相关文章:

  • java中的初等函数
  • 分治算法
  • 专用硬件神经网络优化技术解析
  • 学习逆向的背景知识(自用)
  • Linux-网络安全私房菜(二)
  • pycharm使用远程的ssh的解释器
  • Android SSL Pinning检测利器:SSLPinDetect技术解析
  • AI元人文:社区调解的数字剧场
  • 2025年粉末冶金制品/零件厂家推荐排行榜,专业制造与高品质服务的首选!
  • Dubbo入门-Dubbo的快速使用
  • 站位2
  • 傅里叶变换及DCT点滴
  • 【未完待续】MkDocs 部署安装教程
  • 傅里叶变换点滴
  • [PaperReading] SAIL-Embedding Technical Report: Omni-modal Embedding Foundation Model
  • 人生四大支柱 - 健康,金钱,工作,关系
  • 英伟达个人AI超算Spark技术解析
  • [buuctf]jarvisoj_level3_x64
  • SpringBoot系列十三:SpringBoot面试常见问题
  • [LangChain] 04. 提示词模板
  • 2025 最新不锈钢板厂家推荐榜:剖析国内头部品牌竞争优势,附优质供应商选择指南N06625/N06600/C70600不锈钢板厂家推荐
  • 2025 夹丝玻璃源头厂家最新推荐排行榜:解析防火 / 艺术 / 酒店等多场景厂商优势,助力精准选型
  • 2025 中空板源头厂家最新推荐排行榜揭晓:覆盖全产业链,老牌与新锐共筑品质标杆
  • 2025 年感温电缆厂家最新推荐榜单:覆盖线型 / 缆式 / 可恢复 / 消防等多类型产品,全方位解析头部企业核心优势
  • 2025 年盖板源头厂家最新推荐榜单:电力 / 隧道 / 电缆沟等多场景适用品牌优选,解析原材料采购与成本控制要点
  • win
  • 2025 年真空炉制造厂家最新推荐排行榜:涵盖高温烧结真空炉 / 真空退火炉 / 智能铍铜真空炉,助力企业精准选型
  • 2025 年最新推荐排水沟厂家排行榜:聚焦树脂 / 线性 / 树脂混凝土 / 成品 / U 型排水沟优质企业
  • 将 XMind 测试用例转换为 CSV 文件导入测试管理平台
  • 互评-OO之接口-DAO模式代码阅读及应用