最小生成树

Kruskal

//Kruskal struct edge{ int from,to,val; }e[maxn]; bool operator < (const edge&a,const edge&b){ return a.val<b.val;//边按边权排序 } int find(int a){ return fa[a]==a ? fa[a] : fa[a]=find(fa[a]); } void Kruskal(){ int cnt=0; sort(e+1,e+m+1); for(int i=1,j=0;i<=m,j<n-1;i++){ int a=e[i].from,b=e[i].to; if(find(a)!=find(b)){ //你想干嘛干嘛吧 fa[find(a)]=find(b); j++;//加入n-1条边就可以跳出循环啦 } } }

最小完全图

//最小树的最小完全图： //在Kruskal算法中，当前添加的边是连接两边所在集合的边权最小的边 //所以将边从小到大考察，该边左右端点所在并查集连的边数为f[u]*f[v]-1（因为本来已经有这条边了嘛） //然后因为这条边是最小的，所以其他的边最小也应该是e[i].val+1 //合并两边并查集，搞腚 //在并查集中，用f[]数组记录以i为根节点的并查集大小， //union操作实现如下： void Union(int a,int b){ int x=find(a),y=find(b); //以将a合并到b为例 f[y]+=f[x]; fa[x]=y; }

Prim&前向星

typedef pair<int,int> pii;//<dist,idx>，用于堆排序 int cnt=0,head[maxn],dis[maxn]; bool vis[maxn]; struct edge{ int to,next,val; }e[maxn*3]; bool cmp(pii a,pii b){ return a.first>b.first;//小根堆 } void add(int u,int v,int val){ for(int i=head[u];~i;i=e[i].next){ if(e[i].to==v){ if(e[i].val>val) e[i].val=val; return; } } e[++cnt].to=v; e[cnt].val=val; e[cnt].next=head[u]; head[u]=cnt; } void Prim(int s){ int ans=0; memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pii,vector<pii>,cmp> q; for(int i=head[s];~i;i=e[i].next){ dis[e[i].to]=e[i].val;//初始化与源点相连的所有节点 q.push(make_pair(dis[e[i].to],e[i].to))//入队待扩展 } dis[s]=0; vis[s]=1;//初始化源点 while(!q.empty()){ pii u=q.top(); q.pop(); if(vis[u.second]) continue;//跳过已访问节点 vis[u.second]=1; ans+=u.first;//用于统计最小生成树边权和 for(int i=head[u.second];~i;i=e[i].next){//将与新加入节点相连的所有节点加入堆 int j=e[i].to; if(!vis[j]&&(dis[j]>e[i].val||dis[j]==-1)){//如果目标节点未被访问且（访问边是当前最小的边或目标节点尚未被访问过） dis[j]=e[i].val; //就将dis更新为当前边权，入堆 q.push(make_pair(dis[j],j)); } } } printf("%d\n",ans);//输出最小生成树边权和 }

最短路

SPFA

int dis[maxn]; bool vis[maxn]; bool SPFA(int s){//传入源点，传出是否有负环 int stat[maxn];//统计节点的入队次数，大于节点数n说明有负环 bool flag=0; memset(stat,0,sizeof(stat)); memset(dis,0x3f,sizeof(dis));//到源点的距离 memset(vis,0,sizeof(vis)); //是否在队列内 queue<int> q; q.push(s); vis[s]=1; while(!q.empty()){ if(flag) break; int tmp=q.front(); q.pop(); vis[tmp]=0; for(int i=head[tmp];~i;i=e[i].next){ int cur=e[i].to; if(dis[cur]>dis[tmp]+e[i].val){ dis[cur]=dis[tmp]+e[i].val; vis[cur]=1; stat[cur]++; if(stat[cur]>n){ flag=1; break; } q.push(cur); } } } return flag; }

Dijkstra

void Dijkstra(int s){ //堆优化乱搞 priority_queue<pii> q; bool cmp(pii a,pii b){ return a.first>b.first; } //init memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); q.push(make_pair(dis[s]=0,s));//初始化源点 for(int i=head[s];~i;i=e[i].next){ int cur=e[i].to; dis[cur]=e[i].val; q.push(make_pair(dis[cur],cur)); } while(!q.empty()){ int tmp=q.top(); q.pop(); if(vis[tmp]) continue; for(int i=head[tmp];~i;i=e[i].next){ int cur=e[i].to; if(!vis[cur]&&dis[cur]>dis[tmp]+e[i].val){ dis[cur]=dis[tmp]+e[i].val; vis[cur]=1; q.push(make_pair(dis[cur],cur)); } } } }

Floyd

普通版

//普通版Floyd void Floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; //在读入边的时候边权作为dis即可 }

求最小环

//算最小环 //一个环可以拆成一条链加一条边， //算floyd的时候保证中间点k的编号比i大比j小，就可以保证首尾不经过k点 void Floyd_minimum_cycle(){ for(int k=1;k<=n;k++){ for(int i=1;i<k;i++) for(int j=k+1;j<=n;j++) ans=min(ans,dis[i][j]+map[i][k]+map[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } //有向图求最小环，直接用floyd就可以，以s为起点的环长度为d[s][k]+d[k][s] //也可以跑Dijkstra先算从s到所有点的最短距离，再算所有点到s的最短距离 //求以s为终点的单（终点）最短路，把图上所有边反过来就好

最近公共祖先（LCA）

Tarjan

bool flag[maxn],answered[maxn]; vector<pii> qes;//用来存询问 void csh(){//初始化... memset(flag,0.sizeof(flag));//用来标记是否已经算过LCA了 for(int i=1;i<=n;i++) fa[i]=i; memset(head,0,sizeof(head)); memset(answered,0,sizeof(answered));//用来标记是否已经回答过询问了 } void Union(int x,int y){ fa[find(y)]=find(x); return;//将y集合加入x中 } void LCA(int p,int f){//p为当前节点，f为当前节点的父亲（防止倒流...） for(int i=head[p];~i;i=e[i].next){ if(e[i].to!=f&&!flag[to]){ LCA(e[i].to,p); Union(p,e[i].to); flag[to]=1; } } //处理询问 } 使用方法：LCA(根节点，0);

RMQ+DFS（倍增）

void dfs(int rt){ for(int i=head[rt];~i;i=e[i].next){ if(!dep[e[i].to]){ dep[e[i].to]=dep[rt]+1; p[e[i].to][0]=rt;//p[i][0]为i的直接父节点 dfs(e[i].to); } } return; } void init_bz(){ //p[i][j]为i节点的第2^j祖先 for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) if(p[i][j-1]!=-1) p[i][j]=p[p[i][j-1]][j-1]; return; } int LCA(int a,int b){ int i,j; if(dep[a]<dep[b]) swap(a,b);//保证a是b的儿子节点 for(i=0;(1<<i)<=dep[a];i++); i--; for(j=i;j>=0;j--) if(dep[a]-(1<<j)>=dep[b]) a=p[a][j]; if(a==b) return a; for(j=i;j>=0;j--) if(p[a][j]!=-1&&p[a][j]!=p[b][j]){ a=p[a][j]; b=p[b][j]; } return p[a][0]; } 使用方法： dfs(1);//1为根节点 dep[1]=0; p[1][0]=1; //如果dfs时还要记与根节点距离的话，传入一个参数pa表示dfs节点的父节点即可

二分图

二分图染色

int col[maxn]; bool flag=1; void ran(int p,int rt,int c){ if(col[rt]!=-1&&col[rt]!=c){ flag=0; return; } else { for(int i=head[rt];i!=0;i=e[i].next){ int cur=e[i].to; ran(rt,cur,(c+1)%2); } return; } }

二分图最大匹配（匈牙利算法）

读入优化

inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*f; }//读入优化来一波~~

NTR算法主体

int nx,ny,match[maxn]; bool vis[maxn],w[maxn][maxn]; bool find(int x){ for(int i=1;i<=ny;i++){ if(!w[x][i]||vis[i]) continue;//用vis来标记这个人有没有被霸占 vis[i]=1;//霸占该人 if(match[i]==-1||find(match[i])){//如果该人没有匹配，或者匹配更改可行（可NTR） match[i]=x;//更改这个人的匹配到需要找对象的x身上 return 1;//NTR成功！ } } return 0;//返回：歌颂爱情的伟大！ } int suan(){ int ans=0; memset(match,-1,sizeof(match));//每个人初始化为没有对象 for(int i=1;i<=nx;i++){//对左边的每一个点尝试寻找对象 memset(vis,0,sizeof(vis));//千万记住初始化...最开始每个人都没有被霸占的 if(find(i)) ans++;//可匹配人数++ } return ans; } int m,a,b;//m是边的条数，a/b为临时变量 int main(){ nx=read(); ny=read(); for(int i=1;i<=m;i++){ a=read(); b=read(); w[a][b]=1; //这里默认左右两边的编号都是从1开始好了 //如果题目不一样的话，只需要简单修改下就可以了 } int out=suan(); if(out) printf("%d\n",out); else puts("No."); return 0; }

二分图最小完备匹配（KM算法）

不会网络流怎么破！！！！！！！！！！！！！

int nx,ny,linky[maxn]; double lack,w[maxn][maxn],lx[maxn],ly[maxn]; bool visx[maxn],visy[maxn]; bool find(int x){ visx[x]=1; for(int i=1;i<=ny;i++){ if(visy[i]) continue; int t=lx[x]+ly[i]-w[x][i]; if(t<0){ visy[i]=1; if(linky[i]==-1||find(linky[i])){ linky[i]=x; return 1; } } else if(t<lack) lack=t; } return 0; } double KM(){ memset(linky,-1,sizeof(linky)); for(int i=1;i<=ny;i++) ly[i]=0; for(int i=1;i<=nx;i++){ lx[i]=INF; for(int j=1;j<=ny;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; } for(int x=1;x<=nx;x++){ while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); lack=INF; if(find(x)) break; for(int i=1;i<=ny;i++){ if(visx[i]) lx[i]-=lack; if(visy[i]) ly[i]+=lack; } } } int ans=0; for(int i=1;i<=ny;i++) ans-=w[linky[i]][i]; return ans; }

拓扑排序

Kahn算法

priority_queue<int,vector<int>,greater<int> > s;//入度为0的集合，小根堆保证字典序最小 int in[maxn];//存放每个点的入度 vector<int> ans; void Kahn(){ for(int i=1;i<=n;i++) if(in[i]==0) s.push(i); while(!s.empty()){ int cur=s.top(); s.pop(); ans.push_back(cur); for(int i=head[cur];i!=0;i=e[i].next){ int tmp=e[i].to; in[tmp]--; if(in[tmp]==0) s.push(tmp); } } return; }

强连通分量

%Tarjan

stack<int> s; bool vis[maxn]; int dfn[maxn],low[maxn],cnt=0,num=0;//时间戳，能回到的最远祖先，计数器（标记节点），计数器（标记强连通分量） int qlt[maxn];//点i属于哪一个强连通分量 vector<int> ans[maxn]; void Tarjan(int u){ dfn[u]=low[u]=++cnt; vis[u]=1; s.push(u); for(int i=head[u];i!=0;i=e[i].next){ int cur=e[i].to; if(!vis[cur]){ Tarjan(cur); low[u]=min(low[u],low[cur]); } else if(!qlt[cur]) { low[u]=min(low[u],low[cur]); } } if(dfn[u]==low[u]){ num++; while(1){ int tmp=s.top(); s.pop(); qlt[tmp]=num; if(tmp==u) break; } } }

转载于:https://www.cnblogs.com/leotan0321/p/6081364.html