A & M - Jungle Roads HDU - 1301
题意：字母之间的路，求最小生成树
题解：处理好建边以后就是一个Prime
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<stack> #include<cstdlib> #include <vector> #include <set> #include<queue> #include<map> using namespace std; #define ll long long #define llu unsigned long long #define INF 0x3f3f3f3f #define PI acos(-1.0) const int maxn = 50; const ll mod = 1e9+7; const double eps = 1e-8; bool vis[maxn]; int lowc[maxn]; int Prim(int cost[][maxn],int n) { int ans = 0; memset(vis,false,sizeof vis); vis[0] = true; for(int i=1;i<n;i++) lowc[i] = cost[0][i]; for(int i=1;i<n;i++) { int minc = INF; int p = -1; for(int j=0;j<n;j++) { if(!vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } if(minc == INF) return -1; ans += minc; vis[p] = true; for(int j=0;j<n;j++) if(!vis[j] && lowc[j] > cost[p][j]) lowc[j] = cost[p][j]; } return ans; } int main() { int n; while(scanf("%d",&n) && n) { int cost[maxn][maxn]; for(int i=0;i<maxn;i++) { for(int j=0;j<maxn;j++) if(i == j) cost[i][j] = 0; else cost[i][j] = INF; } for(int i=1;i<n;i++) { char a; cin>>a; int num; cin>>num; for(int i=0;i<num;i++) { char ch; int len; cin>>ch>>len; cost[a-‘A‘][ch-‘A‘] = len; cost[ch-‘A‘][a-‘A‘] = len; } } int ans = Prim(cost,n); cout<<ans<<endl; } }
N - 畅通工程再续 HDU - 1875
题意：岛之间造桥，只有长度在10～1000才可以造，问最少的花费，花费是桥的长度*100
题解：INF值的判定，INF是长度小于10或者长度大于1000，其余就是Prime的板子
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<stack> #include<cstdlib> #include <vector> #include <set> #include<queue> #include<map> using namespace std; #define ll long long #define llu unsigned long long #define INF 99999999999.9 #define PI acos(-1.0) const int maxn = 1005; const ll mod = 1e9+7; const double eps = 1e-8; double lowc[maxn]; bool vis[maxn]; double dis(int x1,int y1,int x2,int y2) { double ans = sqrt((double)(x2-x1)*(x2-x1)*1.0 + (y2-y1)*(y2-y1)*1.0); //cout<<ans<<endl; return ans; } bool check(double x) { //cout<<x<<endl; if(x>=10.0 && x<=1000.0) return true; else return false; } double Prime(double cost[][maxn],int n) { double ans = 0; memset(vis,false,sizeof vis); vis[0] = true; for(int i=1;i<n;i++) lowc[i] = cost[0][i]; for(int i=1;i<n;i++) { double minc = INF; int p = -1; for(int j=0;j<n;j++) { if(!vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } if(minc == INF) return -1; ans += minc; vis[p] = true; for(int j=0;j<n;j++) if(!vis[j] && lowc[j] > cost[p][j]) lowc[j] = cost[p][j]; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int x[maxn]; int y[maxn]; double cost[maxn][maxn]; for(int i=0;i<n;i++) scanf("%d %d",&x[i],&y[i]); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i == j) { cost[i][j] = 0; continue; } else if(check(dis(x[i],y[i],x[j],y[j]))) { //cout<<dis(x[i], y[i], x[j], y[j])<<endl; cost[i][j] = dis(x[i], y[i], x[j], y[j]); cost[j][i] = dis(x[i], y[i], x[j], y[j]); } else if(!check(dis(x[i],y[i],x[j],y[j]))) cost[i][j] = INF; } } //cout<<cost[0][1]<<endl; double ans = Prime(cost,n); if(ans == -1) puts("oh!"); else printf("%.1f\n",ans * 100); } }
原文：https://www.cnblogs.com/smallhester/p/10403095.html
