防2B 图论模板 7788
1.二分图判定染色模板
bool dfs(int u, int cur){col[u]=cur;for(int i=0; i
2.floyd模板
void floyd(){ //求可达性int k, i, j;for(k=1; k<=n; k++)for(i=1; i<=n; i++)for(j=1; j<=n; j++) if(!reach[i][j])reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
}
3.tarjan 求 割边 / 桥
void dfs(int u){dfn[u]=low[u]=++tsp;vis[u]=ins[u]=true; s.push(u);for(int i=h[u]; i!=-1; i=e[i].nxt){int v=e[i].v;if(!vis[v]){ve[e[i].re]=true;dfs(v), low[u]=MIN(low[v], low[u]);if(dfn[v]==low[v]) ans=MIN(ans, e[i].w); //割点，割边}else if(ins[v] && !ve[i]){ve[e[i].re]=true;low[u]=MIN(dfn[v], low[u]);}}if(dfn[u]==low[u]){ //割点int v;do{v=s.top(); s.pop();ins[v]=false;}while(v!=u);}
}void tarjan(){int i, j;memset(vis, 0, sizeof(vis));memset(ve, 0, sizeof(ve));memset(ins, 0, sizeof(ins));int f=tsp=0;for(i=1; i<=n; i++) if(!vis[i])dfs(i), f++;if(f>1) ans=0;if(ans==INF) ans=-1;
}
4.tarjan 求强连通分量
void tarjan(int u){dfn[u]=low[u]=++tsp;s.push(u); ins[u]=true;int i, v, tl=g[u].size();for(i=0; i
5.tarjan 求点双连通分量
void tarjan(int u, int fa){int v, child=0;dfn[u]=low[u]=++tsp;for(unsigned int i=0; i=dfn[u]){iscut[u]=1;edge k;bcc[++cnt].clear();while(1){k=s.top(); s.pop();if(id[k.u] != cnt) {id[k.u]=cnt; bcc[cnt].push_back(k.u);}if(id[k.v] != cnt) {id[k.v]=cnt; bcc[cnt].push_back(k.v);}if(k.u==u && k.v==v) break;}}}else if(dfn[v]
6.tarjan 边双连通分量
void tarjan(int u){int i,v;dfn[u]=low[u]=++tsp;s[top++]=u;for(i=h[u]; i!=-1; i=e[i].nxt){v=e[i].v;if(!dfn[v]){vis[e[i].re]=1;tarjan(v);low[u]=MIN(low[u], low[v]);}else if(!vis[i]) low[u]=MIN(low[u], dfn[v]); //回边不是反向边，且该点：dfn[v] == low[v]}if(low[u] == dfn[u]){cnt++;do{v=s[--top];id[v]=cnt; //缩点}while(v!=u);}
}
7.稳定婚姻问题 / propose-and-reject algorithm
void engage(int man, int woman){int m=fb[woman];if(m) q.push(m), fw[m]=0; //如果有未婚夫,抛弃fw[man]=woman;fb[woman]=man;
}void solve(){memset(fw, 0, sizeof(fw));memset(fb, 0, sizeof(fb));while(!q.empty()){int man=q.front(); q.pop();int woman=pref[man][nxt[man]++];if(!fb[woman]) engage(man, woman); //没有未婚夫else if(order[woman][fb[woman]]>order[woman][man]) engage(man, woman); //出现更迷人的汉子else q.push(man);}for(int i=1; i<=n; i++) cout<（详细见这里：http://www.cnblogs.com/ramanujan/p/3320659.html）
8.2-sat
inline void add(int u, int a, int v, int b){ //加边u = (u<<1) + a;v = (v<<1) + b;g[u].push_back(v^1);g[v].push_back(u^1);
}bool dfs(int u){if(mark[u]) return true; //如果已标记过if(mark[u^1]) return false; //如果否命题假设为真，则矛盾mark[u]=true; s[c++]=u;int i, tl=g[u].size();for(i=0; i
9.扩栈指令(用C++交才有效？)：
#pragma comment(linker,"/STACK:102400000,102400000")
10.Bellman-Ford Algorithm 队列实现
queue q;
int bford(int s, int n){int u,i,w,v;while(!q.empty()) q.pop(); q.push(s);// memset(cnt, 0, sizeof(cnt)); cnt[s]=1;memset(inq, 0, sizeof(inq)); inq[s]=1;for(i=0; id[u]+w){d[v]=d[u]+w;if(!inq[v]){// if(++cnt[v]>n) return 1;q.push(v);inq[v]=1;}}}}ans=d[s-1]-d[0]; // 结果不是d[s-1]么？。。。return 0;
}
11.朱刘算法（抄来：http://www.cnblogs.com/nanke/archive/2012/04/11/2441725.html#commentform）
int mdst(int s, int n, int m){int u,v,i,d;int ret=0;while(true){ //找出每个点的最小入弧for(i=0; i
12.欧拉回路
//判断欧拉回路：
//1.图是否连通 2.是否存在奇点 3.打印欧拉回路
void dfs(int s){for(int i=1; i<=50; i++) if(g[s][i]){g[s][i]--; g[i][s]--;dfs(i);ans.push_back((edge){s,i});}
}
13.次小生成树（mst + dfs + 枚举边）
int p[MAXN]; //并查集
int finds(int x){if(p[x]==-1) return x;else return (p[x]=finds(p[x]));
}bool vis[MAXM];
int w[MAXN][MAXN];
int mst(){ //kruskalfill_n(p+1, n, -1);fill_n(vis, m, false);for(int i=1; i<=n; i++) g[i].clear();sort(e, e+m);int ans=0;for(int i=0, j=0; i pre;//求mst中任意两点间的最大边权
void dfs(int u, int fa){for(int i=0; i
14.优先队列优化的 Dijkstra
void Dijkstra(int s){ for(int i=0; i<=mVertex; i++) dis[i]=INF; dis[s]=0; priority_queue q; q.push((node){0,s}); memset(done, 0, sizeof(done)); while(!q.empty()){ node t=q.top(); q.pop(); int u_ = t.u; if(done[u_]) continue; done[u_]=true; for(int x=h[u_]; x!=-1; x=next[x]) if(dis[v[x]]-dis[u_]>w[x]){ dis[v[x]] = dis[u_] + w[x]; p[v[x]] = x; q.push((node){dis[v[x]],v[x]}); } }
}
15.2B了再补吧。。。
转载于:https://www.cnblogs.com/ramanujan/p/3364299.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！