HDU1181【有向图的传递闭包】

HDU1181【有向图的传递闭包】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1181

题意很简单。

有用并查集做的。我这里用传递闭包做。

有向图的传递闭包采用Floyd思想,可以判断任意两点之间是否有通路。

PS:Floyd思想:对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

这题代码:#include <iostream>

 

#include <cmath>
#include <cstring>
using namespace std;

int map[200][200];

void floyd()
{
    for(int i='a'; i<='z'; i++)
    {
     for(int j='a'; j<='z'; j++)
     {
      if(map[i][j])  //如果i->j 
      {
       for(int k='a'; k<='z'; k++) 
       {
        if(map[k][i]) //并且k->i 
        {
         map[k][j] = 1; //那么k->j 
        }
       }
      }
    }
  }
}

int main()
{
    char str[100];
    memset(map,0,sizeof(map));
    while(cin>>str)
    {
        if(strcmp(str,"0") == 0)
        {
             floyd();
            if(map['b']['m'] == 1)
            {
                cout<<"Yes."<<endl;
            }
            else
            {
                cout<<"No."<<endl;
            }
            memset(map,0,sizeof(map));
        }
        else
        {
            int len = strlen(str);
            map[str[0]][str[len-1]] = 1;
        }
    }
    return 0;
}

 

自己犯的错误:

for(char i=’a’;i<=’z’;i++)
            for(char j=’a’;j<=’z’;j++)
               for(char k=’a’;k<=’z’;k++)
                {

                    if(judge[adj[i]][adj[j]]==1&&judge[adj[j]][adj[k]]==1)
                        {

                            judge[adj[i]][adj[k]]=1;
                        }
                }

结合Floyd做法来实现。(尽管DP原理偶还不是很懂。)

传递闭包自己写的,来一个错误例子  bg  ga am….自己写这个显然可以找到反例。这个应该没问题。

另外数组下标是可以char类型的。

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110029.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • padstart兼容_显示列出polyfill

    padstart兼容_显示列出polyfill?原文链接:欢迎star.今天在看ES7新增的部分Api的时候刚好看到padStart的这个方法,好像还挺实用的,而且也想在正式开始工作之前先找找写代码的感觉,于是顺手(其实还是花了不少时间的)就实现了这个polyfill。相关的API用法在MDN上有说明。链接下面是具体实现if(!String.p…

  • Netty时间轮_java netty

    Netty时间轮_java netty时间轮是一个高性能,低消耗的数据结构,它适合用非准实时,延迟的短平快任务,例如心跳检测。在netty和kafka中都有使用。

  • zuul网关作用_zuul网关的作用

    zuul网关作用_zuul网关的作用Zuul网关使用步骤1.在父项目中导入依赖SpringCloud管理<dependencyManagement><dependencies><dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-dependencies&

  • 备战“软考”之软件project

    备战“软考”之软件project

  • lqr算法优点(lqg控制)

    由来自INTERNAT的资料整理:LQR(linearquadraticregulator)即线性二次型调节器,其对象是现代控制理论中以状态空间形式给出的线性系统,而目标函数为对象状态和控制输入的二次型函数。LQR最优设计指设计是出的状态反馈控制器K要使二次型目标函数J取最小值,而K由权矩阵Q与R唯一决定,故此Q、R的选择尤为重要。LQR理论是现代控制理论中发展最早也最为成熟的…

  • Python注释

    Python注释单行注释python中单行注释采用#开头[cclang='python']print‘hellopython’#thisisacomment[/cc]多行注释然后pyt

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号