加载中…
搜博主文章
访客
加载中…
好友
加载中…
评论
加载中…
博文
标签:

博客七周年

我的博客今天291天了,我领取了徽章.  

  • 2010.12.05,我在新浪博客安家。
  • 2010.12.05,我写下了第一篇博文:《POJ3083 Bfs + Dfs Children of the Candy Corn》。
  • 至今,我的博客共获得
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

hdu

4027

线段树

杂谈

分类: 比赛题目
 
 
注意几点就好了,区间左值可能大于右值,对于已经等于1的线段,做个标记,更新的时候就不往下更新了。
#include <stdio.h>
#in
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

3967

锯齿数组

bfs

杂谈

分类: POJ
 这个题目YY了一个早上,终于刷进前十。。。交了40+次。寂寞,将BFS优化成这样,足够了,呵呵 
 给一个完全图,删除若干边,问有多少个点与1点连通 
 代码加注释 
 #include 
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-30 09:00)
标签:

poj

2553

强连通

杂谈

分类: POJ
 
题意很简单给你N个点M条边,然后求强连通,缩点后,出度为0的点集,最后按升序输出
#include <stdio.h>
#include
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

1236

杂谈

分类: POJ

一些学校联接在一个计算机网络上,学校之间存在软件支援协议,每个学校都有它应支援的学校名单(A学校支援学校B,并不表示B学校一定支援学校A)。当某校获得一个新软件时,无论是直接获得还是通过网络获得,该校都应立即将这个软件通过网络传送给它应支援的学校。因此,一个新软件若想让所有联接在网络上的学校都能使用,只需将其提供给一些学校即可。

子任务A

    请编一个程序,根据学

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-27 10:36)
标签:

poj

3697

bfs

暴力

3500ms

杂谈

分类: POJ
题意给你一个完全图 , 删除若干边,最后问你有多少个点与1号点直接相连或间接相连。
这个方法不构图,利用二分,广搜枚举边的时候,检查该边是否在失败边里面,不在的话就可以继续搜
#include <stdio.h>
#include <algorithm>
#include <queue>
#define MAXSIZE 1001000
using namespace std;

int n,m;

struct node
{
int u,v;
}nodes[MAXSIZE];

bool cmp(const node a,const node b)
{
if(a.u == b.u)
return a.v < b.v;
return a.u < b.u;
}

bool binsearch(int u,int v)
{
int left = 0,mid,right = m - 1;
if(u > v)
{
int t;
t = u;u = v;v = t;
}
mid = (left + right) / 2;
while(left <= right)
{
if(n
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-26 10:07)
标签:

poj

1679

次小生成树

杂谈

分类: POJ
题意很简单,给你一些边,问你求出的最小生成树是否唯一,如果唯一直接输出最小生成树的值,不唯一则输出一串字符。想法简单,求次小生成树,如果次小生成树和最小生成树相等,则最小生成树不唯一。求次小生成树的算法比较暴力,先做出一次最小生成树,标记出构成最小生成树边,然后枚举这些边,每次删一条,然后做一次生成树,将其值保存起来,做完之后,把删除的边补回去。进行下一次删边,枚举过程中保存最小值,如果最小值跟原来的最小生成树的值相等的话,则说明,该最小生成不唯一,反之唯一。
#include <stdio.h>
#define MAXSIZE 200
#define inf 1000000

struct node
{
int front,end,length;
}minedge[MAXSIZE];

int map[MAXSIZE][MAXSIZE];
int n,m;

void ini()
{
for(int i = 0;i < n;++i)
{
for(int j = 0;j < n;++j)
{
map[i][j] = inf;
}
}
}
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-26 10:03)
标签:

poj

2349

最小生成树

杂谈

分类: POJ
有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。告诉你卫星电台的个数S,让你求最小的D.生成最小生成树,去掉最长的S条边后,剩下最长的边就是D.也就是求最小生成树中第S+1长的边。

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define MAXSIZE 600
#define inf 1000000
using namespace std;

double map[MAXSIZE][MAXSIZE],ans[MAXSIZE];
int n,s;

struct node
{
    int front , end;
    double length;
};

struct point
{
    int x,y;
}p[MAXSIZE];

bool cmp(const double a,const double b)
{
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-24 22:58)
标签:

hdu

3123

杂谈

这里面有个很重要的特点,n >= m  n! % m = 0;所以如果n>=m的话,在根据同余模定理,我们只需要算出1到m - 1的阶乘和就可以了,O(n)的复杂度,完全可以接受 
#include <stdio.h>
#include <string.h>

int change(char* s)//字符数组转换数字
{
int ans = 0;
for(int i = 0;s[i];++i)
{
ans *= 10;
ans += s[i] - '0';  
}
return ans;
}
int main()
{
int total,b,x,y;
__int64 num,sum;
char a[1000];
scanf('%d',&total);
while(total--)
{
int m = 0,n = 0;
scanf('%s%d',a,&b);
if(strlen(a) >= 7)
{
n = 1000000;
}
else
{
n = change(a);
}
if(n >= b)
{
n = b - 1;
}
sum = 1; nu
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2011-08-24 11:12)
标签:

hdu

3118

杂谈

分类: 其他OJ
题目的意思是最少去掉多少条边使原来的图不存在奇数环,也就是所有的点都不能通过奇数条边回到自己。恰好图论的知识,二分图刚好具有这个性质,然后我们就可以通过枚举两个点集,同个统计删除相同点集之内的边,来得到删除结果,通过枚举,选取最小的结果
#include <stdio.h>

int main()
{
int total = 0;
scanf('%d',&total);
while(total--)
{
int n = 0,m = 0,all = 1,min = 2000;
int map[17][17] = {0};
scanf('%d%d',&n,&m);
for(int i = 0;i < m;++i)//读入图
{
int x,y;
scanf('%d%d',&x,&y);
map[x][y] += 1;
}
all  = all << n;
//printf('all: %d\n',all);
for(int i = 0;i < all;++i)//利用二进制枚举,因为最多才只有15个点,可以考虑这个
{
int sign[17] = {0};
for(int j = 0;j < n;++j)
{
if((i >
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有