對酒當歌,人生幾何? 譬如朝露,去日苦多

LCA倍增

优质博客推荐hdu6115#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<map> #include<vector> using namespace std; const int inf=0x3f3f3f3f; #define mem(a,b) memset(a,b,sizeof(a)) const int maxn=100005; int n,m; int vis[maxn]; int deep[maxn]; int dis[maxn]; int p[maxn][25]; vector<int>v1[maxn]; int tot; struct node { int u,v,w,nex; } e[maxn*10]; int first[maxn]; void edge(int u,int v,int w) { ...

读文章代码

#include <bits/stdc++.h> using namespace std; int main() { ofstream file; file.open("yuyin.txt"); string s; char bd='"'; while(cin>>s) { if(s[0]==s[1]&&s[1]=='0') break; int len=s.size(); for(int i=0;i<len;i++) { if(s[i]=='"') s[i]='.'; } char bd='"'; file<<"CreateObject("; file<<bd; file<<"SAPI.SpVoice"; ...

LCA(求两点最近公共祖先,也可以求两点间是否连通且最短距离)

LCA就是求公共祖先。优质博客推荐 但是不推荐它的伪代码,感觉思路没错,但是有点问题。 我随手写了一个,有错欢迎之处int get(int u) { if(f[u]==u) return u; else f[u]=get(f[u]); } void dfs(int u,int pre) { //vis[u]=1;//位置1 for(int i=first[u];i!=-1;i=e[i].nex) { int v=e[i].v; if(pre==v) continue; if(!vis[v]) { dfs(v,u); f[v]=u; } } vis[u]=1;//位置2 for(int i=first2[u];i!=-1;i=e2[i].nex) { int v=e2[i].v; int id=e2[i].id...

tarjan之双连通图(无向图)

这里有几个点需要注意 1.为什么无向图缩点需要变成有向图缩点? 无向图两两之间的点可以到达,无法跑回边的话,就跑不到父节点以上的节点了,那么肯定是桥了。 2.为什么不能跑回边,而不是跑父节点? 本来是个无向图单连通,但是你阻止了父节点跑回去,那就不是无向图单连通了。 但是这个题去重也对,嗯。。。数据弱#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long using namespace std; const int maxn=10005; struct node { int u,v,nex; } e[maxn*maxn]; int first[maxn]; int tot; int n,m; int ans,din,top; in...

tarjan算法之桥

博客推荐与割点的最大不同之处:low[v]>low[u]易错点:1.父亲节点与子节点区别一下,防止两个点误认为环。2.去重边#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long using namespace std; const int maxn=10005; int n,m; struct node2 { int x,y; } ee[maxn*maxn]; int cmp(node2 a,node2 b) { if(a.x==b.x) return a.y<b.y; else return a.x<b.x; } struct node { in...