poj1251
用的是Kruskal算法 以及并查集
#include "iostream" using namespace std; #define maxsize 110 typedef struct Edge { int weight;//权值 int node1;//顶点 int node2;//顶点 } Edge; Edge e[maxsize]; int vis[maxsize]; int putIn(int n) { //输入 char ch; int num; char ch1; int t; int i,j,k=0; for (i=0;i<n-1;i++) { cin>>ch>>num; for (j=0;j<num;j++) { cin>>ch1>>t; e[k].weight=t; e[k].node1=ch-65; e[k].node2=ch1-65; k++; } } return k;//边的个数 } int cmp( const void *a ,const void *b) { Edge *aa=(Edge*)a; Edge *bb=(Edge*)b; return aa->weight>bb->weight?1:-1; } void union_node(int i,int len) { //将e[i].node1的集合并入e[i].node2的集合 int j; int t=vis[e[i].node1];//要先将vis[e[i].node1保存下来 因为循环中会改变值 for (j=0;j<len;j++) { if (vis[j]==t) { vis[j]=vis[e[i].node2]; } } } int Kruskal(int len,int n) { int i,j; int ans=0; //vis数组用做并查集 for (i=0;i<n;i++)//i<len是错的 应该是村庄个数 { vis[i]=i;//表示第i个元素属于第i个集合 } for (i=0;i<len;i++) { if (vis[e[i].node1]!=vis[e[i].node2])//如果该边的两个顶点在不同的集合 { //将两点并入一个集合 union_node(i,len); //累加权值 ans+=e[i].weight; } } return ans; } int main() { int n; int i,j; while(cin>>n) { if(n==0) break; int len=putIn(n); //按权值从小到大排序 qsort(e,len,sizeof(e[0]),cmp); //Kruskal算法生成最小生成树 int ans=Kruskal(len,n); //输出结果 cout<<ans<<endl; } return 0; }
poj 1287
prim
#include "iostream" using namespace std; #define MAXSIZE 1500 #define MAX 99999999 int map[MAXSIZE][MAXSIZE]; int vis[MAXSIZE]; int temp[MAXSIZE]; int main() { int n,m; while (1) { scanf("%d",&n); if (n==0) { break; } scanf("%d",&m); int ans=0; int i,j; for (i=0;i<n;i++) { for (j=0;j<n;j++) { map[i][j]=MAX; } } for (i=0;i<m;i++) { int t1,t2,w; scanf("%d%d%d",&t1,&t2,&w); if (w<map[t1-1][t2-1]) map[t1-1][t2-1]=w; } for (i=0;i<m;i++) { for (j=0;j<m;j++) { if (map[i][j]<map[j][i]) { map[j][i]=map[i][j]; } } } memset(vis,0,sizeof(vis)); for (j=0;j<n;j++) { temp[j]=MAX; } i=0; for (j=0;j<n;j++) { if (map[i][j]!=0) if (map[i][j]<temp[j]) { temp[j]=map[i][j]; } } vis[0]=1; while (i<n-1) { //找最小的边 int min=MAX; int minindex=0; for (j=0;j<n;j++) { if (vis[j]==1) { continue; } if (min>temp[j]) { min=temp[j]; minindex=j; } } //把最小的边的顶点加入集合 vis[minindex]=1; //更新temp for (j=0;j<n;j++) { if (map[minindex][j]!=0&&vis[j]!=1) if (map[minindex][j]<temp[j]) { temp[j]=map[minindex][j]; } } ans+=min; i++; } printf("%d\n",ans); } return 0; }
poj 2395
与1251一样
#include "iostream" using namespace std; #define maxsize 10015 typedef struct Edge { int weight;//权值 int node1;//顶点 int node2;//顶点 } Edge; Edge e[maxsize]; int vis[maxsize]; void putIn(int n,int m) { int num=0; //输入 for (int i=0;i<m;i++) { int k1,k2,w; cin>>k1>>k2>>w; e[num].node1=k1; e[num].node2=k2; e[num].weight=w; num++; } //return m;//边的个数 } int cmp( const void *a ,const void *b) { Edge *aa=(Edge*)a; Edge *bb=(Edge*)b; return aa->weight>bb->weight?1:-1; } void union_node(int i,int len) { //将e[i].node1的集合并入e[i].node2的集合 int j; int t=vis[e[i].node1];//要先将vis[e[i].node1保存下来 因为循环中会改变值 for (j=0;j<len;j++) { if (vis[j]==t) { vis[j]=vis[e[i].node2]; } } } int Kruskal(int m,int n) { int i,j; int ans=0; //vis数组用做并查集 for (i=0;i<n;i++)//i<len是错的 应该是村庄个数 { vis[i]=i;//表示第i个元素属于第i个集合 } int count=0; int max=0; for (i=0;i<m;i++) { if (vis[e[i].node1]!=vis[e[i].node2])//如果该边的两个顶点在不同的集合 { //将两点并入一个集合 union_node(i,m); //累加权值 ans+=e[i].weight; if(max<e[i].weight) max=e[i].weight; count++; } if (count==n-1) { break; } } return max; } int main() { int n,m; int i,j; while(scanf("%d%d",&n,&m)!=EOF) { // cin>>n>>m; //cin>>m; putIn(n,m); //按权值从小到大排序 qsort(e,m,sizeof(e[0]),cmp); //Kruskal算法生成最小生成树 int ans=Kruskal(m,n); //输出结果 cout<<ans<<endl; } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://128kj.iteye.com/blog/1704752
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1707218
北大POJ2485-Highways【Prim】 解题报告+AC代码
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
北大POJ1789-Truck History【Prim】 解题报告+AC代码
度限制最小生成树代码 摘自POJ1639代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
jungle.in为输入数据,jungle.out为输出数据
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj1789 Truck History prim
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj2516代码最小费用最大流
Algorithm-Java Algorithms + Data Structures = Programs. ——Niklaus Wirth 没日没夜地写程序。看到这几个字我两眼一黑,仿佛这就是我未来的生活。 为了摆脱这种焦虑心理,我逐步...最小生成树(prim,kruskal)(p
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流...