当前位置：首页 » 开发推广 » 最小堆优化

最小堆优化

发布时间: 2021-03-22 08:27:13

❶ Dijkstra算法的堆优化

设边数是e,总起来看，对堆的处理相当于对e个元素进行插入排序，是eloge.你外边又乘了一个n，是什么意思？注意堆是逐渐增大的，并不是规模一直是n

❷ 最小生成树 kruskal 算法如何优化

肯定是用优先队列好啊，单个边用堆的时间为log2n，不需要用Quicksort来对所有的边长排序（因为很多长边完全不需要），另外，还有一个，判断是否连通来去掉构成回路的边要用优化的并查集才行，同样可以在log2n时间内判断是否连通

❸ 有邻接矩阵，要求用dijkstra+堆优化+邻接链表求平均最短路径

本人写了 Ford-Fulkerson 邻接矩阵版本的 BFS 和 DFS 的模板和 Ford-Fulkerson 邻接表版本的 BFS 模板 , 还有 Dinic 的邻接矩阵和邻接表模板 , 共 5 个模板解此题 , 以下为 5 份模板的 AC 代码 :
[cpp] view plain
//Ford-Fulkerson
//邻接矩阵BFS
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 205
#define inf 2100000000
int c[MAXN][MAXN];
int pass[MAXN];
int bfs_max_flow(int n,int s,int t)
{
int pre[MAXN],low[MAXN],head,tail,que[1000],i,maxflow=0;
while (1)
{
memset(pre,-1,sizeof(pre));
head=tail=0;
low[s]=inf;que[tail++]=s;
pre[s]=0;
while (head<tail)
{
int x=que[head++];
for (i=1;i<=n;++i)
if ((c[x][i])&&(pre[i]==-1))
{
que[tail++]=i;
low[i]=low[x]<c[x][i]?low[x]:c[x][i];
pre[i]=x;
}
if (pre[t]!=-1)
{
x=t;
while (x!=s)
{
c[x][pre[x]]+=low[t];
c[pre[x]][x]-=low[t];
x=pre[x];
}
break;
}
}
if (pre[t]!=-1) maxflow+=low[t];
else return maxflow;
}
}
int main()
{
int n,m,i,a,b,d;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(c,0,sizeof(c));
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&d);
c[a][b]+=d;
}
printf("%d/n",bfs_max_flow(m,1,m));
}
}
//Ford-Fulkerson
//邻接矩阵DFS
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 205
#define inf 2100000000
int c[MAXN][MAXN];
int pass[MAXN];
int dfs(int n,int s,int t,int low)
{
int i,flow;
if (s==t) return low;
if (pass[s]) return 0;
pass[s]=1;
for (i=1;i<=n;++i)
{
if ((c[s][i])&&(flow=dfs(n,i,t,low<c[s][i]?low:c[s][i])))
{
c[s][i]-=flow;
c[i][s]+=flow;
return flow;
}
}
return 0;
}
int dfs_max_flow(int n,int s,int t)
{
memset(pass,0,sizeof(pass));
int maxflow=0,flow;
while (flow=dfs(n,s,t,inf))
{
memset(pass,0,sizeof(pass));
maxflow+=flow;
}
return maxflow;
}
int main()
{
int n,m,i,a,b,d;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(c,0,sizeof(c));
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&d);
c[a][b]+=d;
}
printf("%d/n",dfs_max_flow(m,1,m));
}
}
//Ford-Fulkerson
//邻接表BFS
#include<stdio.h>
#include<string.h>
#define MAXN 205
#define inf 2100000000
struct link
{
int nod,val;
link *next;
}head[MAXN];
int bfs_max_flow(int n,int s,int t)
{
int que[1000],he,ta,maxflow=0,low,pre[MAXN];link *p;
while (1)
{
memset(pre,-1,sizeof(pre));
he=ta=0;low=inf;
que[ta++]=s;
while (he<ta)
{
int x=que[he++];
p=head[x].next;
while (p!=NULL)
{
if ((pre[p->nod]==-1)&&(p->val))
{
que[ta++]=p->nod;
low=low<p->val?low:p->val;
pre[p->nod]=x;
}
p=p->next;
}
if (pre[t]!=-1)
{
x=t;
while (x!=s)
{
p=head[pre[x]].next;
while (p->nod!=x) p=p->next;
p->val-=low;
x=pre[x];
}
break;
}
}
if (pre[t]!=-1) maxflow+=low;
else return maxflow;
}
}
int main()
{
link *p,*s;int n,m,i,a,b,d,find;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=m;++i) {head[i].nod=head[i].val=0;head[i].next=NULL;}
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&d);
if (head[a].next!=NULL)
{
find=0;
p=head[a].next;
do
{
if (p->nod==b) {p->val+=d;find=1;break;}
p=p->next;
}while (p!=NULL);
if (!find)
{
s=new link;
s->nod=b;s->val=d;
s->next=head[a].next;
head[a].next=s;
}
}
else
{
s=new link;
s->nod=b;s->val=d;
s->next=NULL;
head[a].next=s;
}
}
printf("%d/n",bfs_max_flow(m,1,m));
}
}
//Dinic
//邻接矩阵
#include<stdio.h>
#include<string.h>
#define MAXN 205
#define oo 2100000000
int g[MAXN][MAXN],level[MAXN];
int bfs(int n,int s,int t)
{
int que[1000],head,tail,i;
head=tail=0;
que[tail++]=s;
memset(level,-1,sizeof(level));
level[s]=1;
while (head<tail)
{
int x=que[head++];
for (i=1;i<=n;++i)
if ((g[x][i])&&(level[i]==-1))
{
level[i]=level[x]+1;
que[tail++]=i;
}
}
return level[t]+1;
}
int dinic(int n,int s,int t)
{
int maxflow=0,i;
while (bfs(n,s,t))
{
int pos,path[MAXN],cut=0,low,find;
pos=0;
path[pos++]=s;find=1;
while (1)
{
find=1;low=oo;
while ((path[pos-1]!=t)&&(find))
{
find=0;
for (i=1;i<=n;++i)
if ((level[i]==level[path[pos-1]]+1)&&(g[path[pos-1]][i]))
{
path[pos++]=i;
find=1;
break;
}
else if (i==n) break;
}
if (path[pos-1]==t)
{
for (i=0;i<pos-1;++i) if (low>g[path[i]][path[i+1]]) {low=g[path[i]][path[i+1]];cut=i;}
maxflow+=low;
for (i=0;i<pos-1;++i)
{
g[path[i]][path[i+1]]-=low;
g[path[i+1]][path[i]]+=low;
}
pos=cut+1;
}
else
{
if (pos==1) break;
else {level[path[pos-1]]=-1;pos--;}
}
}
}
return maxflow;
}
int main()
{
int n,m,i,a,b,d;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(g,0,sizeof(g));
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&d);
g[a][b]+=d;
}
printf("%d/n",dinic(m,1,m));
}
return 0;
}
//Dinic
//邻接表
#include<stdio.h>
#include<string.h>
#define MAXN 205
#define oo 2100000000
struct link
{
int nod,val;
link *next;
}head[MAXN];
int level[MAXN],g[MAXN][MAXN];
int bfs(int n,int s,int t)
{
int que[MAXN],he,ta,v;
link *p;
he=ta=0;
que[ta++]=s;
memset(level,-1,sizeof(level));
level[s]=0;
while (he<ta)
{
v=que[he++];
p=head[v].next;
while (p!=NULL)
{
if ((p->val)&&(level[p->nod]==-1))
{
level[p->nod]=level[v]+1;
que[ta++]=p->nod;
}
p=p->next;
}
}
return level[t]+1;
}
int dinic(int n,int s,int t)
{
int path[MAXN],pos,low,i,maxflow=0,cut;
link *p;
while (bfs(n,s,t))
{
pos=0;cut=0;
path[pos++]=s;
while (1)
{
p=head[path[pos-1]].next;
while ((p!=NULL)&&(path[pos-1]!=t))
{
if ((p->val)&&(level[p->nod]==level[path[pos-1]]+1))
{
path[pos++]=p->nod;
p=head[path[pos-1]].next;
continue;
}
else if (p->next==NULL) break;
if (p!=NULL) p=p->next;
}
if (path[pos-1]==t)
{
low=oo;
for (i=0;i<pos-1;++i)
{
p=head[path[i]].next;
while (p->nod!=path[i+1]) p=p->next;
if (p->val<low) {low=p->val;cut=i;}
}
maxflow+=low;
for (i=0;i<pos-1;++i)
{
p=head[path[i]].next;
while (p->nod!=path[i+1]) p=p->next;
p->val-=low;
}
pos=cut+1;
}
else if (pos==1) break;
else {level[path[pos-1]]=-1;pos--;}
}
}
return maxflow;
}
int main()
{
link *p,*s;int m,n,a,b,d;int i;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=n;++i) head[i].next=NULL;
for (i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&d);
if (head[a].next!=NULL)
{
p=head[a].next;
while (p!=NULL)
{
if (p->nod==b)
{
p->val+=d;
break;
}
p=p->next;
}
if (p==NULL)
{
s=new link;
s->nod=b;
s->val=d;
s->next=head[a].next;
head[a].next=s;
}
}
else
{
s=new link;
s->nod=b;
s->val=d;
s->next=NULL;
head[a].next=s;
}
}
printf("%d/n",dinic(m,1,m));
}
return 0;
}

❹ Pascal 最小值(时间复杂度 O(N))

对于堆的操作，加入和删除（取出）一个元素的时间复杂度都是O(logn)的。
如果我需要每次从一些数中取出最大值或最小值，正常的方法扫描一遍所有的数的话，复杂度为O(n)，可是如果把这些数用堆储存的话，那么我们每次取最大值或最小值都是取堆顶的元素，只要O(logn)的时间。这就是所谓的堆优化。
比如说，单源最短路(SSSP)中的迪杰斯特拉(Dijkstra)算法，思想是：每次找到一个距离最短的点，更新与其相邻的点的距离。如果普通的去找距离最短的点，需要找N次，而如果把所有的点储存在小根堆中，那么只需要找logN次。
堆优化在很多类似于需要多次找最大值或最小值的情况下，能比较有效的进行时间上的优化。

❺ Dijkstra 堆优化堆的作用是不是仅仅作用在每次寻找能到达的节点中距离最小的那个

您的问题不明确。
堆的作用是在每次枚举中找到最小的点距，并用这个点进行与内其他没有操作的点容做松弛操作。
使得原本需要枚举n^2顶点变成只需枚举n次，每次维护的费用是O(lgn)。在效率上，枚举的复杂度由O(n^2)变成了O(nlgn),是很可观的。
如果我没有曲解您的仅仅这一词的意义的话，堆的作用应该是作用在当前权值最小的顶点上，考虑整个算法，堆作用在每个顶点各一次

❻ dijkstra+堆优化求修改

我给你改好了；
w是加不是×
然后tot开始为1
0.0
一开始我还把你的同名问题提交了。。。费我币啊！！！！
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int v;
int d;
int p;
}heap;
heap a[300000];
int e[300000],next[300000];
int cost[300000];
int g[300000],pos[300000];
int tot=1,top;
int n,k1,k;
void add(int u,int v,int w)
{
e[tot]=v;
cost[tot]=w;
next[tot]=g[u];
g[u]=tot++;
}
void swap(int i,int j)
{
heap t;
t=a[i];
a[i]=a[j];
a[j]=t;
pos[a[i].v]=i;
pos[a[j].v]=j;
}
void up(int i)
{
while (i!=1 && a[i/2].d>a[i].d)
{
swap(i,i/2);
i/=2;
}
}
void update(int u,int v,int w)
{
if (w+a[pos[u]].d<a[pos[v]].d)
{
a[pos[v]].p=u;
a[pos[v]].d=w+a[pos[u]].d;
up(pos[v]);
}
}
void change()
{
int i=2;
while (i<=top)
{
if (i<top && a[i+1].d<a[i].d) ++i;
if (a[i/2].d>a[i].d)
{
swap(i/2,i);
i*=2;
}
else break;
}
}
void del()
{
swap(1,top);
--top;
change();
}
int Dijkstra(int ST,int END)
{
int i,u,p;
for (i=1;i<=n;i++)
a[i].d=99999999,
a[i].v=pos[i]=i;
a[ST].p=ST;
a[ST].d=0;
swap(ST,1);
top=n;
while (top!=0)
{
u=a[1].v;
p=g[a[1].v];
del();
while (p!=0)
{
if (pos[e[p]]<=top)
update(u,e[p],cost[p]);

p=next[p];
}
}
return a[pos[END]].d;
}
int main( )
{
int i;
int x,y,z;

scanf("%d%d",&n,&k1);

for (i=1;i<=k1;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}

printf("%d\n",Dijkstra(1,2));

for (i=1;i<=n;i++)
if (a[pos[i]].d!=99999999)
printf("1 -> %d : %d\n",i,a[pos[i]].d);
else printf("Point 1 is not connected to Point %d\n",i);

system("pause");
return 0;
}
改好的
还有那个SB
嘴别这么臭，会遭报应的
你那脑残话真是到了顶，太没素质了

❼ 怎样用堆优化最小生成树Prim

原理就是做个堆保存所有未加入的点到当前强连通分量的距离这样每次选取只需要O(1) 维护用O(logN) 比直接枚举选点的O(N)要快
代码（这个写的还可以能当模板用）：
#include <cstdio>
#include <cstring>
#define INF 0xfff
#define typec Node
#define parent(i) ((i) / 2)
#define left(i) ((i) * 2)
#define right(i) ((i) * 2 + 1)

struct Node
{
int u, lowc;
Node(int su, int sl)
{
u = su; lowc = sl;
}
Node(){}
inline bool operator < (Node b) const
{
return lowc < b.lowc;
}
inline bool operator <= (Node b) const
{
return lowc <= b.lowc;
}
};

void swapc(typec &a, typec &b)
{
typec t = a;
a = b;
b = t;
}

void swim(typec heap[], int i)
{
if ( i < 2 )
return;

int p = parent(i);
if ( heap[i] < heap[p] )
{
swapc(heap[i], heap[p]);
}
swim(heap, p);
}

void sink(typec heap[], int i, int size)
{
int l = left(i);
if ( l > size )
return;

if ( l == size )
{
if ( heap[l] < heap[i] )
swapc(heap[l], heap[i]);
return;
}
int r = right(i);
int t = heap[l] < heap[r] ? l : r;
if ( heap[i] <= heap[t] )
return;

swapc(heap[i], heap[t]);
sink(heap, t, size);
}

void del(typec heap[], int i, int &size)
{
swapc(heap[i], heap[size]);
--size;
sink(heap, i, size);
}

int w[110][110], vis[110];
typec n[110];
int N;

int prim() // vertex: 0 ~ N-1
{
int i, res = 0;
memset(vis, 0, sizeof vis);

for ( i = 1; i < N; ++i ) // heap: 1 ~ size
{
n[i].lowc = w[0][i] ? w[0][i] : INF;
n[i].u = i;
}
for ( i = N / 2; i < N; ++i )
{
swim(n, i);
}
int size = N - 1, tw;
typec t;
while ( size )
{
t = n[1];
del(n, 1, size);
if ( vis[t.u] == 0 )
{
res += t.lowc;
vis[t.u] = 1;
for ( i = 1; i <= size; ++i )
{
tw = w[n[i].u][t.u];
if ( tw && tw < n[i].lowc )
{
n[i].lowc = tw;
swim(n, i);
}
}
}
}
return res;
}

int main()
{
int i, j, T;
scanf("%d", &T);
while ( T-- )
{
scanf("%d", &N);
for ( i = 0; i < N; ++i )
{
for ( j = 0; j < N; ++j )
scanf("%d", &w[i][j]);
}
printf("%d\n", prim() );
}
return 0;
}

❽ 你好啊，老师。怎么求最小割端集的数目，最小割边集和最小混合割集的数目万分感谢O(∩_∩)O~开心每一天

不好意思一年没有编最小割了基本快忘了
最小割一般都是做边割集，
至于点割集，只要把一个点拆成2个点，再连一条边就行
最小割=最大流啊，如果只要输出一个数量那直接一遍最大流就行
如果要输出点集、边集就会稍微麻烦一点

找到以前写的一个程序，发现看一看还是蛮有用的（虽然效率低，但是容易懂）
题目是USCO 5.4的TELECOWMUNICATION
题目意思就是求N个点S-T的最小点割集
我的程序我贴一下吧（很烂的算法，看看就行，别学）

procere dfs(k,dep:longint); //数据弱，深搜求最大流
var
i:longint;
procere go;
var
i,min:longint;
begin
min:=maxlongint;
for i:=1 to dep-1 do
if a[path[i],path[i+1]]<min then min:=a[path[i],path[i+1]];
for i:=1 to dep-1 do
begin
dec(a[path[i],path[i+1]],min);
inc(a[path[i+1],path[i]],min);
end;
tot:=tot+min;
end;
begin
visited[k]:=true;
path[dep]:=k;
if k=s then
begin
go;
ok:=true;
exit;
end;
for i:=1 to n do
begin
if ok then exit;
if not visited[i] then
if a[k,i]>0 then
dfs(i,dep+1);
end;
end;
begin
assign(input,'telecow.in');
assign(output,'telecow.out');
reset(input);
rewrite(output);
fillchar(a,sizeof(a),0);
readln(n,m,t,s);
t1:=t;s1:=s;
for i:=1 to n do begin a[i*2-1,i*2]:=1; a[i*2,i*2-1]:=1; end;
for i:=1 to m do //拆点
begin
readln(x,y);
a[x*2-1,y*2]:=1;
a[y*2-1,x*2]:=1;
end;
n:=n*2;
for i:=1 to n do for j:=1 to n do f[i,j]:=a[i,j];
t:=t*2-1; s:=s*2;
tot:=0;
repeat
fillchar(visited,sizeof(visited),false);
ok:=false;
dfs(t,1);
until not ok;
writeln(tot);
temp:=tot;
p:=false;
for i:=1 to n div 2 do
if i<>t1 then
if i<>s1 then
begin
a:=f;
a[i*2-1,i*2]:=0;a[i*2,i*2-1]:=0;
tot:=0;
repeat
fillchar(visited,sizeof(visited),false);
ok:=false;
dfs(t,1);
until not ok; //看i是不是一定在最小割集中
if tot<temp then
begin
temp:=tot;
if p then write(' ');
write(i);
p:=true;
f[i*2,i*2-1]:=0; f[i*2-1,i*2]:=0; //在的话删除
end;
end;
writeln;
close(input);
close(output);
end.
其实还是很容易理解的，但效率不高

下面说下求最小割集最普遍，也是效率很高的算法：Stoer-Wagner算法
其实就是n遍最大生成树，具体方法很容易搜到
1.min=MAXINT，固定一个顶点P
2.从点P用类似prim的s算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边
3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min
4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并）
5.转到2，合并N-1次后结束
6.min即为所求，输出min
这种方法加上堆优化就很快了

我二分图什么的非常弱，也许帮不上你什么忙
你也可以自己到网上找Stoer-Wagner的标程研究一下

❾ Dijkstra 堆优化 PASCAL

给你看个源程序
program SSSP;{single source shortest path}
{假设一个图的最大节点数为1000，所有运算在integer范围内}
{程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度}
const maxn=1000;{最大节点数}
var
n:integer;{节点个数}
deg:array[1..maxn] of integer;{每个节点的度数}
list:array[1..maxn,1..maxn,1..2] of integer;{邻接表，第一个元素表示边的中点，第二个元素表示边的长度}

count:integer;{堆内元素个数计数器}
heap:array[1..maxn] of integer;{heap[i]表示堆内的第i的元素的节点编号}
pos:array[1..maxn] of integer;{表示编号为i的元素在堆内的位置}
key:array[1..maxn] of integer;{表示节点1到节点i的最短距离}
exist:array[1..maxn] of boolean;{表示节点i是否存在于堆中}

i,j,now:integer;

procere swap(var i,j:integer);{交换整数i和j}
var temp:integer;
begin
temp:=i;
i:=j;
j:=temp;
end;

procere heapify(p:integer);{调整堆的过程}
var best:integer;
begin
best:=p;
if (p*2<=count) and (key[heap[p*2]]<key[heap[best]]) then best:=p*2;
if (p*2+1<=count) and (key[heap[p*2+1]]<key[heap[best]]) then best:=p*2+1;
if best<>p then
begin
swap(pos[heap[p]],pos[heap[best]]);
swap(heap[p],heap[best]);
heapify(best);
end;
end;

procere modify(id,new_key:integer);{判断new_key与key[id]大小，并修改key[id]大小}
var p:integer;
begin
if (new_key<key[id]) then
begin
key[id]:=new_key;
p:=pos[id];
while (p>1) and (key[heap[p]]<key[heap[p div 2]]) do
begin
swap(pos[heap[p]],pos[heap[p div 2]]);
swap(heap[p],heap[p div 2]);
p:=p div 2;
end;
end;
end;

procere extract(var id,dis:integer);{读取堆中最小元素的节点编号和节点1到该节点的距离}
begin
id:=heap[1];
dis:=key[id];
dec(count);
if (count>0) then
begin
swap(pos[heap[1]],pos[heap[count+1]]);
swap(heap[1],heap[count+1]);
heapify(1);
end;
end;

begin
{读取数据}
readln(n);
for i:=1 to n do
begin
read(deg[i]);
for j:=1 to deg[i] do read(list[i,j,1],list[i,j,2]);
end;
{初始化}
for i:=1 to n do
begin
exist[i]:=true;
pos[i]:=i;
heap[i]:=i;
key[i]:=maxint;
end;
count:=n;
key[1]:=0;
{dijkstra算法的主要操作}
while (count>0) do
begin
extract(i,now);
if now=maxint then break;
for j:=1 to deg[i] do
if exist[list[i,j,1]] then modify(list[i,j,1],now+list[i,j,2]);
end;
{输出}
if key[n]=maxint then writeln('Not Connected!'){节点1和节点n不连通}
else writeln(key[n]);{连通}
end.
讲解的很清楚了

阅读全文

最小堆优化

与最小堆优化相关的阅读推荐