The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

(POJ)倾情奉献系列之MST——最小生成树

POJ 2485 Highways
标准的prim模板题,只是输出的不是最小生成树的总权值,而是MST中的最长边。
#include<iostream>
#include
<cmath>
#include
<cstdio>
using namespace std;
#define MAX 501

int n;
int value[MAX][MAX];
int dis[MAX];
bool flag[MAX];
int maxlen;
void prim ()
{
    
int i,j;
    
int mark;
    memset(flag,
false,sizeof(flag));
    flag[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[1][i];
    }

    
for(i=1;i<n;i++)
    
{
        
int  min=99999;
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&dis[j]<=min)
            
{
                min
=dis[j];
                mark
=j;
            }

        }

        flag[mark]
=true;
        
if(min>maxlen)
            maxlen
=min;
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&value[mark][j]<dis[j])
                dis[j]
=value[mark][j];
        }

    }

}



int main ()
{
    
int testcase;
    
int i,j,k;
    scanf(
"%d",&testcase);
    
for(i=1;i<=testcase;i++)
    
{
        scanf(
"%d",&n);
        
for(j=1;j<=n;j++)
        
{
            
for(k=1;k<=n;k++)
            
{
                scanf(
"%d",&value[j][k]);
            }

        }

    maxlen
=0;
    prim();
    printf(
"%d\n",maxlen);
    }

    
return 0;

}


POJ 1861 Network
刚才又重新看了一遍题,output简直就是个误导,题目要求联通方案中最长的边最小,其实只要输出最小生成树中的最长边就可以了。
除了这个,剩下的问题就是标准的Kruskal模板,输出最长边和具体的生成树方案即可。
#include<iostream>
#include
<algorithm>
using namespace std;
struct element
{
    
int a;
    
int b;
    
int value;
}
edge[15001];

element record[
15001];
int f[1001];
int r[1001];
bool cmp(element a,element b)
{
return a.value<b.value;
}



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}



int main ()
{
    
int num=0;
    
int max=0;
    
int pos=1;
    
int sum=0;
    
int n,m;
    
int i,j;
    scanf ( 
"%d%d"&n, &m );
    

    
for(i=1;i<=m;i++)
    
{
        scanf(
"%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
    }

    
for(i=1;i<=n;i++)
    
{
        f[i]
=i;
        r[i]
=1;
    }

    sort(edge
+1,edge+m+1,cmp);
    
for(i=1;i<=m;i++)
    
{
        
if(Union(edge[i].a,edge[i].b)==1)
        
{
            num
++;
            
if(edge[i].value>max)
                max
=edge[i].value;
            record[pos].a
=edge[i].a;
            record[pos].b
=edge[i].b;
            sum
+=edge[i].value;
            pos
++;
            
            

        }

        
if(num==n-1)
            
break;
    }

    printf(
"%d\n%d\n",max,pos-1);
    
for(i=1;i<=pos-1;i++)
    
{
        printf(
"%d %d\n",record[i].a,record[i].b); 
    }


    
return 0;

}


POJ 2395 Out of Hay
还是求最小生成树的最长边,为什么呢?我想了1分钟,因为kruskal算法是从按照边权从小到大的顺序选择边的,如果形成环路,那么我肯定选择之前选过的那条边,当我不断添加边使得整个图联通的时候,最后一条边一定是任何方案中最小的。感觉这个题目并不是纯粹的最小生成树,但是却暗藏有最小生成树算法的精神。
#include<iostream>
#include
<algorithm>
using namespace std;
struct element
{
    
int a;
    
int b;
    
int value;
}
edge[10005];

int f[2005];
int r[2005];
bool cmp(element a,element b)
{
return a.value<b.value;
}



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}



int main ()
{
    
int num=0;
    
int max=0;
    
int n,m;
    
int i,j;
    
while ( scanf ( "%d%d"&n, &m ) != EOF )
    
{
        num
=0;
        max
=0;

        
for(i=1;i<=m;i++)
        
{
            scanf(
"%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
        }

        
for(i=1;i<=n;i++)
        
{
            f[i]
=i;
            r[i]
=1;
        }

        sort(edge
+1,edge+m+1,cmp);
        
for(i=1;i<=m;i++)
        
{
            
if(Union(edge[i].a,edge[i].b)==1)
            
{
                num
++;
                
if(edge[i].value>max)
                    max
=edge[i].value;

            }

            
if(num==n-1)
                
break;
        }

        printf(
"%d\n",max);
    }

        
return 0;

}



POJ 2377 Bad Cowtractors
最大生成树,由于给出的是边的信息,所以最好用kruskal算法(还能避免重边),注意当图不连通时要输出-1。
另外这个题给我一点额外的启示,判断一个无向图是不是联通可以直接用kruskal呵。扩展一下,如果求任意两点是否连通可以用floyd求传递闭包。
#include<iostream>
#include
<algorithm>
using namespace std;
struct element
{
    
int a;
    
int b;
    
int value;
}
edge[20001];

int f[1001];
int r[1001];
int  cmp(const void *a,const void *b)
{
return -((*(element*)a).value-(*(element*) b).value);
}



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}



int main ()
{
    
int num=0;

    
int sum=0;
    
int n,m;
    
int i,j;
    scanf ( 
"%d%d"&n, &m );
    
        sum
=0;

        
for(i=1;i<=m;i++)
        
{
            scanf(
"%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
        }

        
for(i=1;i<=n;i++)
        
{
            f[i]
=i;
            r[i]
=1;
        }

        qsort(edge
+1,m,sizeof(edge[1]),cmp);
        
for(i=1;i<=m;i++)
        
{
            
if(Union(edge[i].a,edge[i].b)==1)
            
{
                num
++;
                sum
+=edge[i].value;

            }

        
        }

        
if(num==n-1)
        printf(
"%d\n",sum);
        
else
            printf(
"-1\n");


        
return 0;

}



POJ 2421 Constructing Roads
已经修好的路代价为0,此后直接prim就最小代价既可。
呵呵 再贴一个第一次做这个题时候留下的帖子 现在看看挺幼稚的 呵呵,大家不要见笑。
Posted by abilitytao at 2009-01-20 19:34:19 on Problem 2421
离散课上上过 所以就慕名而来了 呵呵
原来课上讲的和实际编起来差距是很大的 从最初的思想到最后的代码实现 我用了2个多小时的时间 参阅过2本书 可见现在的ACM和刚入队时已经不同了 要逐渐适应起来丫
再说说正题吧
我怎么感觉prim 算法和 最短路径算法这么像?呵呵 也许色即是空 空即是色 万物是相互转化的吧 点就是线 线就是点 善哉善哉
看看时间,应该是大二上的寒假做的吧,再次纪念第一道MST。
#include<iostream>
#include
<cstdio>
#include
<cstring>
#include
<cmath>
#include
<algorithm>
using namespace std;


#define N 101
int n;
int map[N][N];
int dis[N];
int visit[N];
int result;

void prim ()
{
    result
=0;
    
int i;
    
int j;
    
int flag;
    
int min=999999999;
    visit[
1]=1;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=map[1][i];
    }

    
for(i=1;i<n;i++)
    
{
        min
=999999999;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<min){min=dis[j],flag=j;}
        }

        visit[flag]
=1;result+=dis[flag];
        
for(j=1;j<=n;j++)
            
if(!visit[j]&&map[flag][j]<dis[j]){dis[j]=map[flag][j];}
    }

}



int main ()
{
    
int testcase;
    
int a,b;
    
int i,j;
    scanf(
"%d",&n);
    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            scanf(
"%d",&map[i][j]);
        }

    }

    scanf(
"%d",&testcase);
    
for(i=1;i<=testcase;i++)
    
{
        scanf(
"%d%d",&a,&b);
        map[a][b]
=0;
        map[b][a]
=0;
    }

    prim();
    printf(
"%d\n",result);
    
return 0;
}




POJ  1679  The Unique MST
问最小生成树是不是唯一,转化成求次最小生成树(注意不连通的情况),当时认为这题不适合新手做,所以直到昨天才A掉这个题。做法是先求出最小生成树,然后枚举删边,求剩余边的最小生成树,求出最小的那个即为次最小生成树。如果次最小生成树权值=原权值,说明MST不唯一,否则唯一输出数值。
#include<cstdio>
#include
<algorithm>
using namespace std;

#define MAX 101
#define INF 100000000
struct node
{

    
int u;
    
int v;
    
int len;
    
bool operator <(node other)
    
{

        
return len<other.len;
    }

}
edge[MAX*MAX];

int f[MAX];
int r[MAX];


int a[MAX];
int p;
int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}
//查找函数,并压缩路径


int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;
    
}
//合并函数,如果属于同一分支则返回0,成功合并返回1

int mincost=0;
int kruskral(int n,int m)
{    
    mincost
=0;
    
int temp=INF;
    p
=0;
    
int i,j;

    
for(i=1;i<=n;i++)
    
{
        f[i]
=i;
        r[i]
=1;
    }

    
for(i=1;i<=m;i++)
    
{
        scanf(
"%d%d%d",&edge[i].u,&edge[i].v,&edge[i].len);
    }

    sort(edge
+1,edge+1+m);
    
int num=0;
    
for(i=1;i<=m;i++)
    
{

        
if(Union(edge[i].u,edge[i].v))
        
{
            num
++;
            p
++;
            a[p]
=i;
            mincost
+=edge[i].len;
        }

        
if(num==n-1)
            
break;
    }

    
int secmincost;
    
for(i=1;i<=n-1;i++)
    
{
        secmincost
=0;
        num
=0;
        
for(j=1;j<=n;j++)
        
{

            f[j]
=j;
            r[j]
=1;
        }

        
for(j=1;j<=m;j++)
        
{
            
if(j==a[i])
                
continue;
            
if(Union(edge[j].u,edge[j].v))
            
{
                num
++;
                secmincost
+=edge[j].len;
            }

            
if(num==n-1)
                
break;
        }

        
if(num==n-1&&secmincost<temp)
            temp
=secmincost;
    }

    
if(temp==mincost)
        
return 0;
    
else 
        
return 1;
}




int main()
{
    
int testcase;
    
int i;
    
int n,m;
    scanf(
"%d",&testcase);
    
for(i=1;i<=testcase;i++)
    
{
        scanf(
"%d%d",&n,&m);
        
if(kruskral(n,m))
            printf(
"%d\n",mincost);
        
else 
            printf(
"Not Unique!\n");
    }

    
return 0;
}

POJ 1751 Highways
还是Highways???难道Highways和最小生成树那么有缘?呵呵
给定边,求出方案。设给定的边的权值是0。可以证明他们一定会被选中
#include<iostream>
#include
<cmath>
#include
<cstdio>
using namespace std;
#define MAX 1001

int record[1001];
int n;
double value[MAX][MAX];
double dis[MAX];
bool flag[MAX];



double lenth(int x,int y,int k,int j)
{
    
double len;
    len
=sqrt(((double)k-(double)x)*((double)k-(double)x)+((double)j-(double)y)*((double)j-(double)y));
    
return len;
}

 
struct dot
{
    
int x;
    
int y;
}
dotset[1001];

dot record2[
1001];
int pos=0;


void prim ()
{
    
int i,j;
    
int mark=0;
    
    memset(flag,
false,sizeof(flag));
    flag[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[1][i];
    }

    
for(i=1;i<=n;i++)
        record[i]
=1;
    
for(i=1;i<n;i++)
    
{
    
        
double min=999999999;
        
for(j=1;j<=n;j++)
        
{
            
            
if(!flag[j]&&dis[j]<=min)
            
{
                
                min
=dis[j];
                mark
=j;
                
            }

        
    
        }

        
if(min!=0)
        
{
            pos
++;
            record2[pos].x
=record[mark];
            record2[pos].y
=mark;
        }

        dis[mark]
=min;flag[mark]=true;
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&value[mark][j]<dis[j])
            
{
                dis[j]
=value[mark][j];
                record[j]
=mark;
            }



        }

    }

}


int main ()

{
    
int m;
    
int i,j;
    scanf(
"%d",&n);
    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d%d",&dotset[i].x,&dotset[i].y);
    }


    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            value[i][j]
=lenth(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
        }

    }

    cin
>>m;
    
for(i=1;i<=m;i++)

    
{
        
int u,v;
        cin
>>u>>v;
        value[u][v]
=0;
        value[v][u]
=0;
    }

    prim();
    
for(i=1;i<=pos;i++)
        printf(
"%d %d\n",record2[i].x,record2[i].y);
    
return 0;

}




POJ 1258 Agri-Net
最经典的MST,建议新手先做此题。
#include<iostream>
#include
<cmath>
#include
<cstdio>
using namespace std;
#define MAX 101

int n;
int value[MAX][MAX];
int dis[MAX];
bool flag[MAX];
int result;

void prim ()
{
    
int i,j;
    
int mark;
    result
=0;
    memset(flag,
false,sizeof(flag));
    flag[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[1][i];
    }

    
for(i=1;i<n;i++)
    
{
        
int min=999999999;
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&dis[j]<=min)
            
{
                min
=dis[j];
                mark
=j;
            }

        }

        flag[mark]
=true;result+=dis[mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&value[mark][j]<dis[j])
                dis[j]
=value[mark][j];
        }

    }

}


int main ()

{
    
int i,j;
    
while(scanf("%d",&n)!=EOF)
    
{
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                scanf(
"%d",&value[i][j]);
            }

        }

        prim();
        printf(
"%d\n",result);
        
    }

    
return 0;
}


POJ 1251 Jungle Roads
输入的时候有些字母,构图的时候要转换一下。
#include<iostream>
#include
<algorithm>
using namespace std;
struct element
{
    
int a;
    
int b;
    
int value;
}
edge[100];

int f[30];
int r[30];
int cmp(const void *a,const void *b)
{
return (*(element*)a).value-(*(element*)b).value;
}



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;

}


    
int num=0;
    
int sum=0;

int main ()
{
    
int pos;
    
int n,m,k;
    
int i,j;
    
char temp[10];
    
while (cin>>n)
    
{
        pos
=0;
        num
=0;
        sum
=0;
        
if(n==0)
            
break;
        
for(i=1;i<n;i++)
        
{
            cin
>>temp;
            cin
>>m;
            
for(j=1;j<=m;j++)
            
{
                pos
++;
                cin
>>temp;
                cin
>>k;
                edge[pos].a
=i;
                edge[pos].b
=temp[0]-64;
                edge[pos].value
=k;
            }

        }




        


        
for(i=1;i<=n;i++)
        
{
            f[i]
=i;
            r[i]
=1;
        }

        qsort(edge
+1,pos,sizeof(edge[1]),cmp);
        
for(i=1;i<=pos;i++)
        
{
            
if(Union(edge[i].a,edge[i].b)==1)
            
{
                num
++;
                sum
+=edge[i].value;

            }

            
if(num==n-1)
                
break;
        }

        printf(
"%d\n",sum);
    }

        
return 0;

}



POJ 3625 Building Roads
非常朴素的prim ^_^
#include<iostream>
#include
<cmath>
#include
<cstdio>
using namespace std;
#define MAX 1001


int n;
double value[MAX][MAX];
double dis[MAX];
bool flag[MAX];
double result;


double lenth(int x,int y,int k,int j)
{
    
double len;
    len
=sqrt(((double)k-(double)x)*((double)k-(double)x)+((double)j-(double)y)*((double)j-(double)y));
    
return len;
}


struct dot
{
    
int x;
    
int y;
}
dotset[1001];



void prim ()
{
    
int i,j;
    
int mark;
    result
=0;
    memset(flag,
false,sizeof(flag));
    flag[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=value[1][i];
    }

    
for(i=1;i<n;i++)
    
{
        
double min=999999999;
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&dis[j]<=min)
            
{
                min
=dis[j];
                mark
=j;
            }

        }

        dis[mark]
=min;flag[mark]=true;result+=dis[mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!flag[j]&&value[mark][j]<dis[j])
                dis[j]
=value[mark][j];
        }

    }

}


int main ()

{
    
int m;
    
int i,j;
    cin
>>n>>m;
    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d%d",&dotset[i].x,&dotset[i].y);
    }


    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            value[i][j]
=lenth(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
        }

    }

        
for(i=1;i<=m;i++)

    
{
        
int u,v;
        cin
>>u>>v;
        value[u][v]
=0;
        value[v][u]
=0;
    }

    prim();
    printf(
"%.2f\n",result);
    
return 0;

}



POJ 1789 Truck History
题目里没数字,但是很容易知道每个车只有一个来源,说明没有环,所以一定是一个树,quality要最大,说明分母最小,故:最小生成树
#include<iostream>
#include
<cstdio>
#include
<cstring>
#include
<cmath>
#include
<algorithm>
using namespace std;

struct node
{
    
char name[7];
}
;

node a[
2001];

int camp(int i,int j)
{
    
int num=0;
    
int k;
    
for(k=0;k<7;k++)
    
{
        
if(a[i].name[k]!=a[j].name[k])
            num
++;
    }

    
return num;
}





#define N 2001
int n;
int map[N][N];
int dis[N];
int visit[N];
int result;

void prim ()
{
    memset(visit,
0,sizeof(visit));
    result
=0;
    
int i;
    
int j;
    
int flag;
    
int min=999999999;
    visit[
1]=1;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=map[1][i];
    }

    
for(i=1;i<n;i++)
    
{
        min
=999999999;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<min){min=dis[j],flag=j;}
        }

        visit[flag]
=1;result+=dis[flag];
        
for(j=1;j<=n;j++)
            
if(!visit[j]&&map[flag][j]<dis[j]){dis[j]=map[flag][j];}
    }

}



int main ()
{
    
int i,j,k;

    
while(cin>>n)

    
{
        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
            cin
>>a[i].name;
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                map[i][j]
=camp(i,j);
            }

        }

        prim();
        printf(
"The highest possible quality is 1/%d.\n",result);
    }


        
    
}



北京赛区的经典题目,最优比率生成树,传说中楼哥1A的G题。。。
什么是最优比率生成树呢?说白了很简单,已知一个完全图,每条边有两个参数(b和c),求一棵生成树,使(∑xi×ci)/(∑xi×bi)最小,其中xi当第i条边包含在生成树中时为1,否则为0。其实也可以看成一个0,1的整数规划问题。
我的做法是LRJ《算法艺术与信息学竞赛》中介绍的二分,详细的证明请看书,这里只是简单的介绍一下核心的方法:
1.首先找出这个比率的最小值和最大值 front,rear
2.求mid=(front+reat)/2
3.用 ci-mid*bi 重新构图
4.求出新图的最小生成树权值之和
5.如果权值等于0,mid就是我们要求的比率,结束。如果权值>0,front=mid,如果权值<0,rear=mid,跳回2继续循环。


不过这个算法对精度的要求比较高,我用0.001就错了,0.00001超时,只有0.0001AC,汗
另外时间效率也不高,3000MS的题,耗去了2500MS,看来这个算法还是有待改进。
下面是我的代码:

#include<iostream>
#include
<algorithm>
#include
<cstring>
#include
<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{

    
double x,y,h;
}
dot[MAX];


inline 
double dis(double x1,double y1,double x2,double y2)
{

    
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}



double graph[MAX][MAX];

inline 
void creat(int n,double l)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{

        
for(j=1;j<=n;j++)
        
{

            graph[i][j]
=fabs(dot[i].h-dot[j].h)-l*dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
        }

    }

}


inline 
double prim(double graph[MAX][MAX],int n)
{
    
bool visit[MAX]={0};
    
int mark;
    
double dis[MAX];
    
double ans=0;
    
int i,j;
    visit[
1]=true;
    
for(i=1;i<=n;i++)
        dis[i]
=graph[1][i];
    
for(i=1;i<n;i++)
    
{

        
int minnum=INF;
        
for(j=1;j<=n;j++)
        
{

            
if(!visit[j]&&dis[j]<=minnum)
            
{
                minnum
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        ans
+=dis[mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&graph[mark][j]<dis[j])
                dis[j]
=graph[mark][j];
        }


    }

    
return ans;
}



int main()
{

    
int i,j;
    
int n;
    
double res;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
        }

        
double front,rear;
        front
=0;
        rear
=100;//这个地方有点悬。。。
        double mid;
        
double pre=0.0;
        
while(front<=rear)
        
{

            mid
=(front+rear)/2;
            creat(n,mid);
            res
=prim(graph,n);
            
if(fabs(res-pre)<=0.0005)
                
break;
            
else if(res>0.0005)
                front
=mid;
            
else
                rear
=mid;
        }

        printf(
"%.3lf\n",mid);
    }

    
return 0;
}

———————————————————————传说中的分割线————————————————————————————
终于在今天下午 使用迭代法将此题优化到282MS,呵呵 这名字让我又想起了数值分析。。。
#include<iostream>
#include
<algorithm>
#include
<cstring>
#include
<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
    
double x,y,h;
}
dot[MAX];


inline 
double dis(double x1,double y1,double x2,double y2)
{

    
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}



double graph[MAX][MAX];
double c[MAX][MAX];
double s[MAX][MAX];

inline 
void creatcs(int n)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{
        
for(j=1;j<=n;j++)
        
{
            c[i][j]
=fabs(dot[i].h-dot[j].h);
            s[i][j]
=dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
        }

    }

}



inline 
void creat(int n,double l)
{
    
int i,j;
    
for(i=1;i<=n;i++)
    
{

        
for(j=1;j<=n;j++)
        
{

            graph[i][j]
=c[i][j]-l*s[i][j];
        }

    }

}

double sumc;
double sums;

inline 
void prim(double graph[MAX][MAX],int n)
{
    sumc
=0;
    sums
=0;
    
bool visit[MAX]={0};
    
int mark;
    
int pre[MAX];
    
double dis[MAX];
    
int i,j;
    visit[
1]=true;
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=graph[1][i];
        pre[i]
=1;
    }

    
for(i=1;i<n;i++)
    
{

        
int minnum=INF;
        
for(j=1;j<=n;j++)
        
{

            
if(!visit[j]&&dis[j]<=minnum)
            
{
                minnum
=dis[j];
                mark
=j;
            }

        }

        visit[mark]
=true;
        sumc
+=c[pre[mark]][mark];
        sums
+=s[pre[mark]][mark];
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&graph[mark][j]<dis[j])
            
{
                dis[j]
=graph[mark][j];
                pre[j]
=mark;
            }

        }


    }

}



int main()
{

    
int i,j;
    
int n;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
        }

        creatcs(n);
        
double prerate=30.0;
        
double rate=30.0;
        
while(true)
        
{
            creat(n,rate);
            prim(graph,n);
            rate
=sumc/sums;
            
if(fabs(rate-prerate)<0.001)
                
break;
            prerate
=rate;
        }

        printf(
"%.3lf\n",rate);
    }

    
return 0;
}


POJ 1287 Networking.....Orz
此题再次证明了我的预感是正确的。。。Network...
#include<iostream>
#include
<algorithm>
using namespace std;
struct element
{
    
int a;
    
int b;
    
int value;
}
edge[15001];

int f[1001];
int r[1001];
bool cmp(element a,element b)
{
    
return a.value<b.value;
}



int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}



int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
    }

    
return 1;
    
}



int main ()
{
    
int num=0;
    
int sum=0;
    
int n,m;
    
int i,j;
    
while(scanf ( "%d"&n))
    
{
        
if(n==0)
            
break;
        scanf(
"%d",&m);
        sum
=0;
        num
=0;
        
for(i=1;i<=m;i++)
        
{
            scanf(
"%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
        }

        
for(i=1;i<=n;i++)
        
{
            f[i]
=i;
            r[i]
=1;
        }

        sort(edge
+1,edge+m+1,cmp);
        
for(i=1;i<=m;i++)
        
{
            
if(Union(edge[i].a,edge[i].b)==1)
            
{
                num
++;
                sum
+=edge[i].value;
            }

            
if(num==n-1)
                
break;
        }

        printf(
"%d\n",sum);
    }

    
return 0;
    
}


                                                                                                                                                                                                          

posted on 2009-09-05 23:30 abilitytao 阅读(3091) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理