显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 

标签

 
 
数据加载中...
 
 
 
 
 

天气

 
 
模块内容加载中...
 
 
 
 
 
 
 

浙江省 绍兴市 天蝎座

 发消息  写留言

 
低调
 
近期心愿省选进去
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 

发现好博客

 
 
列表加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 
 
 

双联通分量

2015-3-15 19:46:49 阅读5513 评论1 152015/03 Mar15

转自 http://www.haogongju.net/art/1330869

1:一些概念

割点:是无向连通图中一个顶点v, 如果删除它以及它关联的边后,得到的新图至少包含两个连通分支。

桥:无向连通图中的一条边,如果删除它,得到的新图包含两个连通分量。

双连通图:不含割点的无向连通图。

双连通分支:无向连通图的最大双连通子图。

点双连通分支:(自己猜的)通过找割点获得的双连通分支。

边双连通分支:(自猜)通过找桥获得的双连通分支。

举个例子:一个无向图有 1、2、3、4、5共5个顶点,一共有如下6条边,1 2,2 3,1 3,3 4,3 5,4 5,由于去掉任意一条边原图都是连通的,所以原图整体是边双连通的,但3是一个割点,如果去掉3原图就不连通了,所以原图整体不是点双连通的。还有是在有重边的情况下,边连通和点连通有点区别。

作者  | 2015-3-15 19:46:49 | 阅读(5513) |评论(1) | 阅读全文>>

插头DP

2015-3-11 15:19:05 阅读120 评论3 112015/03 Mar11

1519. Formula 1

Time limit: 1.0 second

Problem illustration

作者  | 2015-3-11 15:19:05 | 阅读(120) |评论(3) | 阅读全文>>

O(n)求阶乘逆元(转)

2014-12-26 20:48:34 阅读171 评论6 262014/12 Dec26

一个Catalan数的题,打表对每个数都求一次逆元会T,于是问到了一种求阶乘逆元的打表新方法。 比如打一个1~n的阶乘的逆元的表,假如叫inv[n],可以先用费马小定理什么的求出inv[n],再用递推公式求出前面的项。

  我们记数字 x 的逆元为f(x) (%MOD)。

  因为 n! = (n-1)! * n

  所以 f(n!) = f( (n-1)! * n) = f( (n-1)! ) * f(n)。

  所以 f( (n-1)! ) = f(n!) * f( f(n) ) = f(n!) * n   (逆元的逆元就是他自身)

这样子我们就可以用后项推出前面的项了。

 

题目是说,有一个人从0点开始走路,每次可以向前走或者向后走,每次可以走一步,但是所有的位置必须大于等于0,问走过2n步之后又回到0点有多少种方法。

作者  | 2014-12-26 20:48:34 | 阅读(171) |评论(6) | 阅读全文>>

DINIC

2014-12-11 13:11:32 阅读128 评论0 112014/12 Dec11

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 2100000000
#define mm 250000
#define nn 510
#define CH getchar()
using namespace std;
struct nod{int end,next,c;
}g[mm*2];
 
int tot,i,n,z,ans,Dis,m;
int dis[nn],fa[nn],x[mm],y[mm],t[mm],c[mm],f[nn][nn],q[nn*4];

作者  | 2014-12-11 13:11:32 | 阅读(128) |评论(0) | 阅读全文>>

DJ+堆和系统队列用法

2014-10-29 15:28:35 阅读184 评论3 292014/10 Oct29

#include<cstdio>
#include<queue>
#include<cstring>
#define nn 100010
#define pii pair<ll,int> 
#define mk make_pair
#define x first
#define y second
using namespace std;
/*struct node{
  int x,y;
  bool operator <(const node&b)const{

作者  | 2014-10-29 15:28:35 | 阅读(184) |评论(3) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 
 
 
 
 
 
 
网易云音乐 曲目表歌词秀
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注