UVa247 Calling Circles(Floyd warshall算法)

这篇具有很好参考价值的文章主要介绍了UVa247 Calling Circles(Floyd warshall算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题意

给定两个人相互打电话,如果a打给b,b打给c,c打给a,则说a,b,c在同一电话圈中。给出n个人的m次通话,输出所有的电话圈

思路

用graph[u][v]=1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]=1表示u,v之间有直接或者间接打电话。如果graph[u][v] = 1并且graph[v][u]=1,说明u和v是在同一个电话圈

代码如下文章来源地址https://www.toymoban.com/news/detail-660097.html

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)

int n, m;
int graph[N][N];
bool vis[N];
map<string, int> nameMap;
vector<string> names;


int getId(const string& name)
{
    if (!nameMap.count(name))
    {
        int size = names.size();
        nameMap[name] = size;
        names.push_back(name);
    }


    return nameMap[name];
}

void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int main()
{
    fastio();

    #ifndef ONLINE_JUDGE
        ifstream fin("f:\\OJ\\uva_in.txt");
        streambuf* back = cin.rdbuf(fin.rdbuf());
    #endif

    int kase = 1;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) {
            break;
        }

        if (kase > 1) {
            cout << endl;
        }

        nameMap.clear();
        names.clear();
        memset(graph, 0, sizeof(graph));
        fill(vis, vis + N, false);
        _for(i, 0, m) {
            string a, b;
            cin >> a >> b;
            int u = getId(a);
            int v = getId(b);
            graph[u][v] = 1;
        }

        _for(k, 0, n) {
            _for(i, 0, n) {
                _for(j, 0, n) {
                    graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);
                }
            }
        }

        cout << "Calling circles for data set " << kase << ":" << endl;
        _for(u, 0, n) {
            if (vis[u]) {
                continue;
            }

            vis[u] = true;
            cout << names[u];

            _for(v, 0, n) {
                if (!vis[v] && graph[u][v] && graph[v][u]) {
                    vis[v] = true;
                    cout << ", " << names[v];
                }
            }

            cout << endl;
        }

        kase++;
    }


    #ifndef ONLINE_JUDGE
        cin.rdbuf(back);
    #endif

    return 0;
}

到了这里,关于UVa247 Calling Circles(Floyd warshall算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Warshall算法

    🚀write in front🚀 📜所属专栏: 算法 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   Warshall算法是一种经典的 图论算

    2024年01月21日
    浏览(33)
  • WarShall算法求传递闭包(可达矩阵)

    最近在复习离散数学,顺便记录记录自己对warshall算法的理解。 传递闭包是有向图的一个重要性质,它指的是在有向图中从任意一个节点出发,可以到达的所有节点的集合。在某些应用中,需要求解给定有向图的传递闭包,以便更好地分析和理解图的结构和性质。 步骤如下:

    2024年02月08日
    浏览(35)
  • Warshall算法(用法详解,并转换成代码的形式)

    关于Warshall算法,我先通过离散数学中求传递闭包来解释他的使用规则。 一般的,给定一个矩阵A(行列相等),我们对其使用Warshall算法: //注,该矩阵上只有0或1两种元素,做加法时,1+1还是1 1、先找到该矩阵的对角线,并从对角线的左上方开始为第一个元素 2、以对角线上

    2024年02月01日
    浏览(35)
  • Acwing.854 Floyd求最短路 (Floyd算法)

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输\\\"impossible”。 数据保证图中不存在负权回路。 第一行包含三个整数n, m, k 接下来m行,每行包含三

    2024年02月13日
    浏览(36)
  • 算法提高-图论-floyd算法及其扩展应用

    离散化 (只要用到200个点,但是题目给的点编号是1-1000)+ 倍增(快速幂)+ flyod变式(将递推公式改变了) 能用快速幂的原因是递推公式里面的两端路径两两之间相互独立,用结合律就可以用快速幂。矩阵乘法能用快速幂的原因也是矩阵乘法中两两矩阵之间具有结合律 帮助

    2024年02月09日
    浏览(51)
  • 图算法——求最短路径(Floyd算法)

    目录 一、什么是最短路径 二、弗洛伊德(Floyd)算法 三、测试程序         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多

    2024年02月07日
    浏览(38)
  • 【图论】Floyd算法

     Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两个节点之间的最短路径长

    2024年02月11日
    浏览(48)
  • Floyd算法求解最短路径

      Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。   核心思路:通过一个图的权值矩阵求出它的每

    2024年02月05日
    浏览(33)
  • Floyd算法的MATLAB代码

            现有一张城市地图如图4-10所示,图4-10中的顶点为城市,边代表两个城市间的连通关系,边上的权即为距离。每一对可达的城市间设计一条公共汽车线路,要求线路的长变在所有可能的方案里是最短的。  图1 公交车线路 由图1可知,很显然,这个问题可以抽象成为

    2024年02月01日
    浏览(38)
  • 40.弗洛伊德(Floyd)算法

    我们此前拆解过迪杰斯特拉(Dijkstra)算法,与它一样,弗洛伊德(Floyd)算法也是用于寻找给定的加权图中顶点间最短路径的算法。该算法是1978年图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德 及其团队发现的,以主要创始人 弗洛伊德 命名。 迪杰斯特拉算

    2024年02月06日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包