MST

模板kruskalprim A: POJ 2377 Bad CowtractorsB: POJ 1287 NetworkingC: HDU 1875 畅通工程再续D: POJ 1258 Agri-NetE: POJ 2031 Building a Space StationF: CodeForces 1108F MST Unification

模板

kruskal

#include<bits/stdc++.h> using namespace std; struct Edge { int x,y,len; } edge[500010]; int fa[100010],n,m,ans=0; bool operator <(Edge a,Edge b) { return a.len<b.len; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { cin>>n>>m; for(int i=1; i<=m; i++) cin>>edge[i].x>>edge[i].y>>edge[i].len; //按照边权排序 sort(edge+1,edge+m+1); //初始化并查集 for(int i=1; i<=n; i++) fa[i]=i; //求最小生成树 for(int i=1; i<=m; i++) { int x=find(edge[i].x); int y=find(edge[i].y); if(x==y) continue; fa[x]=y; ans+=edge[i].len; } cout<<ans<<endl; return 0; }

prim

#include<bits/stdc++.h> using namespace std; // T:确定属于最小生成树的节点集合 // S:剩余节点集合 int a[3010][3010]; int d[3010];// d[x], x表示x加入T时选出的最小边的权值 bool vis[3010];// vis[x]==true表示该节点已经加入了T集合 int n,m,ans=0; void prim() { memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); d[1]=0; for(int i=1; i<n; i++)//循环n-1次 每次找出一个点加入T { int x=0; for(int j=1; j<=n; j++)//遍历所有节点 { //当前d[]数组存储的是各个节点距离生成树的最小权值 if(!vis[j] && (x==0 || d[j]<d[x])) //!vis[j]表示该节点尚未加入T集合 x=j; //选出距离生成树最近的节点 } vis[x]=1;//将该节点加入到生成树中(T集合) for(int y=1; y<=n; y++) { if(!vis[y])//新加了一个点，就维护该点到还没有加入T集合的点的距离 d[y]=min(d[y],a[x][y]);//取距离生成树 } } } int main() { cin>>n>>m; //构建邻接矩阵 memset(a,0x3f,sizeof(a)); for(int i=1; i<=n; i++) a[i][i]=0; for(int i=1; i<=m; i++) { int x,y,z; cin>>x>>y>>z; a[x][y]=a[y][x]=min(a[x][y],z); } //求最小生成树 prim(); for(int i=2; i<=n; i++) ans+=d[i]; cout<<ans<<endl; return 0; } /* 输入 输出15 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 */

题目链接 : 图zcib

A: POJ 2377 Bad Cowtractors

传送门：http://poj.org/problem?id=2377

思路：模板题，最大生成树，边权排序的时候大的放到前面，直接套kruskal模板就能过。

AC代码

#include<iostream> #include<algorithm> using namespace std; struct cc { int x,y,r; } edge[20005]; int fa[1005]; int cmp(cc a,cc b) { return a.r>b.r; } int n,m; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { cin>>n>>m; for(int i=0; i<m; i++) { cin>>edge[i].x>>edge[i].y>>edge[i].r; } sort(edge,edge+m,cmp); for(int i=0; i<=n; i++) fa[i]=i; int ans=0; for(int i=0; i<m; i++) { int x=find(edge[i].x); int y=find(edge[i].y); if(x==y) continue; fa[x]=y; ans+=edge[i].r; } int flag=0; for(int i=1; i<=n; i++) { if(i==find(fa[i])) flag++; } if(flag>1) cout<<-1<<endl; else cout<<ans<<endl; return 0; }

B: POJ 1287 Networking

传送门：http://poj.org/problem?id=1287

思路：这也是个kruskal模板题，套模板就完事了

AC代码：

#include<iostream> #include<algorithm> using namespace std; struct cc { int x,y,r; } ; int fa[1005]; int cmp(cc a,cc b) { return a.r<b.r; } int n,m; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { while(cin>>n,n) { cin>>m; cc edge[20005]; for(int i=0; i<m; i++) { cin>>edge[i].x>>edge[i].y>>edge[i].r; } sort(edge,edge+m,cmp); for(int i=0; i<=n; i++) fa[i]=i; int ans=0; for(int i=0; i<m; i++) { int x=find(edge[i].x); int y=find(edge[i].y); if(x==y) continue; fa[x]=y; ans+=edge[i].r; } cout<<ans<<endl; } return 0; }

C: HDU 1875 畅通工程再续

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1875

思路:修改下prim的板子 当边权在 [10,1000] 这个范围内时再加点

AC代码：

#include<bits/stdc++.h> using namespace std; const int INF = 1000007; double a[105][105]; double d[105]; bool v[105]; struct point { int x,y; } cc[105]; double dis(point a,point b) { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int n; void prim() { for(int i=0; i<=n; i++) d[i]=INF; memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) if(a[x][y]>=10 && a[x][y]<=1000) d[y]=min(d[y],a[x][y]); } } int main() { int t; cin>>t; while(t--) { cin>>n; for(int i=1; i<=n; i++) cin>>cc[i].x>>cc[i].y; for(int i=1; i<=n; i++) { a[i][i]=0; for(int j=i+1; j<=n; j++) { a[i][j]=a[j][i]=dis(cc[i],cc[j]) ; } } prim(); int flag=0; double ans=0; for(int i=2; i<=n; i++) { if(d[i]==INF) { flag=1; break; } ans+=d[i]; } if(!flag) printf("%.1lf\n",ans*100.0); else cout<<"oh!"<<endl; } return 0; }

D: POJ 1258 Agri-Net

传送门：http://poj.org/problem?id=1258

思路：注意有多组输入，然后还是套prim模板

AC代码

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int INF = 0x3f3f3f3f; int a[105][105]; int d[105]; int v[105]; void prim(int n) { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],a[x][y]); } } int main() { int n; while(cin>>n) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cin>>a[i][j]; } } prim(n); int ans=0; for(int i=2; i<=n; i++) ans+=d[i]; cout<<ans<<endl ; } return 0; }

E: POJ 2031 Building a Space Station

传送门：http://poj.org/problem?id=2031

思路：题目给出的是空间直角坐标系中每个点的坐标，遍历每个点，用二维数组储存两点之间的距离s，如果 s<=r1+r2则两点相交或者相切，这种情况两点距离储存为0，否则就储存为s-r1-r2; 两层for将二维数组填满后，就可以套prim模板了。

注意：POJ里面用 G++ 提交的时候 double 类型要用 %f 输出，不然判定为Wa,用 C++ 提交就可以用 %lf 了

AC代码：

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int INF = 1000000007; struct zb { double x,y,z,r; } point[105]; double dis(zb a,zb b) { double x=pow(a.x-b.x,2); double y=pow(a.y-b.y,2); double z=pow(a.z-b.z,2); double t=sqrt(x+y+z); if(t<=a.r+b.r) return 0; return t-a.r-b.r; } int n; double a[105][105]; double d[105]; int v[105]; void prim() { memset(v,0,sizeof(v)); for(int i=0; i<=n; i++) d[i]=INF; d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) if(!v[j] && (x==0 || d[j]<d[x])) x=j; v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],a[x][y]); } } int main() { while(cin>>n,n) { for(int i=1; i<=n; i++) cin>>point[i].x>>point[i].y>>point[i].z>>point[i].r; for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { a[i][j]=a[j][i]=dis(point[i],point[j]); } } prim(); double ans=0; for(int i=2; i<=n; i++) ans+=d[i]; printf("%.3f\n",ans); } return 0; }

F: CodeForces 1108F MST Unification

传送门：http://codeforces.com/problemset/problem/1108/F

思路：这道题的大意就是改变多少个边权使得这个图仅有唯一一个最小生成树。我们先按常规做法吧边按照权值从小到大排序，先用一次find记录有多少个权值相同的边并且他们可以相连（即用并查集find()寻找父根节点之后两根节点不同），再用一次并查集将父根节点不同的点相连，相连后剩余的就是需要更改权值的边，统计最后有多少边需要更改即可。

AC代码：

#include<bits/stdc++.h> using namespace std; const int N = 200005; int fa[N]; int n,m; struct cc { int x,y,r; } edge[N]; int cmp(cc a,cc b) { return a.r<b.r; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int main() { cin>>n>>m; for(int i=0; i<m; i++) cin>>edge[i].x>>edge[i].y>>edge[i].r; sort(edge,edge+m,cmp); for(int i=0; i<=n; i++) fa[i]=i; int num=0; for(int i=0; i<m;) { int j=i; while(edge[i].r==edge[j].r) j++; //记录有多少个权值相同的边 for(int k=i; k<j; k++) { int x=find(edge[k].x); int y=find(edge[k].y); if(x!=y) num++;//如果两个点的父根节点不同 } for(int k=i; k<j; k++) { int x=find(edge[k].x); int y=find(edge[k].y); if(x!=y) //把父根节点不同的点连接在一块 ，num-- { fa[x]=y; num--; } } i=j; } cout<<num<<endl; return 0; }