noip提高组图论模板

noip提高组图论模板

//拓扑排序void Top(){ for(i=1;i<=n;++i) if(!du[i]) q.push(i); while(!q.empty()){ int u=q.front();q.pop(); ans[++num]=u; for(int i=head[u];i;i=nxt[i]){ int t=to[i]; if(!--du[t]) q.push(t); } }}//有向图tarjanvoid tarjan(int cur){ dfn[cur]=low[cur]=++sign; sta[++top]=cur,insta[cur]=1; for(int i=first[cur];i;i=next[i]){ int t=to[i]; if(!dfn[t]) tarjan(t),low[cur]=min(low[cur],low[t]); else if(insta[t]&&low[cur]>dfn[t]) low[cur]=dfn[t]; } if(low[cur]==dfn[cur]){ do{insta[sta[top]]=0,id[sta[top]=++sum;}while(sta[top--]!=cur); }}//无向图tarjanvoid tarjan(int cur,int in_E){ dfn[cur]=low[cur]=++sign; for(int i=first[cur];i;i=next[i]){ int t=to[i]; if(!dfn[t]){ tarjan(t,i); low[cur]=min(low[cur],low[t]); if(low[t]>dfn[cur]){ bridge[i]=bridge[i^1]=1; } } else if(i!=(in_E^1)){ low[cur]=min(low[cur],dfn[t]); } }}void Make_id(int cur,int Id){ id[cur]=Id; for(int i=first[cur];i;i=next[i]){ int t=to[i]; if(id[t]||bridge[i]) continue; Make_id(t,Id); }} //dijkstraint dfs(int st,int ed){ memset(dis,127,sizeof(dis)); q.push(make_pair(0,st)); dis[st]=0; while(!q.empty()){ int u=q-().second; q.pop(); for(int i=first[u];i;i=next[i]){ int t=to[i]; if(dis[t]>dis[u]+w[i]){ dis[t]=dis[u]+w[i]; q.push(make_pair(-dis[t],t)); } } } return dis[ed];} //spfavoid spfa(int st){ queue q; dis[st]=0; q.push(st); while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=0; for(int i=first[x];i;i=next[i]){ int t=to[i]; if(dis[t]>dis[x]+w[i]){ dis[t]=dis[x]+w[i]; if(!vis[t]){vis[t]=1;q.push(t);} } } }}//dfs_spfa找负环 void dfs(int u){ if(vis[u]){flag=1;return;} vis[u]=1; if(flag) return; for(int i=first[u];i;i=next[i]){ int t=to[i]; if(dis[t]>dis[u]+w[i]){ dis[t]=dis[u]+w[i]; dfs(t); } }vis[u]=0;}//Kruscalvoid Kruskal(){ sort(E+1,E+m+1,cmp); for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++){ int x=find(E[i].u),y=find(E[i].v); if(x!=y){ father[x]=y; add(x,y,E[i].w),add(y,x,E[i].w); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。