头像

xjsc01

https://blog.csdn.net/xjsc01




离线:9小时前


最近来访(4)
用户头像
no_one
用户头像
Lin_LL
用户头像
yxc
用户头像
笑脸人

活动打卡代码 AcWing 358. 岛屿

xjsc01
21小时前
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
int ver[N*2], nxt[N*2], edge[N*2], head[N], tot;
int n;
int dfn[N], num;//时间戳
int fa[N];//注意:fa里面存放的是边
int s[N*2], p;
long long sum[N*2];
bool v[N];
long long d[N];
long long ans;
int q[2*N];
inline void add(int x, int y, int z)
{
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}

void get_circlee(int x, int y, int z)
{
    sum[1] = z;
    while(x != y)
    {
        s[++p] = y;
        sum[p+1] = edge[fa[y]];
        y = ver[fa[y] ^ 1];
    }
    s[++p] = x;
    //copy
    for(int i = 1; i <= p; i++) sum[i+p] = sum[i];
    for(int i = 1; i <= p; i++) s[i+p] = s[i];
    for(int i = 1; i <= p*2; i++) sum[i] += sum[i-1];
    for(int i = 1; i <= p; i++) v[s[i]] = true;
}

void dfs(int x)
{
    dfn[x] = ++num;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(!dfn[y]) 
        {
            fa[y] = i;
            dfs(y);
        }
        else
        {
            if((i^1) != fa[x] && dfn[y] > dfn[x])
            {
                get_circlee(x, y, edge[i]);
            }
        }
    }
}

void dp(int x)
{
    v[x] = 1;
    for(int i = head[x]; i; i = nxt[i])
    {

        int y = ver[i], z = edge[i];
        if(!v[y])
        {
            dp(y);
            ans = max(ans, d[x] + d[y] + z);//这里是表示答案在树枝内部的情况
            d[x] = max(d[x], d[y] + z);
        }
    }
}

int main()
{
    static long long tot_ans = 0;
    tot = 1;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int y, z;
        scanf("%d%d", &y, &z);
        add(i, y, z);
        add(y, i, z);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!dfn[i])
        {
            p = 0; ans = 0;
            dfs(i);
            for(int i = 1; i <= p; i++) dp(s[i]);
            int l = 1, r = 0;
            for (int i = 1; i <= 2 * p; i++) {
                while (l <= r && q[l] <= i - p) l++;
                if (l <= r) ans = max(ans, d[s[i]] + d[s[q[l]]] + sum[i] - sum[q[l]]);
                while (l <= r && d[s[q[r]]] - sum[q[r]] <= d[s[i]] - sum[i]) r--;
                q[++r] = i;
            }
            tot_ans += ans;
        }
    }
    cout << tot_ans << '\n';
}



xjsc01
4天前

右击image在新的标签页中打开可以查看图片!

最近公共祖先

在一棵树中,

公共祖先:两个点所共有的祖先。

最近公共祖先(LCA):在所以祖先中,深度最深的。

所具备的性质:

  1. 在所以的公共祖先中,深度最深。
  2. 两个点到达根节点的路径上的交汇点。
  3. 两点之间路径上的最浅的点。

有三种求法

向上标记法(一步一步走)

x向上标记到达根节点的路径,y也向上标记,与x的标记交会的点就是LCA。

树上倍增法(如果向上标记,太过于慢,倍增!)

注意:有两个性质

  1. 满足单调性。如果x与y向上走,走的太远,以至于超越了LCA,那么是到达的同一点。(默认走的超过根节点全部是0号节点)。
  2. 满足可加性。走$k_1$步到达某一个点,从这一个点走$k_2$步到达最终的点,与从最初的点走$k_1+k_2$相同。

构建需要$nlogn$

查询需要$logn$

代码实现:

#include <bits/stdc++.h>
using namespace std;
#define N 305
int head[N], tot;
int ver[N*2], nxt[N*2];
int n;
int d[N], f[N][21];//d既是深度的标记,也是访问以及没有访问的标记。
queue<int > q;
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void bfs(int w)//nlogn
{
    d[w] = 1;
    q.push(w);
    while(q.size())
    {
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
            f[y][0] = x;
            for(int k = 1; k <= 19; k++) f[y][k] = f[ f[y][k-1] ][k-1];
        }
    }
}
int lca(int x, int y)
{
    if(d[x] < d[y]) swap(x, y);
    for(int i = 19; i >= 0; i--)
        if(d[f[x][i]] >= d[y]) x = f[x][i];
    if(x == y)return x;
    for(int i = 19; i >= 0; i--)
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main()
{
    tot = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    bfs(1);
    return 0;
}

AcWing391. 聚会

Y 岛风景美丽宜人,气候温和,物产丰富。Y 岛上有 N 个城市(编号 1,2,,N),有 N1 条城市间的道路连接着它们。

每一条道路都连接某两个城市。

幸运的是,小可可通过这些道路可以走遍 Y 岛的所有城市。

神奇的是,乘车经过每条道路所需要的费用都是一样的。

小可可,小卡卡和小 YY 经常想聚会,每次聚会,他们都会选择一个城市,使得 3 个人到达这个城市的总费用最小。

由于他们计划中还会有很多次聚会,每次都选择一个地点是很烦人的事情,所以他们决定把这件事情交给你来完成。

他们会提供给你地图以及若干次聚会前他们所处的位置,希望你为他们的每一次聚会选择一个合适的地点。

输入格式

第一行两个正整数,N 和 M,分别表示城市个数和聚会次数。

后面有 N−1 行,每行用两个正整数 A 和 B 表示编号为 A 和编号为 B 的城市之间有一条路。

再后面有 M 行,每行用三个正整数表示一次聚会的情况:小可可所在的城市编号,小卡卡所在的城市编号以及小 YY 所在的城市编号。

输出格式

一共有 M 行,每行两个数 Pos 和 Cost,用一个空格隔开,表示第 i 次聚会的地点选择在编号为 Pos 的城市,总共的费用是经过 Cost 条道路所花费的费用。

数据范围

N≤500000,M≤500000

输入样例:

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

输出样例:

5 2
2 5
4 1
6 0

如果询问两个人聚会,应该怎么走,这样的话,相聚的点必定在两点的路径上,并且任意一点都可以。

image

如果可以得到每一个节点的LCA,任意两点的距离就是这两点的深度减去LCA(x, y)的深度的两遍

代码实现

#include <bits/stdc++.h>
using namespace std;
#define N 500005
int head[N], tot;
int ver[N*2], nxt[N*2];
int n, m;
int d[N], f[N][21];
queue<int>q;
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void bfs(int w)
{
    d[w] = 1;
    q.push(w);
    while(q.size())
    {
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
            f[y][0] = x;
            for(int k = 1; k <= 19; k++)
            {
                f[y][k] = f[ f[y][k-1] ][k-1];
            }
        }
    }
}
int lca(int x, int y)
{
    if(d[x] < d[y]) swap(x, y);
    for(int i = 19; i >= 0; i--) if(d[f[x][i]] >= d[y]) x = f[x][i];
    if(x == y) return x;
    for(int i = 19; i >= 0; i--)
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
inline int dist(int x, int y)
{
    int lc = lca(x, y);
    return d[x] + d[y] - d[lc] * 2;
}
int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n-1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    bfs(1);
    //for(int i = 1; i <= n; i++)printf("\n\t%d", d[i]);
    //cout << "tot" << tot;
    for(int xx = 1; xx <= m; xx ++)
    {
        int lc = 0;
        int a[5];
        for(int i = 1; i <= 3; i++) scanf("%d", a+i);
        lc = lca(a[1], a[3]);
        for(int i = 1; i <= 2; i++)
        {
            int tmp = lca(a[i], a[i+1]);
            if(d[tmp] > d[lc]) lc = tmp;
        }
        int ans = 0;
        for(int i = 1; i <= 3; i++) ans += dist(a[i], lc);
        printf("%d %d\n", lc, ans);
    }
    return 0;
}

Tarjan算法(与并查集的路径压缩相似)

这是一个离线算法!

image

这里的v数组不再是只有0和1.

在这里有三种状态:0,1,2。

0:还没有被访问过。

1:正在访问的点以及这个点到根节点上的所有点。

2:已经被访问的点。

在任何时候,2号点的最终父亲是1号节点。

这一个过程就像是并查集。所以采用路径压缩在进行求

值得注意的是:

  1. 对于x,y(不相等),那么如果遍历到x的时候y是0,那么遍历到y的时候x是2.
    反着对于x以及y,正着与反着都考虑一下总有答案。
  2. 当x以及y相等的时候,就不向邻接表中存了,直接把答案记作x。

AcWing391的Tarjan算法实现。(例题见上一题)

(使用邻接表的形式对数据进行离线化)

#include <bits/stdc++.h>
using namespace std;
#define N 500005
int n, m;
int head[N], tot, ver[N*2], nxt[N*2];
inline void add(int x, int y)
{
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
struct {
    int x, y, z;
}a[3*N];
int lca[N*3];
int hq[3*N], tq = 1;
int vq[6*N], idxq[N*6], nq[N*6];
int d[N];
int fa[N];
int v[N];
int get(int x)
{
    if(x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

inline void add_val(int x, int y, int i)
{
    if(x == y) {
        lca[i] = x;
        return ;
    }
    vq[++tq] = y;
    idxq[tq] = i;
    nq[tq] = hq[x];
    hq[x] = tq;
    vq[++tq] = x;
    idxq[tq] = i;
    nq[tq] = hq[y];
    hq[y] = tq;
} 

inline int dist(int x, int y, int ll)
{
    return d[x] + d[y] - 2*d[ll];
}

void dfs(int x)
{
    v[x] = 1;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(!v[y])
        {
            d[y] = d[x] + 1;
            dfs(y);
            fa[y] = x;
        }
    }
    for(int i = hq[x]; i; i = nq[i])
    {
        int y = vq[i];
        if(v[y] == 2)
        {
            lca[idxq[i]] = get(y);
        }
    }
    v[x] = 2;
}
int main()
{
    tot = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n-1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    for(int i = 1; i <= m; i++)
    {
        add_val(a[i].x, a[i].y, i);
        add_val(a[i].x, a[i].z, i+m);
        add_val(a[i].y, a[i].z, i+m*2);
    }
    for(int i = 1; i <= n; i++) fa[i] = i;
    dfs(1);
    //for(int i = 1; i <= 3*n; i++) printf("%d\t", d[i]);
    for(int i = 1; i <= m; i++)
    {
        int x = a[i].x, y = a[i].y, z = a[i].z;
        int xy = lca[i];
        int xz = lca[i+m];
        int yz = lca[i+m*2];
        int p = 0;
        int len = 0;
        if(d[xy] >= d[xz] && d[xy] >= d[yz])
        {
            p = xy;
            len = dist(x, xy, xy) + dist(y, xy, xy) + dist(z, xy, xz);//这一个是根据性质所得到的。
        }
        else if (d[xz] >= d[xy] && d[xz] >= d[yz])
        {
            p = xz;
            len = dist(x, xz, xz) + dist(z, xz, xz) + dist(y, xz, yz);//这一个是根据性质所得到的。 
        }
        else
        {
            p = yz;
            len = dist(y, yz, yz) + dist(z, yz, yz) + dist(x, yz, xz);//这一个是根据性质所得到的。
        }
        printf("%d %d\n", p, len);
    }
    return 0;
}



xjsc01
5天前

温馨提示:点击题目标题即可跳转到OJ
右击image在新的标签页中打开可以查看图片

树的直径

树上两点的距离:从一个点到另一个点的唯一一条路径的权值之和。

树的直径:任意选取两个点,距离最长的那个距离为这一棵树的直径。

树的最长链:距离最长的那个距离所对应的路径(有时候称为树的直径)


接下来的两种求法时间复杂度都是O(N)

如果是单纯求树的直径这一个数字,或者是有负权边,那么采用树形DP
如果要有具体的方案,采用两次DFS为妙。(在第二次的时候记录更新每一个点的点)
What‘s more? 如果使用两次DFS没有爆栈的风险!

树形DP

状态表示:d[i],表示所有以i为根的树的深度。

状态转移:对于所有子树,有max(d[son]+edge[i])

这种是暴力枚举。对于一个最长链,肯定有一个层数最小的点。在这一个点处,就可以得到树的直径(最大路径)。
d[son1]+d[son2]+edge1+edge2

有一种方法是求出son[x]+edge x,然后取前两个。

还有书上的思考如下:

可以枚举son1从1到t(子树的个数),son2从1到t,son1不等于son2,求d[son1]+d[son2]+edge1+edge2最大值。

由于具有对称性,所以枚举son1从1到t(子树的个数),son2从1到son1-1,求d[son1]+d[son2]+edge1+edge2最大值。

然后见代码

#define N 305
bool v[N];
int d[N];
int ans = 0;
void dp(int x)
{
    v[x] = 1;
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[y];
        int z = edge[i];
        if(v[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + z);//在这个时候,d[x]仅仅是从1到i-1的最大值。
        //这相当于是枚举son1,取最大的son2属于从1到son1-1
        d[x] = max(d[x], z+d[y]);//更新d[x].
    }
}

两次BFS

第一次,任意选取一个点,求出与这一个点的最远距离的点p

第二次,选取p,求出与p最远的点q。

p到q的路径就是最长链。

证明:

image


AcWing350. 巡逻

在一个地区有 n 个村庄,编号为 1,2,,n

n1 条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任一个村庄。

每条道路的长度均为 1 个单位。

为保证该地区的安全,巡警车每天都要到所有的道路上巡逻。

警察局设在编号为 1 的村庄里,每天巡警车总是从警局出发,最终又回到警局。

为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K 条新的道路,每条新道路可以连接任意两个村庄。

两条新道路可以在同一个村庄会合或结束,甚至新道路可以是一个环。

因为资金有限,所以 K 只能为 12

同时,为了不浪费资金,每天巡警车必须经过新建的道路正好一次。

编写一个程序,在给定村庄间道路信息和需要新建的道路数的情况下,计算出最佳的新建道路的方案,使得总的巡逻距离最小。

输入格式

第一行包含两个整数 nK

接下来 n1 行每行两个整数 ab,表示村庄 ab 之间有一条道路。

输出格式

输出一个整数,表示新建了 K 条道路后能达到的最小巡逻距离。

数据范围

3n100000,

1K2,

1a,bn

输入样例:

8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6 

输出样例:

11

注意同一个点:题目中所说的是每一条道路全部巡逻一遍,而不是每一个点巡逻一遍。

注意:虽然是标记的“简单题”,但是如果直接想出来根本不可能。

网上的各种方法没有严谨的推倒。这里使用欧拉回路进行证明。

欧拉回路中,每一条边都只能被走1次,(原来的路可以认为是有无数条重边,新修的路仅仅只有一条)。

具有欧拉回路的充分必要条件是每一个点的度数均为偶度数。

对于原来的图

image

当在两个点之间连接了边之后,那么这两个点与父亲节点连接的边数应该是1(也可以是3,5…但是1最优)。

经过推理,恰好是两点之间的路径均走过一次。

如果是增加第二条边,那么重叠部分被减为0,与题意不符,所以必须再走这条边!

image

在3-5之间,不能是0条边,应该是2条边。

即,在重叠部分,走过的仍然是2遍。恰好把第一次的最长的边给抵消了。

由此,我们可以得到解题的思路。

第一次,采用BFS进行遍历,并求出方案数。得到最长路径$L_1$然后把最长链上的值改为-1.

第二次,由于有负边权的加入,所以使用树形DP,得到最长路径(直径)$L_2$

最终结果是$2\times (n-1)-L_1-L_2+1+1$

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int n, k;
int head[N], tot;
int ver[N*2], edge[N*2], nxt[N*2];
int pre[N];
queue<int > q;//仅仅供bfs使用,在每一次使用之后,
//这一个队列会清空,所以不需要进行初始化
int d[N];
int L2 = 0;
inline void add(int x, int y)
{
    ver[++tot] = y;
    edge[tot] = 1;
    nxt[tot] = head[x];
    head[x] = tot;
}
int bfs(int w)
{
    memset(d, -1, sizeof(d));
    q.push(w);
    d[w] = 0;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i];
            if(d[y] != -1) continue;
            d[y] = d[x] + 1;
            pre[y] = i;
            q.push(y);
        }
    }
    int p = w;
    for(int i = 1; i <= n; i++) 
        if(d[i] > d[p]) p = i;
    return p;
}
void update(int p, int q)
{
    while(p != q)
    {
        edge[pre[q]] = -1;
        edge[pre[q]^1] = -1;
        q = ver[pre[q]^1];
    }
}
int dp(int x, int fa)
{
    for(int i = head[x]; i; i = nxt[i])
    {
        int y = ver[i];
        if(y == fa) continue;
        dp(y, x);
        L2 = max(L2, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
    return L2;
}
int main()
{
    tot = 1;//这样可以使用成对变化。
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n-1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    int p = bfs(1);
    int q = bfs(p);
    int ans = 2*(n-1) + 1 - d[q];
    if(k == 1)
    {
        printf("%d\n", ans);
        //cout << p <<"  " << q;
        return 0;
    }
    update(p, q);
    memset(d, 0, sizeof(d));
    ans = ans - dp(1, 0) + 1;
    printf("%d\n", ans);

    return 0;
}



xjsc01
12天前

AcWing349. 黑暗城堡

在顺利攻破 Lord lsp 的防线之后,lqr 一行人来到了 Lord lsp 的城堡下方。

Lord lsp 黑化之后虽然拥有了强大的超能力,能够用意念力制造建筑物,但是智商水平却没怎么增加。

现在 lqr 已经搞清楚黑暗城堡有 N 个房间,M 条可以制造的双向通道,以及每条通道的长度。

lqr 深知 Lord lsp 的想法,为了避免每次都要琢磨两个房间之间的最短路径,Lord lsp 一定会把城堡修建成树形的。

但是,为了尽量提高自己的移动效率,Lord lsp 一定会使得城堡满足下面的条件:

D[i] 为如果所有的通道都被修建,第 i 号房间与第 1 号房间的最短路径长度;而 S[i] 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度;要求对于所有整数 i,有 S[i]=D[i] 成立。

为了打败 Lord lsp,lqr 想知道有多少种不同的城堡修建方案。

你需要输出答案对 $2^{31}-1$ 取模之后的结果。

输入格式

第一行有两个整数 NM

之后 M 行,每行三个整数 XYL,表示可以修建 XY 之间的一条长度为 L 的通道。

输出格式

一个整数,表示答案对 $2^{31}-1$ 取模之后的结果。

数据范围

2N1000,

N1MN(N1) / 2,

1L100

输入样例:

3 3
1 2 2
1 3 1
2 3 1

输出样例:

2

做这一道题目,首先要做到心中有数。

首先来他一个Dijkstra,求出原图中的每一个点到1号节点的最短路。

然后进行细细考虑。

对于已经是最短路的情况,对于任意两个点x, y:有$dist[y] [HTML_REMOVED]= dist[x] + z$.

现在考虑$dist[y] [HTML_REMOVED] dist[x] + z$,那么在最短路径生成树中一定不能有这一条边。如果有这一条边,那么y的路径就不是最小的。(因为是树,所以只能是这一个点来对y进行更新)

那么当$dist[y] == dist[x] + z$,最短路径生成树里面可以包含这一条边。

具体做法:

  1. 对于每一个点,都有到达1号点的距离。现在按照距离从小到大对点进行考虑。
  2. 对于考虑到的i个点,查找已经遍历过的集合,看有多少x满足$dist[i] == dist[x] + z$。这是方案数。使用乘法原理。

详细证明:

  1. 从小到大进行考虑。因为边的权值是整数,所以每一个点仅仅可以被小于他的点进行更新。现在已经考虑完所有比他小的点的情况。满足“拓扑序”要求
  2. 因为对于一个点,类似于动态规划,其对后面的点的影响,仅仅与他的dist有关系。而与他之前是如何走过来的没有关系。所有可以使用乘法原理!

代码实现简直就是套板子,重点是对于过程的理解!!!

图比较稠密,还是使用邻接矩阵存储,并且使用$n^2$ 的Dijkstra靠谱呀。

#include <bits/stdc++.h>
using namespace std;
#define N 1020
int a[N][N];
int n, m;
int d[N];
bool v[N];
typedef long long ll;
const long long mod = (ll)(1LL << 31) - 1;//不是(ll)(1 << 31) - 1;
pair<int, int > nodes[N];
int main()
{
    ll ans = 1;
    scanf("%d%d", &n, &m);
    memset(a, 0x3f, sizeof(a));
    for(int i = 1; i <= n; i++) a[i][i] = 0;//注意:这里自己到自己可能会更新。如果下面不使用v,那么这一条语句应该删除。
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = a[y][x] = min(a[x][y], z);
    }

    //dijkstra
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = 0;
        for(int j = 1; j <= n; j++)
            if(!v[j] && (x == 0 || d[x] > d[j])) x = j;
        v[x] = 1;
        for(int y = 1; y <= n; y++)
        {
            d[y] = min(d[y], d[x] + a[x][y]);   
        }
    }

    //加入nodes中
    for(int i = 1; i <= n; i++) nodes[i] = make_pair(d[i], i);
    sort(nodes+1, nodes+1+n);

    memset(v, 0, sizeof(v));
    v[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        int y = nodes[i].second;
        int cnt = 0;
        for(int x = 1; x <= n; x++) if(v[x])
        {
            if(d[x] + a[x][y] == d[y]) cnt ++;
        }
        ans = ans * cnt % mod;
        v[y] = 1;
    }
    printf("%lld\n", ans);
}

另一种:

#include <bits/stdc++.h>
using namespace std;
#define N 1020
int a[N][N];
int n, m;
int d[N];
bool v[N];
typedef long long ll;
const long long mod = (ll)(1LL << 31) - 1;//不是(ll)(1 << 31) - 1;
pair<int, int > nodes[N];
int main()
{
    ll ans = 1;
    scanf("%d%d", &n, &m);
    memset(a, 0x3f, sizeof(a));
    //for(int i = 1; i <= n; i++) a[i][i] = 0;//注意:这里自己到自己可能会更新。如果下面不使用v,那么这一条语句应该删除。
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = a[y][x] = min(a[x][y], z);
    }

    //dijkstra
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = 0;
        for(int j = 1; j <= n; j++)
            if(!v[j] && (x == 0 || d[x] > d[j])) x = j;
        v[x] = 1;
        for(int y = 1; y <= n; y++)
        {
            d[y] = min(d[y], d[x] + a[x][y]);   
        }
    }

    //加入nodes中
    for(int i = 1; i <= n; i++) nodes[i] = make_pair(d[i], i);
    sort(nodes+1, nodes+1+n);

    //memset(v, 0, sizeof(v));
    //v[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        int y = nodes[i].second;
        int cnt = 0;
        for(int x = 1; x <= n; x++) 
        {
            if(d[x] + a[x][y] == d[y]) cnt ++;
        }
        ans = ans * cnt % mod;
    }
    printf("%lld\n", ans);
}




xjsc01
15天前

342. 道路与航线

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 T 个城镇,编号为 1T

这些城镇之间通过 R 条道路 (编号为 1R) 和 P 条航线 (编号为 1P) 连接。

每条道路 i 或者航线 i 连接城镇 Ai 到 Bi,花费为 Ci。

对于道路,0Ci10,000;然而航线的花费很神奇,花费 Ci 可能是负数(10,000Ci10,000)。

道路是双向的,可以从 Ai 到 Bi,也可以从 Bi 到 Ai,花费都是 Ci。

然而航线与之不同,只可以从 Ai 到 Bi。

事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策:保证如果有一条航线可以从 Ai 到 Bi,那么保证不可能通过一些道路和航线从 Bi 回到 Ai。

由于约翰的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。

[HTML_REMOVED]输入格式[HTML_REMOVED]

第一行包含四个整数 T,R,P,S

接下来 R 行,每行包含三个整数(表示一个道路)Ai,Bi,Ci。

接下来 P 行,每行包含三个整数(表示一条航线)Ai,Bi,Ci。

输出格式

1..T 行:第 i 行输出从 S 到达城镇 i 的最小花费,如果不存在,则输出 NO PATH

[HTML_REMOVED]数据范围[HTML_REMOVED]

1T25000,

1R,P50000,

1A~i,~B~i~,ST

[HTML_REMOVED]输入样例:[HTML_REMOVED]

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

输出样例:

NO PATH
NO PATH
5
0
-95
-100

谨慎谨慎:这道题目最最最暴力的方法就是SPFA,但是会卡住。

某一些奇奇怪怪的优化可以过,但是想要卡这一些优化也是可以的。

与其用各种方法与出题人斗智斗勇,还不如思考这道题目的正确解法。

题目思路简单描述:

由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策:保证如果有一条航线可以从 Ai 到 Bi,那么保证不可能通过一些道路和航线从 Bi 回到 Ai。

其实这一个条件并不是求最短路的方法,但是题目明显暗示,这启示我寻找其他求最短路的方法。

即:把公路以及航线分开考虑:

公路相当于是双向边,凡是可以由公路连起来的地方都是双向连通的。所以可以把由公路连接起来的地方看成一个个块,块之间是相互可达的。

但是航线只能从一个地方到另一个地方,之后,另一个地方就回不去了。所以:航线是连接的两个不同的块(并且只有一条单向的)

航线和块构成了有向无环图,可以使用拓扑排序进行求解。(负边不受影响)

在每一个块内部,边是非负的,所以直接进行“堆优化的迪杰斯特拉”

更多解释详细见代码

#include <bits/stdc++.h>
using namespace std;
#define M 150020//海上加路上*2
#define N 25020
int n, m, p, s;
int head[N], tot;
int edge[M], ver[M], nxt[M], mark[M];//0表示双向,1表示只可以从x到y
int c[N], cnt = 0;//c表示某一个点所属于的集合(块),cnt是c的计数
vector<int >bloc[N];//在第i个块里面的所有点(方便迪杰斯特拉把所有点加入到heap中)
int deg[N];//注意:这个还是块的度!!!
stack<int > st;//拓扑排序可以使用栈,也可以用队列
int d[N];//到起点的距离
//小根堆
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >heap;
bool v[N];//迪杰斯特拉模板中的v
inline void add(int x, int y, int z, int k)
{
    tot++;
    ver[tot] = y, edge[tot] = z, mark[tot] = k;
    nxt[tot] = head[x], head[x] = tot;
}
void dfs(int x)//标记第一个块里面的点属于哪一个块(拓扑序中减去入度需要使用)
{
    c[x] = cnt;
    for(int _ = head[x]; _; _ = nxt[_])
    {
        if(mark[_] == 1) continue;
        int y = ver[_];
        if(!c[y]) dfs(y);
    }
}
void dijkstra(int k)
{//heap不需要进行初始化,因为上一次执行完以后就是空的
 //v也不需要,因为不冲突着
    for(int x : bloc[k]) heap.push(make_pair(d[x], x));
    //迪杰斯特拉的神奇用法:可能不只一个点是从其他地方过来的,并且也不知道是哪一个点,所以全部存起来
    while(!heap.empty())
    {
        int x = heap.top().second;
        heap.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int _ = head[x]; _; _ = nxt[_])
        {
            int y = ver[_], z = edge[_];
            if(mark[_] == 1)//对下一个块的拓扑排序
            {
                d[y] = min(d[y], d[x] + z);
                deg[c[y]]--;
                if(deg[c[y]] == 0) st.push(c[y]);
            }
            else//迪杰斯特拉
            {
                if(d[y] > d[x] + z)
                {
                    d[y] = d[x] + z;
                    heap.push(make_pair(d[y], y));
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &p, &s);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, 0);
        add(y, x, z, 0);
    }
    for(int i = 1; i <= p; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, 1);
    }
//标记块:
    for(int i = 1; i <= n; i++)
    {
        if(!c[i]) {
            cnt++;
            dfs(i);
        }
    }
//得到某一个块的所有点
    for(int i = 1; i <= n; i++) bloc[c[i]].push_back(i);

    for(int x = 1; x <= n; x++)
    {
        for(int j = head[x]; j; j = nxt[j])
        {
            if(mark[j] == 0) continue;
            int y = ver[j];
            deg[c[y]] ++;
        }
    }
    for(int k = 1; k <= cnt; k++) if(deg[k] == 0) st.push(k);

    memset(d, 0x3f, sizeof(d));
    d[s] = 0;

    while(!st.empty())
    {
        int k = st.top();
        st.pop();
        dijkstra(k);//注意:在这里面既进行了迪杰斯特拉,顺便算了一topu序
    }

    for(int i = 1; i <= n; i++) 
    {
        if(d[i] > 10000 * n) puts("NO PATH");
        else printf("%d\n", d[i]);
    }
    return 0;
}



xjsc01
15天前

AcWing341. 最优贸易

C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。

任意两个城市之间最多只有一条道路直接相连。

m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 1 条。

C 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。

但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。

当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚一点旅费。

Cn 个城市的标号从 1n,阿龙决定从 1 号城市出发,并最终在 n 号城市结束自己的旅行。

在旅游的过程中,任何城市可以被重复经过多次,但不要求经过所有 n 个城市。

阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品——水晶球,并在之后经过的另一个城市卖出这个水晶球,用赚取的差价当做旅费。

因为阿龙主要是来 C 国旅游,他决定这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。

现在给出 n 个城市的水晶球价格,m 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。

请你告诉阿龙,他最多能赚取多少旅费。

注意:本题数据有加强。

输入格式

第一行包含 2 个正整数 nm,中间用一个空格隔开,分别表示城市的数目和道路的数目。

第二行 n 个正整数,每两个整数之间用一个空格隔开,按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行,每行有 3 个正整数,xyz,每两个整数之间用一个空格隔开。

如果 z=1,表示这条道路是城市 x 到城市 y 之间的单向道路;如果 z=2,表示这条道路为城市 x 和城市 y 之间的双向道路。

输出格式

一个整数,表示答案。

数据范围

1n100000,

1m500000,

1≤各城市水晶球价格100

输入样例:

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

输出样例:

5

思路:

如果硬是要找一条路,其实有一点不太现实。没有办法枚举所有的路线。但是可以像动态规划一样,求出一个点的转状态。

结合题目中的意思,需要在来这一个点的时候找到一个最大值,离开这一个点的时候找一个最小值就可以。

有两个数组,$f$数组里存放从开头到该点的途径的最大值,$g$数组里存放到这一个点的最小的值。

这里是点带权,与边带权相似。

注意:不能使用djs,因为它的贪心不再成立[HTML_REMOVED]当求最大值的时候,小的也可以更新大的。

所以改用SPFA算法。

最后的理想状态是对于所有的边x->y,f[y] = max(f[y], f[x])

虽然一次不可以,但是基于SPFA的迭代思想,多次就可以。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define N 100008
#define M 1000010
int head[N], tot = 1;
int ver[M], nxt[M], edge[M];
int a[N];//价值
int f[N];//min 1-x
int g[N];//max x-n
bool v[N];
queue<int >q;
inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
void spfa(int n, int st, int z, int *d)
{
    //v和q没有必要初始化
    d[st] = a[st];
    q.push(st);
    v[st] = true;
    while(!q.empty())
    {
        int x = q.front();
        q.pop(), v[x] = false;
        //cout << x << "   ";
        for(int _ = head[x]; _; _ = nxt[_])
            if(edge[_] == 2 || edge[_] == z)
            {
                int y = ver[_];
                if(z == 1) {
                    int t = min(d[x], a[y]);
                    if(t < d[y])
                    {
                        d[y] = t;
                        if(!v[y]){
                            q.push(y);
                            v[y] = true;
                        }
                    }
                }
                else {
                    int t = max(d[x], a[y]);
                    if(t > d[y])
                    {
                        d[y] = t;
                        if(!v[y]){
                            q.push(y);
                            v[y] = true;
                        }
                    }
                }
            }
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z == 2?2:-1);
    }
    memset(f, 0x3f, sizeof(f));
    spfa(n, 1, 1, f);
    memset(g, 0xcf, sizeof(g));
    spfa(n, n, -1, g);
    int ans = 0;
    for(int i =1; i <= n; i++)
    {
        ans = max(ans, g[i]-f[i]);
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++)
    {
        //printf("%d\t\t\t%d\t\t\t%d\n", i, f[i], g[i]);
        //cout << a[i] << "  ";
    }
    return 0;
}



xjsc01
15天前

广搜变形——双端队列BFS(0-1 BFS)

使用范围:求解边权只有0以及1的图的最短路。

时间复杂度:m(但是deque的常数也还比较大)

思路:每一次取出队头的元素,如果有更新,那么就更新。

  1. 边权是1,从堆尾插入
  2. 边权是0,从队首插入

特别的,可能会有一个元素多次入队,仅仅需要注意第一次入队,不用在意其他几次入队。

严格证明:

广度优先搜索,假设把每一个点的每一次拓展算作一步(即所有的边权值为1),那么可以一直搜索,得到层数。这个层数就是这一个点到root的最短路。

要证明:任意一个时刻,队列里面的点的层数最多有两种不同的层数

数学归纳法1:

在最一开始,只有第0层的点root,显然满足。

数学归纳法2:

假设在某一个时刻,里面只有k-1层的点,

[k-1, k-1, k-1 .... ]

那么拿出k-1,把k层的放到后面即下面的情况:

队列里面仅仅会有两个相邻层数的点,记作$k, k+1$层。

[k, k, k, k, k+1, k+1, k+1]

随着把队头的k拿出,广度搜索一下,得到k+1层,放到最后面。

当有一个时刻,队列里面全部是k+1.

继续,拿出k+1,把k+2放到队尾....

由1,2所得到,任意一个时刻,队列里面的点的层数最多有两种不同的层数k和k+1

so,在任意一个时刻,队头的是k,

如果边的权值是1,那么得到的元素的点在k+1层,放在队列的末尾。
如果是0,那么放在队列的前面


AcWing\340. 通信线路

image-20220802115420708

输入样例:

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例:

4

image

动态规划和图之间的关系非常紧密

动态规划的实质:在一张有向无环图中,按照拓扑序进行一次遍历。

动态规划的状态表示d[i][j]:从 1 号到第 i 个节点处,使用了 j 条免费的额度,剩下的边中的最贵的那一个。

通过 j 把图分为若干层。


方法一:分层图套上DJS

——采用多层图进行求解。

注:实际上仅仅存一层就可以了。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1020, MAX_M = 20005;//重大失误:是双向图,应该是两倍的边!!!
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, k, d[MAX_N][MAX_N];
bool v[MAX_N][MAX_N];
// pair<-dist[x], pair<x, j>>
priority_queue< pair<int , pair<int, int> >  >q;

inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
int main()
{
    int n, p, k;
    scanf("%d%d%d", &n, &p, &k);
    for(int i = 1; i <= p; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    memset(d, 0x7f, sizeof(d));//3f也可以
    d[1][0] = 0;
    q.push(make_pair(0, make_pair(1, 0)));
    while(!q.empty())
    {
        int i = q.top().second.first, j = q.top().second.second;
        q.pop();
        if(v[i][j]) continue;
        v[i][j] = 1;
        for(int _ = head[i]; _ ; _ = nxt[_])
        {
            int y = ver[_], z = edge[_];
            if(d[y][j] > max(d[i][j], z)) 
            {
                d[y][j] = max(d[i][j], z);
                q.push(make_pair(-d[y][j], make_pair(y, j)));
            }
            if(j < k && d[y][j+1] > d[i][j])
            {
                d[y][j+1] = d[i][j];
                q.push(make_pair(-d[y][j+1], make_pair(y, j+1)));
            }
        }
    }
    int ans = 0x7f7f7f7f;
    for(int i = 0; i <= k; i++) ans = min(ans, d[n][i]);
    if(ans == 0x7f7f7f7f) puts("-1");
    else printf("%d\n", ans);

    return 0;
}

方法二:分层图套上SPFA

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define M 20010
int head[N], tot;;
int ver[M], nxt[M], edge[M];
int d[N][N];
bool v[N][N];
queue<pair<int, int > > q;
inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    memset(d, 0x3f, sizeof(d));
    d[1][0] = 0;
    q.push(make_pair(1, 0));
    v[1][0] = true;
    while(!q.empty())
    {
        int x = q.front().first, j = q.front().second;
        q.pop();
        v[x][j] = false;
        for(int xx = head[x]; xx; xx = nxt[xx])
        {
            int y = ver[xx], z = edge[xx];
            if(d[y][j] > max(d[x][j], z))
            {
                d[y][j] = max(d[x][j], z);
                if(!v[y][j]){
                    q.push(make_pair(y, j));
                    v[y][j] = true;
                }
            }
            if(j < k && d[y][j+1] > d[x][j])
            {
                d[y][j+1] = d[x][j];
                if(!v[y][j+1]){
                    q.push(make_pair(y, j+1));
                    v[y][j+1] = true;
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 0; i <= k; i ++)
    {
        ans = min(ans, d[n][i]);
    }
    //for(int i = 0; i <= k; i++) cout << d[n][i] << "  ";
    if(ans == 0x3f3f3f3f) puts("-1");
    else printf("%d", ans);
    return 0;
}

重中之重:最后的循环寻找答案部分不可以去!!

int ans = 0x3f3f3f3f;
    for(int i = 0; i <= k; i ++)
    {
        ans = min(ans, d[n][i]);
    }

如果直接取d[n][k],那么就会发生以下问题:

输入:

2 1 2
1 2 5

输出:

i = 0    d[n][i] = 5
i = 1    d[n][i] = 0
i = 2    d[n][i] = 5

正确答案应该是0,但是我的结果是5.

方法三:二分答案+双端队列BFS

H氏二分分析法

二分的思路:假设答案是x,

合理性判断:当大于x的边的个数小于等于k,那么合法(要求大于等于x的边的最短个数,可以使用广搜变形1

二分单调性判断:显然。

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define M 20005//注意要开两倍
int head[N], tot;
int ver[M], nxt[M], edge[M];
//bool v[N];
int d[N];
deque<int > q;
inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
bool judge(int n, int k, int val)
{
    for(int i = 0; i <= n; i++)
    {
//        v[i] = false;
        d[i] = 0x3f3f3f3f;
    }
    q.clear();
    d[1] = 0;
    q.push_back(1);
//    v[1] = true;
    while(!q.empty())
    {
        int x = q.front();
        q.pop_front();
        for(int _ = head[x]; _; _ = nxt[_])
        {
            int y = ver[_], z = edge[_]>val?1:0;
            if(d[y] > d[x] + z)
            {
                d[y] = d[x] + z;
                if(z) q.push_back(y);
                else q.push_front(y);
            }
        }
    }
    if(d[n] <= k) return true;
    else return false;
}
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    int l = 0, r = 0x3f3f3f3f;
    while(l < r)
    {
        int mid = (l+r)>>1;
        if(judge(n, k, mid)) r =mid;
        else l = mid+1;
    }
    if(l == 0x3f3f3f3f) puts("-1");
    else printf("%d\n", l);
    return 0;
}

  1. 广搜变形: 




xjsc01
17天前

采用邻接表 + 堆优化

在操作中,需要对堆有3个操作:插入,删除,修改。

手写一个堆就可以全部实现,但是比较麻烦。这里使用priority_queue

  1. 插入:push
  2. 删除:pop
  3. 修改:看成先删除(没有办法直接删除,采用懒惰删除)再增加(push)

对于懒惰删除的详细解释:修改实质上是更新,更新之后,会优先出队,所以更新之后的值比原值先出来。更新之前的就相当于是“垃圾”,当轮到它时,进行合法性判定。

时间复杂度的详细解释:

对所有点进行遍历,对边进行遍历,所以是(m+n)
在优先队列里面实际上存储的最多的个数应该是边的个数,所以是logM,但是$M\le N^2$,替换后还是2logN

对于数据范围的考虑:

  1. 最大值一定是最大值吗?
    在这里可能到最后,d数组中会有$1.5\times 10^9,已经比0x3f3f3f3f大。所以:
    memset(d, 0x7f, sizeof(d));
  2. 用不用开long long:
    从以下两个方面进行考虑:
    (1)结果会不会爆int?答:不会。
    (2)运算过程中会不会爆?答:不会。d[y] = d[x] + z;没有什么大问题!
#include <bits/stdc++.h>
using namespace std;
#define N 150020
int ver[N], nxt[N], edge[N];
int head[N];
int tot = 0;
bool v[N];
int d[N];
priority_queue<pair<int, int> , vector<pair<int, int> >,greater<pair<int, int> > >q;
inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;//注意不是d[0] = 0;
    q.push(make_pair(d[1], 1));
    while(!q.empty())
    {
        int x = q.top().second;
        //cout << x;
        q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i], z = edge[i];
            if(d[x]+z < d[y]){
                d[y] = d[x] + z;
                q.push(make_pair(d[y], y));
            }
        }
    }
    //for(int i = 0; i <= n; i++) cout << d[i] << "  ";
    if(d[n] == 0x7f7f7f7f) puts("-1");
    else printf("%d\n", d[n]);
    return 0;
}



xjsc01
17天前

采用邻接表 + 堆优化

在操作中,需要对堆有3个操作:插入,删除,修改。

手写一个堆就可以全部实现,但是比较麻烦。这里使用priority_queue

  1. 插入:push
  2. 删除:pop
  3. 修改:看成先删除(没有办法直接删除,采用懒惰删除)再增加(push)

对于懒惰删除的详细解释:修改实质上是更新,更新之后,会优先出队,所以更新之后的值比原值先出来。更新之前的就相当于是“垃圾”,当轮到它时,进行合法性判定。

时间复杂度的详细解释:

对所有点进行遍历,对边进行遍历,所以是(m+n)
在优先队列里面实际上存储的最多的个数应该是边的个数,所以是logM,但是$M\le N^2$,替换后还是2logN

对于数据范围的考虑:

  1. 最大值一定是最大值吗?
    在这里可能到最后,d数组中会有$1.5\times 10^9,已经比0x3f3f3f3f大。所以:
    memset(d, 0x7f, sizeof(d));
  2. 用不用开long long:
    从以下两个方面进行考虑:
    (1)结果会不会爆int?答:不会。
    (2)运算过程中会不会爆?答:不会。d[y] = d[x] + z;没有什么大问题!
#include <bits/stdc++.h>
using namespace std;
#define N 150020
int ver[N], nxt[N], edge[N];
int head[N];
int tot = 0;
bool v[N];
int d[N];
priority_queue<pair<int, int> , vector<pair<int, int> >,greater<pair<int, int> > >q;
inline void add(int x, int y, int z)
{
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;//注意不是d[0] = 0;
    q.push(make_pair(d[1], 1));
    while(!q.empty())
    {
        int x = q.top().second;
        //cout << x;
        q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = ver[i], z = edge[i];
            if(d[x]+z < d[y]){
                d[y] = d[x] + z;
                q.push(make_pair(d[y], y));
            }
        }
    }
    //for(int i = 0; i <= n; i++) cout << d[i] << "  ";
    if(d[n] == 0x7f7f7f7f) puts("-1");
    else printf("%d\n", d[n]);
    return 0;
}



xjsc01
17天前

邻接表时间复杂度是$n^2$

#include <bits/stdc++.h>
using namespace std;
#define N 505
int n, m;
int a[N][N], d[N];
bool v[N];
int main()
{
    scanf("%d%d", &n, &m);
    //初始化邻接矩阵
    memset(a, 0x3f, sizeof(a));
    //时间复杂度:这里已经是n^2了
    for(int i = 1; i <= n; i++) a[i][i] = 0;

    //read
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = min(a[x][y], z);//这一个是为了防止有重边。
    }
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    for(int cnt = 1; cnt <= n; cnt++)
    {
        int min_val = 0x3f3f3f3f, pos;
        for(int i = 1; i <= n; i++)
        {
            if(!v[i] && d[i] < min_val)
            {
                min_val = d[i];
                pos = i;
            }
        }
        v[pos] = true;
        for(int i = 1; i <= n; i++)
        {
            d[i] = min(d[i], d[pos] + a[pos][i]);
            //不用判断是不是存在边,如果不存在,本来就是负无穷
        }
    }
    if(d[n] == 0x3f3f3f3f) puts("-1");
    else printf("%d", d[n]);
    return 0;
}