當前位置：首頁 » 開發推廣 » 最小堆優化

最小堆優化

發布時間: 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.
講解的很清楚了

閱讀全文

最小堆優化

與最小堆優化相關的閱讀推薦