校赛 SDUT OJ2860生日Party(BFS)

2024-08-24 22:18
文章标签 bfs party 生日 校赛 sdut oj2860

本文主要是介绍校赛 SDUT OJ2860生日Party(BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目地址:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2860

唉。。校赛的时候把这题用搜索的时间复杂度2^15次方想成了15^15次方。。。。所以没写。。。后来用的最短路的floyd算法改成了最长路做的,但有一些细节不好处理,调了会没调出来。。赛后才想到用暴搜不会超时。。于是补完线代后怒敲暴搜代码,敲了10分钟然后1Y。。。sad。。。。遗憾。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
int mp[20][20], b[20], max1, n;
struct node
{int a[15], top, ans, x;
};
void bfs()
{int i, j, x;queue<node>q;node f1, f2;f1.top=0;f1.x=-1;f1.ans=0;q.push(f1);while(!q.empty()){f1=q.front();q.pop();//printf("%d\n",f1.ans);if(f1.x==n-1){if(max1<f1.ans)max1=f1.ans;continue ;}for(i=0;i<f1.top;i++){f2.a[i]=f1.a[i];}f2.ans=f1.ans;f2.top=f1.top;f2.x=f1.x+1;q.push(f2);f2.top=f1.top+1;f2.a[f1.top]=f2.x;f2.ans=f1.ans+b[f2.x];for(i=0;i<f1.top;i++){f2.ans=f2.ans+mp[f2.a[i]][f2.x];}q.push(f2);}
}
int main()
{int t, i, j;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&b[i]);}for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&mp[i][j]);}}max1=-1;bfs();if(max1<0)printf("0\n");elseprintf("%d\n",max1);}return 0;
}


这篇关于校赛 SDUT OJ2860生日Party(BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

【生日视频制作】酒吧一群美女车展模特大屏幕视频改字AE模板修改文字软件生成器教程特效素材【AE模板】

生日视频制作教程酒吧一群美女车展模特大屏幕视频改字AE模板修改文字特效广软件告生成神器素材祝福玩法AE模板工程 怎么如何做的【生日视频制作】酒吧一群美女车展模特大屏幕视频改字AE模板修改文字软件生成器教程特效素材【AE模板】 生日视频制作步骤: 安装AE软件 下载AE模板 把AE模板导入AE软件 修改图片或文字 渲染出视频

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<

【生日视频制作】劳斯莱斯库里南中控改名软件AE模板修改文字软件生成器教程特效素材【AE模板】

生日视频制作教程豪车劳斯莱斯库里南中控改名软件AE模板修改文字特效广告生成神器素材祝福玩法AE模板工程 怎么如何做的【生日视频制作】劳斯莱斯库里南中控改名软件AE模板修改文字软件生成器教程特效素材【AE模板】 生日视频制作步骤: 下载AE模板 安装AE软件 把AE模板导入AE软件 修改图片或文字 渲染出视频

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接: http://acm.hdu.edu.cn/showproblem.