UVA 247 - Calling Circles(floyd 传递背包)

2023-12-05 02:09

本文主要是介绍UVA 247 - Calling Circles(floyd 传递背包),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这个题还是比较简单的。  就是被输出坑了一下啊。  ‘,’ 的后面有个空格。 我没注意到。。  WA了一次。


剩下的就比较简单了。  直接套上 传递背包模板。 


然后 dfs  深搜输出就好。  还有一开始 给每一个名字 标记数字的时候 用的是 vector 《》 的 size 就好。 用的 set 来判重。 用map来 把名字 和 id对应输出的时候用。


没什么可以注意的地方了。


#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 100+10
#define INF 1<<30
int vis[maxn] = {0};
int d[maxn][maxn] = {0};
set <string> l;// 集合保存 所有的名字。
vector <string> q;  //  用来获取 id
map <string , int> id;   // 名字  获取id
map <int , string> name; //  id 获取名字
int n,num;
int dfs(int i,int o){vis[i] = 1;if(o)printf(", ");cout << name[i];for(int j = 1; j <= n; j++){if(d[i][j] == 1 && d[j][i] == 1 && !vis[j]){dfs(j,o+1);}}
}
int main (){int counts = 0;while(scanf("%d%d",&n,&num)){if(n == 0 && num == 0)break;if(counts)printf("\n");memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));l.clear();q.clear();id.clear();name.clear();for(int i = 0; i <= n; i++){for(int j = 0; j <= n; j++){d[i][j] = INF;}}for(int i = 0; i < num; i++){string a,b;cin >> a >> b;if(!l.count(a)){l.insert(a);q.push_back(a);id[a] = q.size();name[id[a]] = a;}if(!l.count(b)){l.insert(b);q.push_back(b);id[b] = q.size();name[id[b]] = b;}d[id[a]][id[b]] = 1;}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(d[i][k] < INF && d[k][j] < INF)d[i][j] = d[i][j] ||(d[i][k] && d[k][j]);}}}printf("Calling circles for data set %d:\n",++counts);for(int i = 1; i <= n; i++){if(!vis[i]){dfs(i,0);printf("\n");}}}return 0;
}


这篇关于UVA 247 - Calling Circles(floyd 传递背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/455729

相关文章

异步线程traceId如何实现传递

《异步线程traceId如何实现传递》文章介绍了如何在异步请求中传递traceId,通过重写ThreadPoolTaskExecutor的方法和实现TaskDecorator接口来增强线程池,确保异步... 目录前言重写ThreadPoolTaskExecutor中方法线程池增强总结前言在日常问题排查中,

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》:本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

如何在页面调用utility bar并传递参数至lwc组件

1.在app的utility item中添加lwc组件: 2.调用utility bar api的方式有两种: 方法一,通过lwc调用: import {LightningElement,api ,wire } from 'lwc';import { publish, MessageContext } from 'lightning/messageService';import Ca

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &