Блог пользователя lenohoo

Автор lenohoo, 12 лет назад, По-английски

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

并查集:以前些的代码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; } } } } }

Полный текст и комментарии »

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится