hdu 1162 && hdu 1875-白红宇

hdu 1162 && hdu 1875

阅读量：5327 次

发布时间：2019-06-14

本文共 3432 字，大约阅读时间需要 11 分钟。

这来到题目差不多，因为几乎是每条边都用到，所以用prim算法应该会比较好，从运行的效率来看也十分明显

hdu1875 则对边做了一定的限制，只需要的加边的时候判断一下就好了

hdu 1162

#include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #define MAXN 101 #define MAXINT 99999999 using namespace std; int n,s[MAXN]; double dis[MAXN],map[MAXN][MAXN]; struct  node{
     double x,y; }node1[MAXN]; double distance(int i,int j) {
     return (node1[i].x-node1[j].x)*(node1[i].x-node1[j].x)+(node1[i].y-node1[j].y)*(node1[i].y-node1[j].y); } void prim() {
     for(int i=1;i<=n;i++)         dis[i]=map[1][i];     dis[1]=0;     memset(s,0,sizeof(s));     s[1]=1; double ans=0; for(int i=1;i

hdu 1875 pime

#include 
      
        #include 
       
         #include 
        
          static const int V = 100; struct Pos {
     int x; int y; int operator- (const Pos& rhs) const     {
     return (x - rhs.x) * (x - rhs.x) + (y - rhs.y) * (y - rhs.y);     } }; Pos point[V]; int map[V][V]; double Prim(int n) {
     int* dist =map[0];          int c = n; double amount = 0.0; while (--c)     {
     int add, min = INT_MAX; for (int i = 1; i < n; ++i)               {
     if (dist[i] != 0 && dist[i] < min)             {
                     add = i;                 min = dist[i];             }         } if (min == INT_MAX)           return -1;         amount += sqrt((double)min);         dist[add] = 0;                       for (int i = 1; i < n; ++i)                {
     if (map[add][i] < dist[i])                 dist[i] = map[add][i];         }     } return amount; } int main() {
     int t;     scanf ("%d", &t); while (t--)     {
     int c;         scanf ("%d", &c); for (int i = 0; i < c; ++i)         {
                 scanf ("%d %d", &point[i].x, &point[i].y);             map[i][i] = 0; for (int j = 0; j < i; ++j)             {
     int d = point[i] -point[j]; if (d < 10 * 10 || d > 1000 * 1000)                     d = INT_MAX;                 map[i][j] = map[j][i] = d;             }         } double amount = Prim(c); if (amount == -1)             printf ("oh!\n"); else             printf ("%.1lf\n", amount * 100);     } return 0; }

hdu 1875 Kruskal算法

#include
      
        #include
       
         #include
        
          #include
         
           #define MAXN 101 #define MAXINT 99999999 using namespace std; int n,m,num; double ans; int f[MAXN]; struct edge{
     int u,v,w;     edge(int x=0,int  y=0,int z=0):u(x),v(y),w(z){}; }e[MAXN*MAXN]; struct node{
     int x,y; }node1[MAXN]; int find(int x) {
     if(x==f[x]) return x;     f[x]=find(f[x]); return f[x]; } void Union(int x,int y,int z) {
     int a=find(x); int b=find(y);    if(a==b) return ;     f[b]=a;     ans+=(double)sqrt((double)z); } int distance(int i,int j) {
     return (node1[i].x-node1[j].x)*(node1[i].x-node1[j].x)+(node1[i].y-node1[j].y)*(node1[i].y-node1[j].y); } bool cmp(edge a,edge b) {
     return a.w
          
           1000000||tmp<100) continue;                 e[num++]=edge(i,j,tmp);             }         sort(e,e+num,cmp);         ans=0; for(int i=0;i<=num;i++)             Union(e[i].u,e[i].v,e[i].w); int cou=0; for(int i=1;i<=n;i++) if(find(i)==i)                 cou++; if(cou>1) printf("oh!\n"); else printf("%.1f\n",ans*100);     } return 0; }