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; }
|