首页 > 其他分享 >dijkstra 求最小环（ CCPC桂林 - E. Buy and Delete ）

dijkstra 求最小环（ CCPC桂林 - E. Buy and Delete ）

时间：2022-10-22 20:00:49浏览次数：66  
标签：Buy dist tx int CCPC st dijkstra push define

原文

题意经过转化后，本质就是求最小环。

有向图有以下三种实现方式，而无向图只能用第一种实现方式。

  1. 实现方式1：删边求最短距离
  2. 有向图实现方式2：回到起点构成环
  3. 有向图实现方法3：任意两点间的最短距离

删边求最短距离

这种实现方法有向图无向图都可用。

  • 如果是无向图必须用这种
  • 如果是有向图边数和点数差不多是也可以使用。

对于一条有向边 \((u,v)\)，可以删掉这条边（不用这条边更新）跑从 v 到 u 的最短距离，加上这条边的权值便是该边所在的最小环。

对于每条边都求一次最短路，所以时间复杂度：\(O(m∗mlogn)\)。

有向图代码

有向图不需要删除边 \((a,b)\) ，因为是求的 \(dij(b,a)\) 会自动忽略边 \((a,b)\);

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

const int N = 50010, mod = 1e9 + 7;
int T, n, m, k;
int a[N], c;
int dist[N], f[N];
vector<PII> e[N];
int mina = 1e9; //最小环权值

struct node
{
    int x, y, w;
} b[N];

int dij(int st, int en)
{
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, st});

    for (int i = 1; i <= n; i++)
        dist[i] = 1e10, f[i] = 0;
    dist[st] = 0;

    while (que.size())
    {
        int x = que.top().se;
        que.pop();

        if (f[x])
            continue;
        f[x] = 1;

        for (auto it : e[x])
        {
            int tx = it.fi, w = it.se;

            if (dist[tx] > dist[x] + w)
                dist[tx] = dist[x] + w, que.push({dist[tx], tx});
        }
    }
}

signed main()
{
    Ios;
    cin >> n >> m;

    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].pb({y, z});

        b[i] = {x, y, z};
    }

    for (int i = 1; i <= m; i++)
    {
        int x = b[i].x, y = b[i].y, w = b[i].w;
        dij(y, x);
        mina = min(mina, dist[x] + w); //从y到x的最短距离加上从x到y的这条边就是这个边所在的最小环
    }

    cout << mina;

    return 0;
}

无向图代码

有向图需要对边 \((a,b)\) 进行continue处理

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

const int N = 50010, mod = 1e9 + 7;
int T, n, m, k;
int a[N], c;
int dist[N], f[N];
vector<PII> e[N];
int pre[N];

struct node
{
    int x, y, w;
} b[N];

int dij(int st, int en)
{
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, st});

    for (int i = 1; i <= n; i++)
        dist[i] = 1e10, f[i] = 0, pre[i] = 0;
    dist[st] = 0;

    while (que.size())
    {
        int x = que.top().se;
        que.pop();

        if (f[x])
            continue;
        f[x] = 1;

        for (auto it : e[x])
        {
            int tx = it.fi, w = it.se;
            if (x == st && tx == en || x == en && tx == st)
                continue; // st-en这条边不能走

            if (dist[tx] > dist[x] + w)
                dist[tx] = dist[x] + w, que.push({dist[tx], tx}), pre[tx] = x;
        }
    }
}

signed main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].pb({y, z});
        e[y].pb({x, z});

        b[i] = {x, y, z};
    }

    stack<int> stk;

    int mina = 1e9;
    for (int i = 1; i <= m; i++)
    {
        int x = b[i].x, y = b[i].y, w = b[i].w;

        dij(y, x);
        if (dist[x] + w < mina)
        { //记录最小环中的所有点
            mina = dist[x] + w;
            while (stk.size())
                stk.pop();

            int t = x;
            while (t)
                stk.push(t), t = pre[t];
        }
    }

    cout << mina << endl;
    if (!stk.size())
        cout << "No solution.";
    while (stk.size())
        cout << stk.top() << " ", stk.pop();

    return 0;
}

回到起点构成环

只能用于有向图，推荐使用这个，时间复杂度：\(O(n∗mlogn)\) 会比第一种速度快。

思想：
将每一个点都作为起点，跑 \(dijkstra(u,u)\)。
对于每个点，从该点出发判断是否能够再回到起点，如果能，说明从该点出发能构成环。
因为是跑最短路求得的，所以这个环是 所有从起点出发回到起点的环中 权值最小的一个。
将所有点作为起点所得的最小环的最小值 便是 整张图的最小环。

每个点都跑一遍 dij，所以 时间复杂度：\(O(n∗mlogn)\)。

有向图代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

const int N = 200010, mod = 1e9 + 7;
int T, n, m, k;
int a[N], c;
int dist[N], f[N];
vector<PII> e[N];
int mina = 1e18; //最小环大小

void dij(int st)
{
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, st});
    for (int i = 1; i <= n; i++)
        dist[i] = 1e9, f[i] = 0;
    dist[st] = 0;

    while (que.size())
    {
        int x = que.top().se;
        que.pop();

        if (f[x])
            continue;
        f[x] = 1;

        for (auto it : e[x])
        {
            int tx = it.first, w = it.second;

            if (tx == st)
                mina = min(mina, dist[x] + w); 
                //下一个节点是起点，那么环的大小就是起点到当前点距离+到起点这条边的权值。

            if (dist[tx] > dist[x] + w)
                dist[tx] = dist[x] + w, que.push({dist[tx], tx});
        }
    }
}

signed main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].pb({y, z});
    }
    for(int i=1;i<=n;i++)
        dij(i);

    cout << mina;
    return 0;
}

任意两点间的最短距离

对于每个点都跑一遍最短路，便得到任意两点间的最短距离。

那么从 x 点到 y 点的最短距离 + 从 y 点到 x 点的最短距离 便构成了一个最小环。
二重遍历所有组合，取所有环中的最小值便是整张图的最小环。

每个点都求一次最短路，所以时间复杂度：\(O(n∗mlogn)\)。

有向图代码

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second

const int N = 5010, mod = 1e9 + 7;
int T, n, m, k;
int a[N], c;
int dist[N][N], f[N];
vector<PII> e[N];

int dij(int st)
{
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, st});

    for (int i = 1; i <= n; i++)
        dist[st][i] = 1e10, f[i] = 0;
    dist[st][st] = 0;

    while (que.size())
    {
        int x = que.top().se;
        que.pop();

        if (f[x])
            continue;
        f[x] = 1;

        for (auto it : e[x])
        {
            int tx = it.fi, w = it.se;

            if (dist[st][tx] > dist[st][x] + w)
                dist[st][tx] = dist[st][x] + w, que.push({dist[st][tx], tx});
        }
    }
}

signed main()
{
    Ios;
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].pb({y, z});
    }

    for (int i = 1; i <= n; i++)
        dij(i);

    int mina = 1e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
                mina = min(mina, dist[i][j] + dist[j][i]);
        }

    cout << mina;

    return 0;
}

题目代码

因为没有学过dij求最小环，所以使用了第一种方法来求。结果被t疯了。后来面前通过剪枝通过。
代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2005, M = 5005;
const int INF = 0x3f3f3f3f;
int n, m, c;
int h[N], w[M], e[M], ne[M], idx; // 邻接表存储所有边
int dist[N];                      // 存储所有点到1号点的距离
bool st[N];                       // 存储每个点的最短距离是否已确定
void add(int u, int v, int ww)
{
    e[idx] = v;
    ne[idx] = h[u];
    w[idx] = ww;
    h[u] = idx++;
}
int ans = INF;
int dijkstra(int u, int v)
{
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    for (int i = 0; i <= n; i++)
        st[i] = 0;
    dist[u] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, u}); // first存储距离，second存储节点编号

    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver])
            continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                if (dist[j] >= ans)
                    continue;
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[v] == INF)
        return -1;
    return dist[v];
}

signed main()
{
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 0; i <= n; i++)
        h[i] = -1;
    int mi = INF;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        mi = min(w, mi);
    }
    if (mi > c)
        return puts("0"), 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int sum = dijkstra(e[j], i);
/*重要剪枝*/
            if(w[j]>=c) continue;
            if (sum == -1)
                continue;
            ans = min(ans, sum + w[j]);
        }
    }
    if (ans <= c)
        puts("2");
    else
        puts("1");
}

标签：Buy,dist,tx,int,CCPC,st,dijkstra,push,define
From： https://www.cnblogs.com/kingwz/p/16817157.html

相关文章

  • 算法 -Dijkstra算法
    以这个图为例，找到从起点到终点的耗时最短的路径（圆圈连线上的数字代表耗时）。graph={}graph["start"]={}graph["start"]["a"]=6graph["start"]["b"]=2graph["a"]={}graph["a......
  • 2022 CCPC河南省赛
    AMocha上小班啦题意求有n位且每位数字都不同的最小正整数1≤n≤20签到题Bhash分析：其实很好想到dp但是数据范围不允许n方考虑本题的性质发现长度超过15......
  • 2020CCPC威海 C Rencontre（树形DP，期望）
    题意：有3个人，每个人有一些待选位置。就是当确定三个人确定位置u1,u2,u3后，需要找到一个位置v到三个位置的距离之和最小，现在给出u1,u2,u3的待选取值，问距离......
  • Buy a house
    最近想买房子，记录一下一些信息贷款假设借了12w元，月利率0.5%，1年还请(12期)。(https://www.zhihu.com/zvideo/1385957708458340352?utm_source=wechat_session&utm_medium=soc......
  • SQLBackupAndFTP Features & PricesDownloadBuyLinuxMore 备份数据库到对象存储
    额，最近妖孽又开始泛滥了，怎么能把数据库备份到对象存储，避免丢数据SQLBackupAndFTPDownloadSQL备份和FTP可以做什么？SQLBackupAndFTP是一款软件，用于备份SQLServer、......
  • ac 849 dijkstra
    时间复杂度为n^2#include<bits/stdc++.h>usingnamespacestd;constintN=510;intn,m;intdist[N];//每个点到起点的最短距离boolst[N];//判断某个点......
  • 【2022 CCPC Henan Provincial Collegiate Programming Contest #K】复合函数
    题目链接K.复合函数输入文件：standardinput输出文件：standardoutput时间限制：1second空间限制：512megabytes给定正整数\(n\)，并记\(I_n={1,2,\cdots,n}\)。给定......
  • 【施工中，已完成C】2021 CCPC 女生专场（TeamVP）
    比赛相关信息比赛信息比赛名称：2021年中国大学生程序设计竞赛女生专场比赛地址：Gym补题全部参赛队伍：（非官方）257队金：（非官方）Rk35，6题，710m银：（非官方）Rk105，5题，330m......
  • 2021 CCPC 威海站 VP记录(题解)
    2021CCPC威海站VP记录(题解)题目顺序为vp时开题顺序:A-Goodbye,Ziyin!签到，连边数小于等于2的可以作为二叉树根，若有大于4的直接输出0。code:voidsolve(){ int......
  • 2020CCPC秦皇岛-K. Kingdom's Power（树形DP + 贪心）
    题意给出一个有n个节点的有根树，1为根节点，根节点有无穷多个兵，每一秒可以让任意一个兵向任意一个地方移动一步，兵所到的点被占领，问最少需要经过多少秒，才能将所有的点都占领......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99