1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
| #include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define NUM 5
#define INF 2000000000
using namespace std;
struct edge
{
int f,t,w,next;
edge(int _f,int _t,int _w,int _next):f(_f),t(_t),w(_w),next(_next){}
edge(){}
int operator<(const edge &x)
const{return w<x.w;} //kruskal限定
} e[NUM+10];
int head[NUM+10],c=0;
void adde(int f,int t,int w)
{
e[++c]=edge(f,t,w,head[f]);
head[f]=c;
} //linjiebiao
int g[NUM+10][NUM+10]; //linjiejvzhen
void adds(int f,int t,int w)
{
/*
g[f][t]=w;
g[t][f]=w;*/
adde(f,t,w);
adde(t,f,w);
}
void floyd_1()
{
for (int k=1;k<=6;k++)
for (int i=1;i<=6;i++)
for (int j=1;j<=6;j++)
g[i][j]=g[i][j]>(g[i][k]+g[k][j])?(g[i][k]+g[k][j]):g[i][j];
} //n^3
int dis[NUM+1];
void dj_0(int src)
{
bool vis[NUM+1]={0};
dis[src]=0;
/*
for(int i=1;i<=NUM;i++)
{
int minn=INF,mind;
for (int j=1;j<=NUM;j++)
if (dis[j]<minn&&!vis[j]) {minn=dis[j];mind=j;}
// zhao min yongdui->faster
vis[mind]=1;
for (int j=head[mind];j;j=e[j].next)
if (!vis[e[j].t])
dis[e[j].t]=dis[e[j].t]<(e[j].w+dis[mind])?dis[e[j].t]:(e[j].w+dis[mind]);
}*/ //normal mode
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.push(make_pair(0,src));
while(!q.empty())
{
pair<int,int> t=q.top();
q.pop();
if (vis[t.second]) continue; //texing
vis[t.second]=1; //t.second==mind
for (int j=head[t.second];j;j=e[j].next)
{
if (dis[t.second]+e[j].w<dis[e[j].t])
{
dis[e[j].t]=dis[t.second]+e[j].w;
q.push(make_pair(dis[e[j].t],e[j].t)); //texing
}
}
}
// qq(dui) mode
}
void spfa_0(int src)
{
queue<int> q;
int vis[NUM+1]={0}; //vis[src]=0; //meiyouyong dagai
dis[src]=0;
q.push(src);
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0; //important
for(int i=head[now];i;i=e[i].next)
{
if (dis[e[i].t]>e[i].w+dis[now])
{
dis[e[i].t]=e[i].w+dis[now];
if (!vis[e[i].t])
{
q.push(e[i].t);vis[e[i].t]=1;
}
}
}
}
}
//kruskal
int fa[NUM],m; //m=边数
int findset_n(int q)
{
return fa[q]?findset_n(fa[q]):q;
}//查询代表元素_n (normal) 仅查询
int findset(int q)
{
return fa[q]?fa[q]=findset(fa[q]):q;
} //压缩路径的同时输出代表元素
void unset(int a,int b)
{
int ta=findset(a),tb=findset(b);
if(ta!=tb) //a,b如果为同一集合会很糟糕...
fa[ta]=tb;
}
int kruskal()
{
sort(e,e+m);//从小到大
int tot=0,ans=0;
for (int i=0;i<=m;i++)
{
int f1=findset(e[i].f),f2=findset(e[i].t);
if(f1!=f2)
{
fa[f1]=f2; //此时的并查集只起到集合作用，不能代表树
tot++;ans+=e[i].w;
if(tot==m) break; //最小生成树：边数=节点数-1 其实不加这一句应该也可以
}
}
return ans; //最小值权值和
}
int main()
{
/*
adde(1,2,1);
adde(2,3,2);
adde(3,1,3);
adde(1,4,4);
adde(1,5,5);
adde(2,4,6);*/
memset(g,0x3f,sizeof(g)); //init g
memset(dis,0x3f,sizeof(dis));
/*
adds(1,2,1);
adds(2,4,6);
adds(2,3,3);
adds(3,1,3);
adds(3,5,3);
adds(5,1,5);
//test 1
adds(1,5,5);
adds(5,4,6);
adds(1,4,4);
adds(4,3,3);
adds(1,2,8);
adds(2,3,3);
//test 2
//dj_0(1);
spfa_0(1);
for (int i=1;i<=NUM;i++)
printf("%d:%d ",i,dis[i]);
//floyd_1();*/
/*
fa[4]=1;
fa[2]=1;
fa[3]=2;
fa[6]=5;
fa[8]=6;
fa[7]=5;
fa[10]=3;
printf("%d",findset(3));
cutset(10);
unset(4,7);*/
/*
int i=0;
e[i++]=edge(1,5,5,0);
e[i++]=edge(5,4,6,0);
e[i++]=edge(1,4,4,0);
e[i++]=edge(4,3,3,0);
e[i++]=edge(2,1,8,0);
e[i++]=edge(3,2,3,0); //最后一个选项没有用，只要普通的边就行 并且貌似kruskal的图应该是有向的
m=6;
printf("%d",kruskal());*/
return 0;
}
|