AcWing 道路与航线

AcWing 道路与航线

Description

  • Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T),花费为C_i。

    对于道路,0 <= C_i <= 10,000;然而航线的花费很神奇,花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的,可以从A_i到B_i,也可以从B_i到A_i,花费都是C_i。然而航线与之不同,只可以从A_i到B_i。

    事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台 了一些政策保证:如果有一条航线可以从A_i到B_i,那么保证不可能通过一些道路和航线从B_i回到A_i。由于FJ的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

Input

  • * Line 1: Four space separated integers: T, R, P, and S

    * Lines 2..R+1: Three space separated integers describing a road: A_i, B_i and C_i

    * Lines R+2..R+P+1: Three space separated integers describing a plane: A_i, B_i and C_i

Output

  • Lines 1..T: The minimum cost to get from town S to town i, or ‘NO PATH‘ if this is not possible

Sample Input

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10 

Sample Output

NO PATH
NO PATH
5
0
-95
-100 

题解:

  • 最短路。
  • 有负边权,spfa呗。但是最坏会被卡成O(nm),对于这题明显不行。所以思考用别的方法。
  • 这题很特别,给了很多限定条件:
  1. “然而航线的花费很神奇,花费C_i可能是负数” -> 有负边权
  2. “如果有一条航线可以从A_i到B_i,那么保证不可能通过一些道路和航线从B_i回到A_i” -> 不存在负环,有可能有正环
  • 再想想每个最短路算法的特点。spfa可以有负边权,不能有环。dijkstra不能有负边权。
  • 那么这题我们可以只把双向边添加进来,这样就会形成若干个连通的块,块内用dijkstra跑最短路。再将单向边添加进来,就变成了一个DAG,块与块衔接部分用拓扑序跑最短路。
  • 还有几个要注意的地方:
  1. 拓扑排序是保证可以按顺序更新,不产生紊乱。并不是用拓扑像以往的题跑dp去算。

    • 因为块内算dij时,可能会更新到块外的点,这个时候就已经在算块与块间的最短路了。
  2. 入度为0的块要一起加进来,不能只加s所在块,因为要保证拓扑排序的进行。
  3. 由于第2点的存在,可能存在某个点被s不能走到的点更新。因此最后判断无解的时候不能写成==inf
  • 具体算法流程参照lyd老师的讲解。
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#define N 25005
#define M 200005
using namespace std;

struct Node
{
    int val, pos;
    friend bool operator < (Node x, Node y) {
        return x.val > y.val;
    }
};
struct E {int next, to, dis;} e[M];
int n, m1, m2, s, num, dfn;
int h[N], bel[N], deg[N], dis[N];
bool vis[N];
vector<int> c[N];
queue<int> que;

int read()
{
    int x = 0, f = 1; char c = getchar();
    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;
}

void add(int u, int v, int w)
{
    e[++num].next = h[u];
    e[num].to = v;
    e[num].dis = w;
    h[u] = num;
}

void dfs(int x)
{
    bel[x] = dfn, vis[x] = 1, c[dfn].push_back(x);
    for(int i = h[x]; i != 0; i = e[i].next)
        if(!vis[e[i].to]) dfs(e[i].to);
}

void dijkstra(int id)
{
    priority_queue<Node> pue;
    for(int i = 0; i < c[id].size(); i++) pue.push((Node){dis[c[id][i]], c[id][i]});
    while(pue.size())
    {
        int now = pue.top().pos;
        pue.pop();
        if(vis[now]) continue;
        vis[now] = 1;
        for(int i = h[now]; i != 0; i = e[i].next)
        {
            if(dis[now] + e[i].dis < dis[e[i].to])
            {
                dis[e[i].to] = dis[now] + e[i].dis;
                if(bel[now] == bel[e[i].to]) pue.push((Node){dis[e[i].to], e[i].to});
            }
            deg[bel[e[i].to]]--;
            if(!deg[bel[e[i].to]] && bel[now] != bel[e[i].to]) que.push(bel[e[i].to]);
        }
    }
}

int main()
{
    cin >> n >> m1 >> m2 >> s;
    for(int i = 1; i <= m1; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w), add(v, u, w);
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i]) ++dfn, dfs(i);
    for(int i = 1; i <= m2; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w);
        deg[bel[v]]++;
    }
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0, que.push(bel[s]);
    for(int i = 1; i <= dfn; i++)
        if(!deg[i]) que.push(i);
    while(que.size())
    {
        int now = que.front();
        que.pop();
        dijkstra(now);
    }
    for(int i = 1; i <= n; i++)
        if(dis[i] >= 1e9) printf("NO PATH\n");
        else printf("%d\n", dis[i]);
}

原文地址:https://www.cnblogs.com/BigYellowDog/p/11373901.html

时间: 08-16

AcWing 道路与航线的相关文章

道路和航线

题目描述 Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接.每条道路i或者航线i连接城镇Ai (1 <= Ai <= T)到Bi (1 <= Bi <= T),花费为Ci.对于道路,0 <= Ci &l

[Usaco2011 Jan]道路和航线

Description Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查.他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1T.这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接.每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T),花费为C_i.对于道路,0

ACwing 342. 道路与航线

首先看到这道题目,我们发现这道题目的复杂度,首先确定了是O(nlogn)O(nlogn)级别的,所以说,我们的算法初步确定在dijskra和SPFA上面. 但是我们发现这道题目一个关键点,就是题目中出现了负权边. 一旦出现了负权边,那么我们只能使用SPFA. 关于SPFA优化https://www.cnblogs.com/TFLS-gzr/p/10389141.html #include <bits/stdc++.h> using namespace std; const int N=4000

BZOJ 2200 道路与航线

好厉害呀这道题,有种豁然开朗的感觉.... 按拓扑顺序跑最短路. 然后注意细节,像WA的代码犯下的错是一笔带过没有丝毫考虑的...然而就是错了. 考试的时候一定要拍啊. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #define

BZOJ2200: [Usaco2011 Jan]道路和航线

n<=25000个点m1<=50000条正权无向边m2<=50000条正负权有向边,保证有向边连接的无向边联通块形成一个拓扑图,求从s到每个点最短路. 第一次发现不会最短路.没看题乱写迪杰无脑WA,很好.迪杰从来不能处理负权最短路,然后就开始啃题解..http://www.cnblogs.com/staginner/archive/2012/10/01/2709487.html这篇代码不错,讲得也很好. 在每个无向边联通块中找最短路可以直接迪杰.至于过度到不同的联通块,可以对无向图联通块

算法提高课——图论

图论难点:问题的转化和抽象(可看成特殊的某一类DP) 图论与DP的联系: DP问题(从集合角度分析最优化问题)可以看成从F(0,0).F(0,1).F(1,2)......F(0,m)到F(n,m)的最长路.因此DP问题可以转化为拓扑图(一般DP问题的状态间无环)上的最短(长)路. 当DP依赖关系不具有拓扑序时(即存在环时),可以将其转化为最短路,也可以用高斯消元. //TLE的原因常常是没有memsert //st数组在不同算法中的用法: 单源最短路的建图方式 AcWing 1129. 热浪

2017/07/25 杂题(完全不可做题(划去))选讲

先膜一发主讲人@Antileaf 真是核平的一天那--大脑已经被蹂躏的死去活来了-- cogs2421 简单的Treap 链接:http://cogs.pro/cogs/problem/problem.php?pid=2421 题意:什么都给你了,建出Treap,输出先序遍历顺序. 实际上只是用了Treap的原则建树--先按照数值大小排序,然后按照建立笛卡尔树方法,维护单调栈,最大的全扔到右儿子去即可. 1 #include<iostream> 2 #include<cstdio>

bzoj2702[SDOI2012]走迷宫

题意:给你一个有向图,点数10000,边数1000000,SCC大小不超过100(按数据范围的写法只有第三部分数据满足这个条件,不过第二部分数据并没有出现大小大于100个点的SCC,我是用数组大小为100的代码以身试法的2333)从s出发随机走,问走到t的期望步数. 首先考虑inf的情况.如果从s出发可以走到一个无法走到t的点,比如这个数据:红色点为起点,绿色点为终点,那么有1/2的概率永远也走不到(在蓝色点停下). 注意出现环的情况不一定是INF,因为在环上走无穷步的概率可能是无穷小.于是先缩

DP&amp;图论 DAY 4 下午图论

DP&图论  DAY 4  下午 后天考试不考二分图,双联通 考拓扑排序 图论 图的基本模型 边: 有向边构成有向图 无向边构成无向图 权值: 1.无权 2.点权 3.边权 4.负权(dij不可以跑) 环: 1. 2.重边 3.有向无环图DAG 路径: 1.简单路径:不经过重复的点  1-->2-->3 不简单路径:经过重复点  1-->2-->3-->1-->4 2.连通,具有传递性 图: 1.树:n个点,n-1条边的无环连通图 2.完全图:一个无向图,图中任