最近整理了一下最小生成树和最短路的问题：

并查集：以前些的代码find函数是非递归形式的，现在改成了递归形式的，感觉代码量少了好多，但是消耗了栈空间，不知道这样是不是好，附上 核心代码：

define maxn 1010

int p[maxn]; int n,m; void init(){for(int i=1;i<=n;i++) p[i]=i;} int find(int x) { return (x==p[x])?x:(p[x]=find(p[x])); } void Union(int a,int b){ p[find(a)]=find(b); }

后来发现可以加一个优化防止退化树的产生，自己没有验证过，感觉可以：

void Union(int a,int b){ p[a] = p[find(a)]=find(b); }

还有就是，自从学会prim后就不太用kruskal了，所以明天要是碰到kruskal的变形就“杯具”了，我现在用的prim代码相对以前得要简短一些，附上 核心代码(有点问题就是下面的代码解决不了生成树不存在的问题，需要在添加一点信息);

void prim(){ for(int i=1;i<=n;i++) dist[i]=INF,vi[i]=0; dist[1]=0; int ans=0; while(1){ int u=-1,Min=INF; for(int i=1;i<=n;i++) if(i==-1 || (!vi[i] && dist[i]<Min)) Min=dist[u=i]; if(u==-1) break; ans+=Min; vi[u]=1; for(int i=1;i<=n;i++) if(!vi[i] && map[u][i]<dist[i]) dist[i]=map[u][i]; } printf("%d\n",ans); }

dijkstra算法和prim是差不多一样的贪心的思想（略）

bellman_ford不太用啊，话说都可以用spfa实现，而spfa写起来也是很方便的：

核心代码：

queue Q; bool mark[maxn]; int dist[maxn]; int inque[maxn];

bool spfa(){ memset(mark,0,sizeof(mark)); memset(inque,0,sizeof(inque)); for(int i=0;i<n;i++) dist[i]=INF; dist[s]=0; mark[s]=true; //inque[s]++; Q.push(s); int u,v,w; while(!Q.empty()){ u=Q.front();Q.pop(); mark[u]=false; for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v;w=edge[i].w; if(dist[u]+w<dist[v]){ dist[v]=dist[u]+w; if(!mark[v]){ mark[v]=true; inque[v]++; if(inque[v]>n) return false; Q.push(v); } } } } return true; }

spfa算法可以加堆栈优化，在判断是否存在负环的时候有的时候比队列要快一些：

核心代码：

int sta[maxn];

void spfa(){ memset(mark,0,sizeof(mark)); for(int i=0;i<n;i++) dist[i] = INF; int u,v,w,top=0; sta[++top]=s; mark[s]=true; dist[s]=0; while(top){ u=sta[top--]; mark[u]=false; for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v;w=edge[i].w; if(dist[u]+w<dist[v]){ dist[v]=dist[u] + w; if(!mark[v]){ mark[v]=true; sta[++top]=v; } } } } }