Tag-最短路

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-02-26 20:08:10 |  0 Comments  |  最短路

HDU - 5876 Sparse Graph 补图最短路(使用两个set的做法)

题目大意

给出图G,求图G的补图H对于源点S的单源最短路


题解

这道题目就是稍微考虑一下就可以了。同样是一个BFS的写法,只不过这次的BFS要求不能使用图中给出的边,我们要求的是补图的最短路,就要用非原图的所有边。
这样我们可以使用两个set,其中过一个记录当前会被更新的点,另一个记录还没有被更新过的点。具体实现看代码,不好解释。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
sets1;
sets2;
const int maxn = 2e5+5;
struct edge{
    int to,next;
}e[maxn];
int h[maxn];
int dis[maxn];
int T,n,m,S,u,v,cnt;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (((num<<2)+num)<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
void init(){
    for(int i = 1;i <= n;++i){
        h[i] = -1;
        dis[i] = -1;
    }
    cnt = 0;
}
void add(int u,int v){
    e[cnt].to = v;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void BFS(int s){
    for(int i = 1;i <=
 2019-02-14 10:43:38 |  0 Comments  |  网络流 最小割 最短路

BUPT校内训练 & HDU 5294 最短路&最小割

Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

 2019-02-13 09:33:40 |  0 Comments  |  最短路 差分约束系统

[转载]差分约束系统详细讲解

差分约束系统

一、何为差分约束系统:
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:


二、差分约束系统的求解:
差分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
 如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。


因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最长路求解算法证明如下:
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题

 2016-12-11 21:25:50 |  1 Comments  |  DP 最短路

[NOIP2016Day1T3]换教室classroom

[NOIP2016Day1T3]换教室classroom

题目描述

对于刚上大学的牛牛来说, 他面临的第一个问题是如何根据实际情况中情合适的课程。
在可以选择的课程中,有2n节课程安排在n个时间段上。在第 i ( 1≤ i≤n)个时同段上, 两节内容相同的课程同时在不同的地点进行, 其中, 牛牛预先被安排在教室 ci上课, 而另一节课程在教室 di进行。
在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出中情。若申请通过,学生就可以在第 i个时间段去教室 di上课, 否则仍然在教室 ci上课。
由于更换教室的需求太多, 申请不一定能获得通过。 通过计算, 牛牛发现申请更换第 i节课程的教室时, 中情被通过的概率是一个已知的实数 ki, 并且对于不同课程的申请, 被通过的概率是互相独立的。
学校规定, 所有的申请只能在学期开始前一次性提交, 并且每个人只能选择至多m节课程进行申请。 这意味着牛牛必须一次性决定是否申请更换每节课的教室, 而不能根据某些课程的申请结果来决定其他课程是否申请; 牛牛可以申请白己最希望更换教室的 m门课程,也可以不用完这m个中情的机会,甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行, 所以牛牛需要利用课问时间从一间教室赶到另一间教室。
牛牛所在的大学有 v个教室,有 e条道路。每条道路连接两间教室, 并且是可以双向通行的。 由于道路的长度和拥;i者程度不同, 通过不同的道路耗费的体力可能会有所不同。当第i ( 1≤i≤n-1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

输入格式

第一行四个整数 n,m,v,e 。 n表示这个学期内的时间段的数量; m表示牛牛最多可以申请更换多少节课程的教室; v表示牛牛学校里教室的数量; e表示牛牛的学校里道路的数量。
第二行n个正整数,第 i ( 1≤ i≤ n)个正整数表示c,,即第 i个时间段牛牛被安

Title - Artist
0:00