BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短…
2018-09-10 00:58:34来源:博客园 阅读 ()
题意
给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长度
Sol
emmm,考场上想了个贪心开心的飞起然而只多得了10分qwq
正解比较神仙。
首先把最短路树建出来,考虑一条非树边$(u, v)$什么时候能更新答案
结论是:除了他们的LCA外的子树内其他都可以更新,且新的权值为$dis[u] + dis[v] + w(u, v) - dis[x]$,$x$表示新节点
这样我们把所有的边按照$dis[u] + dis[v] + w(u, v)$排序,显然,一个点如果被更新过那么就再也不会被更新了。
用并查集把已经更新过的点缩起来即可
这题的关键是要发现非树边与答案之间的性质。。
#include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second using namespace std; const int MAXN = 1e6 + 10, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; vector<Pair> v[MAXN]; struct Edge { int u, v, w; }E[MAXN]; int num = 0; int dis[MAXN], top[MAXN], vis[MAXN], cnt = 0, ans[MAXN]; void Dij() { memset(dis, 0x7f, sizeof(dis)); dis[1] = 0; priority_queue<Pair> q; q.push(MP(0, 1)); while(!q.empty()) { int p = q.top().se; q.pop(); if(vis[p]) continue; vis[p] = 1; for(int i = 0; i < v[p].size(); i++) { int to = v[p][i].fi, w = v[p][i].se; if(dis[to] > dis[p] + w && (!vis[to])) { top[to] = p; dis[to] = dis[p] + w; q.push(MP(-dis[to], to)); } } } } int comp(const Edge &a, const Edge &b) { return dis[a.u] + dis[a.v] + a.w < dis[b.u] + dis[b.v] + b.w; } int fa[MAXN]; int unionn(int x, int y) { fa[x] = y; } int Find(int x) { if(fa[x] == x) return fa[x]; else return fa[x] = Find(fa[x]); } int solve(int x, int y, int w) { while((x = Find(x)) != (y = Find(y))) { //int dx = dis[x], dy = dis[y]; if(dis[x] < dis[y]) swap(x, y); ans[x] = w - dis[x]; x = (fa[x] = top[x]); cnt++; } } int main() { N = read(); M = read(); for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); v[x].push_back(MP(y, z)); v[y].push_back(MP(x, z)); } Dij(); for(int i = 1; i <= N; i++) { fa[i] = i; for(int j = 0; j < v[i].size(); j++) { int to = v[i][j].fi, w = v[i][j].se; if(top[to] == i || top[i] == to) continue; E[++num] = (Edge) {i, to, w}; } } sort(E + 1, E + num + 1, comp); for(int i = 1; i <= num; i++) { solve(E[i].u, E[i].v, dis[E[i].u] + dis[E[i].v] + E[i].w); if(cnt == N - 1) break; } for(int i = 2; i <= N; i++) printf("%d\n", ans[i] ? ans[i] : -1); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LuoguP3069 【[USACO13JAN]牛的阵容Cow Lineup 2019-10-30
- P5200 [USACO19JAN]Sleepy Cow Sorting 2019-08-26
- Tarjan算法初探 (1):Tarjan如何求有向图的强连通分量 2019-04-11
- BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp) 2018-09-05
- BZOJ1093: [ZJOI2007]最大半连通子图(tarjan dp) 2018-09-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash