Coco_young
- 浏览: 125467 次
- 性别:
- 来自: 湖南长沙
-
最新评论
-
5474510：
哪有源码，哪有 文本？
通信——基于Xmpp协议实现的聊天室 -
Flywarrior：
很喜欢楼主的编程风格，学习了。
POJ_2337_欧拉回路+贪心 -
igdnss：
static List<Home> symbol= ...
我的多线程小游戏——坦克大战 -
yinger_fei：
赞一个！！
我的多线程小游戏——坦克大战 -
Coco_young：
25262875 写道您好楼主，我下来试了试，服务器启动不了。 ...
通信——实现多人聊天室
文章列表
这一章主要介绍了一些图的基本概念:
1.顶点，边：图中的点就是顶点，连接顶点的线就是边。
2.孤立点：没有任何边与之相连的顶点。
3.图同构：给定两个图G1，G2，对于G1中的边（U1，V1）在G2中总能找到（U2，V2）与之相对应，且所有的边是一一对应的，那么这两个图是同构的
4.自环：边（V，V）叫做自环
5.简单图：不含自环的图叫做简单图
6.二分图：把图中的顶点分成两个集合Set1，Set2，任意一条边（U,V）有U在Set1中，V在set2中，那么该图叫做二分图。
7.完全图：对于任意两个顶点都有直接边相连的图，叫做完全图。
8.补图：把 ...
- 2012-03-17 18:42
- 浏览 762
- 评论(0)
Frogs' Neighborhood
Time Limit : 10000/5000ms (Java/Other)Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 5Accepted Submission(s) : 1
Special Judge
Problem Description
未名湖附近共有N个大小湖泊L1, L2, ...,
Ln(其中包括未名湖)，每个湖泊Li里住着一只 ...
- 2012-03-14 13:22
- 浏览 762
- 评论(0)
题意：给定一个有向图，求最少要从几个结点开始能把图遍历完，最少添加多少条边，使得整个图强连通。
先缩点，然后对于缩点以后的图，入度为0的点的个数就是第一问的解，第二问的解是入度为0结点个数和出度为0结点个数中的最大值，第二问参考的解题报告是：http://hi.baidu.com/oichampion/blog/item/1882abd7d86adec5a9ec9aa5.html
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#i ...
- 2012-03-13 15:03
- 浏览 471
- 评论(0)
题目大意：给定一个网络，看是否有关节点存在（即割点，即去除该点后，图变成非连通图），如果存在输出该节点和去除该节点后连通子图的个数，如果不存在割点即输出没有割点存在。
求割点直接用dfs解决即可，问题在于统计去除该割点后，连通子图的个数，其实在dfs时，遇到割点时，只要发现其儿子结点的low值比该割点的dfn值大或相等，那么去除该结点后，其儿子结点能到达的所有结点 必定构成一个连通子图，这样用一个son数组记录所有这样的儿子结点的个数，最后加上割点的父亲结点能到达的所有结点形成的连通子图，即为去除该结点后整个图的连通子图的个数。
代码如下：
#include<iostrea ...
- 2012-03-12 23:07
- 浏览 591
- 评论(0)
//无向图求割点和桥
void dfs(int cur,int fa,int deep,int &time)
{
visit[cur] = 1;
DFN[cur] = LOW[cur] = deep;
int soncnt = 0;
for(int i=0;i<g[cur].size();i++)
{
int v = g[cur][i];
if(!vis[v])
{
soncnt++;
dfs(v,cur,deep+1,time);
LOW[cur] = MIN(LOW[cur],LOW[v]);
if(c ...
- 2012-03-12 09:19
- 浏览 1061
- 评论(0)
先明白一些概念。
割点：若一个点删除后（也就是与之相连的边统统去掉），无向图不再连通，那么此点称为割点。
桥：若一条边断去后，无向图不再连通，那么此边称为桥。桥有一个很好的性质，就是DFS一个无向图，那么 ...
- 2012-03-12 08:48
- 浏览 1419
- 评论(0)
题目链接：http://poj.org/problem?id=2337
欧拉回路相关定理：
1 无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。
2 无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。
3 有向图为欧拉图，当且仅当的基图连通，且所有顶点的入度等于出度。（忽略有向图所有边 的方向，得到的无向图称为该有向图的基图。）
4 有向图为半欧拉图，当且仅当的基图连通，且存在顶点的入度比出度大1、的入度比出度小1，其它所有顶点的入度等于出度。
以上定理用于判断图是否为欧拉图。
求出一条欧拉回路（路径）的算法：
时间复杂度O(E)
...
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1001;
vector<int> g[MAXN];//adjlist
stack<int> S,P;
int belong[MAXN],vis[MAXN],indeg[MAXN],sccg[MAXN][MAXN],scccnt,disc[MAXN];
void in ...
- 2012-03-02 12:56
- 浏览 626
- 评论(0)
链接：http://poj.org/problem?id=2513
1.把木棒的端点考虑为顶点，木棒考虑为边，建立起一个无向图。
2.问题转化为在无向图上判断是否有欧拉回路或者欧拉道路。
3.在无向图上判断是否有欧拉回路或者欧拉道路：欧拉定理+并查集（判断连通性）
4.考虑如何统计每个顶点的度，开始用的是暴力解法，直接用数组记录顶点，并且通过顺序查找获得顶点编号，TLE，然后考虑用map（红黑树），每次以logn的时间复杂度完成顶点度的 更新，继续TLE，想到用HASH，不过没想到好的映射方式，最后搜解题报告，发现trie树这种玩意。
6.Trie树能以O(sizeof(key))的 ...
还是POJ_2762,前段时间用Kosaraju算法解决掉了，不过解决强连通分量的线性时间复杂度的算法还有两个，Tarjan，Gabow，今天把Tarjan看了下，感觉基本思想还是不难的，实现起来也算容易，不过我还不能证明其正确性。
Tarjan算法的基本思路就是，利用DFS去求强连通分量，具体步骤如下：
1.任意选取一个顶点做为DFS的起始位置，进行DFS。
2.在每次DFS中，先把discoverTime[now_node]，和lowlink[now_node]赋值为当前搜索时间，并把当前结点压入栈内，然后查看当前结点的所有后继结点，如果其后继结点尚未访问，则继续DFS下去，并且 ...
刚刚在算导上学会用两次dfs求SCC,终于过了前段时间群赛的一个题。
http://poj.org/problem?id=2762
题意：给定一个有向图，让你求它是否为半连通图（即对于图中任意两个顶点u,v 是否有u可以到达v或者v可以到达u）
解题思路：当时还不 ...
刚刚在算导上学会用两次dfs求SCC,终于过了前段时间群赛的一个题。
http://poj.org/problem?id=2762
题意：给定一个有向图，让你求它是否为半连通图（即对于图中任意两个顶点u,v 是否有u可以到达v或者v可以到达u）
解题思路：当时还不知道啥强连通分量，看了人家的一篇博客，了解了下解题思路，就是先求强连通分量+缩点，得到缩点以后的DAG（有向无环图），然后对缩点以后的图进行拓扑排序，如果有分叉则说明，原图不是半连通的（即从分叉处往下的两个分支，不能保证对于其中任意两个节点之间可达）。
关于该算法的正确性，算导上面证明的很清楚。
求SCC的步骤为：
1. ...
- 2012-02-17 17:00
- 浏览 886
- 评论(0)
http://poj.org/problem?id=1062
哎，弱菜伤感呐，N久前做最短路的题，看了这个题，被等级差搞的没思路，昨天突发奇想，脑残的认为1号节点是等级最高的节点，然后把等级差和1号节点超过m的结点忽略，用Dij求一遍最短路，即是解。 写完，提交，wa了，然后看了discuss，发现这个自己的程序建立在一个错误的前提上(1号节点是等级最高的节点)，其实可能其他的结点等级更高，所以把程序改成，对于每个包含1号结点等级的长度为m的区间用一次Dij，然后算出最小值。
#include<iostream>
#include<cmath>
using ...
- 2012-01-31 13:22
- 浏览 726
- 评论(0)
一. AVL概念：
对于一颗BST，其中每个节点的左右子树高度差均不超过1的平衡二叉搜索树，就叫做AVL树。
二. 如何维护一颗AVL树。
旋转操作：
1. rotateWithLeft:(右旋转)
* (N) (L)
* / \ / \
* (L) 3 ==> 1 (N)
* / \ / \
* 1 2 2 3
2. rotateWit ...
链接: http://poj.org/problem?id=2299
分析:统计给定序列中的逆序数，蛮力法复杂度达O(n^2)会超时，由于归并排序复杂度为O(nlogn)
并且，在排序过程中可以顺便统计逆序数，所以用归并排序可以求出。
注意：在求逆序数时要注意，每当前半部分的数被加入到辅助数组中时，逆序数总数应当增加后半部分已经被添加到辅助数组中的元素的总个数.
#include<stdio.h>
#include<stdlib.h>
//归并排序统计
#define SIZE 500010
int arr[SIZE],T[SIZE];
l ...