huyifan951124
- 浏览: 82959 次
-
最新评论
-
coralsea：
试试log4jdbc
SpringMVC+MyBatis+Log4j输出sql语句 -
hellotieye：
题目是什么意思？？？
NYOJ118 求次小生成树
文章列表
Poj1144 tarjan算法求割点
- 博客分类：
- 算法
题目大意：给你一个节点从1到n的连通图，问你这个图的割点有多少个。
算法思路：求割点的简单题，求割点也用tarjan算法，但要注意，根如果为割点的话，那么根的度必须大于等于2，其他点判定割点的话当且仅当自己的子节点没有越过自己的回边，也就是low[v]>=dfn[u].
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int a[105][105],dfn[105],lo ...
POj2762 tarjan算法求强连通分量
- 博客分类：
- 算法
题目大意：有n个房间，这些房间都有给定的路，现在要求任意两个房间能否相同(假设a与b相连通，那么只要满足a与b能够连通或者b与a能够连通即可)。，如果任意的两点能够连通输出Yes，否则输出No.
算法思路：明显的求强连通分量，再缩点，再对缩点后的图判断连通性(这里采用拓扑排序判断连通性，如果有2个及以上的点入度为0的点出现的话，说明缩点后的图是不连通的)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue&g ...
题目大意：k^0+k^1+k^2+...+K^r=n，给你n让你求k和r，若有多组k和r取乘积最小的，若最小的乘积相同，取r值最小的(这里注意,蛋糕的中心可以不放蜡烛，因此k^0可以省略，所以判断的时候不要忘记)。
算法思路：有等比数列公式可得，当k取最小的2时，r最大不超过40，因为超过40，n就要超过12位了。那么只需要遍历r，然后对k在[2,pow(n,1/r)]区间内进行二分，求出答案即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> ...
Poj1286 tarjan算法求强连通图
- 博客分类：
- 算法
题目大意：问给你n头牛和m个牛与牛之间的关系，问你有多少头年能够被所有的牛所知道，当然两头牛通过第三方的牛有连接也算认识。(注意A认识B但B不一定认识A，所以是个有向图).
算法思路：就是求强连通图，因为A与B如果要认识，则A肯定有变直接或间接到B，同理B也必须满足这样的条件，因此这道题我们可以用tarjan算法求出图中有几个强连通分量。稍微想一想我们就可以发现，如果强连通分量X与强连通分量Y有如下关系：X->Y说明Y中的点都被X中的点认识，因此我们可以根据缩点后的图中出度为0的分量来求得答案，但要注意如果缩点后的图中有2个出度为0的点，则答案为0，因为没有牛能被所有牛认识。
...
题目大意：有N个学校，学校与学校之间要能够两两通信，现在有2个解决方案：1.要是这些学校都能用上该软件，要准备多少份软件。
2.要是只有一份软件，那么要新建多少条边。
算法思路：就是一个求强连通图问题，第一个问题可以转化为，再强连通分量之间，有多少个入度为0的强连通分量。第二个问题可以转化为，要构成一个强连通图，需要添加多少条边连接这些强连通分量（相当于求这些强连通分量的入度为0点的个数和出度为0的点之间的个数之间的最大值）。
这里我用了tarjan算法，因为折算阀无论在时间复杂度方面还是编码量方面都很有优势。
#include<iostream>
#include& ...
题目大意：给出连通的房间，让你求能否从0走到M并且关闭了所有的房间，注意关闭的房间不能再次打开。题目已经告诉你图已经连通。
算法思路：就是让你求这个图是否是一个欧拉回路或者是欧拉图，当m==0的时候求是否是欧拉回路，当m!=0的时候求是否是欧拉图。
无向图欧拉回路的判定：图连通并且所有点的度是偶数。
无向图欧拉通路的判定：图连通并且度为奇数的点位0个或2个，且这两个奇点必为起点或终点。
有向图欧拉回路的判定：图连通且任意一点的入度等于出度。
有向图欧拉通路的判定：图连通且恰好只有2个点，其中一个出度比入度多一（起点），另一个入度比出度多一（终点）。
#include<io ...
题目大意：问该图中是否存在一条欧拉回路，若存在则输出其路径。
算法思路：存在欧拉回路很好判断，记录下每个点的度，因为是无向图，因此只需要每个点的度都是偶数即可。主要就是输出路径的问题，用普通的递归方法会超时，这里借鉴了网上的思路，详见代码。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int maps[45][2000];
int h,a1,b1;
int a,b,num,e,len,sa, ...
题目大意：给你一个手机字典，让你根据用户的输入键号对应找到输入次数最多的那一个单词并输出。
算法思想：字典树的应用，仙剑好字典树，再便利用户的输入，运用递归找到最优数组，并输出，
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,m,w,k,MAX;
char c[12][5]={{"\0"},{"\0"},{"abc"},{"def"},{"g ...
题目大意：给你一个字母表格，问你在这些字母表格中是否存在下面所给的字符串，如果存在的话给出字符串首字母的起始坐标，已经搜寻方向。
算法思路：一开始直接暴力深搜，从每个满足条件的首字母开始，递归8个方向，结果超时，于是去学习了字典树。如果不明白什么是字典树，可自行了解，网上的很多博客都有详细的介绍和实现代码。后来对于这道题，我发现字典树快就快在如果一个字符串是另一个字符串的前缀，直接深搜要找两遍，而字典树直接一边就得出了结果，我想优化就优化在这里吧。。。（理解不正确的话还请指正）。
#include<iostream>
#include<cstdio>
#incl ...
题目大意：将字母按照所给的序列从小到大输出。
算法思路：首先判断该图是否存在环，如果不存在，看能否进行有序输出，如果有序则后面的处理步骤都可以跳过，否则输出题目所给的话。
#include<iostream>
#include<string>
using namespace std;
int n,m,indegree[30],map[30][30];
char ans[30];
int topusort()
{
int temp[30],sym=0,i,j,m,flag,res=1;
for(i=0;i<n;i++)
{
temp ...
题目大意:让你求出从原点到其他各个点来回的最短路径之和。
算法思想：首先正向建图，求出原点到各个点之间最短路径之和，在反向建图，再求一遍原点到各个点之间最短路之和（可以看做是各个点到远点的最短路，因为这时候原点到各个点的距离==各个点到原点的距离，这道题昨天不知道什么原因，wa了不下10次，今天上午一样的算法，一样的写法，重新写一遍 。。1A也是醉了）.。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; ...
题目大意：让你求从S点到A点的所能达到的最小距离。
算法思路：先通过bfs求出各个字母之间的最短距离，再求最小生成树。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
typedef struct Node
{
int x,y;
int lev;
int sym;
};
Node nodes[3000];
cha ...
题目大意：也是求最短路的题，有多个起始点，每个点按时间从小到大，输出路径等。
算法思路：dijikstra算法的应用。但是注意一下路径的输出，这里可以用记录每个点前驱的方法，来做，最后只要通过while循环(递归也可以)从结束点不断的寻找前驱即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
i ...
题目大意：给顶每条边的汇率和所花费的手续费，让你求是否会比原来的钱多。
算法思想：spfa的变形，只需要判断是否存在正环即可，但要注意精度问题，又在这精度上wa了好几次，还是太粗心了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,s,sym;
double v;
int a,b,e;
double ex,ch,ex2,ch2;
bool visited[300];
int h ...
题目大意：将一块木板切成n块，问你最小所需要的费用是多少。
算法思路：哈夫曼编码实现，这里特别要注意（不是算切完后木板的长度计算费用，而是在切之前计算费用）
，千万不要理解错题意，我就是因为理解错题意而想错了算法。
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int t,v;
long long sum,res;
typedef struct Node
{
int v;
...