poj2485 kruskal与prim

Kruskal:


#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

//#define debug

#if defined debug

#define CDBG(format,...) printf("File: "__FILE__", Line: %05d: "format"\n", __LINE__, ##__VA_ARGS__)

int open_file(){

    FILE *fp ;

    if((fp = freopen("input3.txt","r",stdin)) == NULL){

        CDBG("error in freopen");

        return -;

    }

    CDBG("success in freopen");

    return ;

}

#else

#define CDBG(format,...) do{}while(0)

#endif

#define N 510

int n,k,pre[N];

struct point

{

    int x;

    int y;

    int len;

}p[N*N];

/*int cmp(const void * x,const void * y)

{

    return ((point*)x)->len>((point*)y)->len?1:-1;

}*/

void swap(point &x,point &y)

{

   point temp;

   temp = x;

   x = y;

   y = temp; // 从指针改成数组就行了

}

int choose_pivot(int i,int j )

{

   return((i+j) /);

}

void quicksort(point list[],int m,int n)

{

   int key,i,j,k;

   if( m < n)

   {

      k = choose_pivot(m,n);

　　　 if(m != k)
      swap(list[m],list[k]);

      key = list[m].len;

      i = m+;

      j = n;

      while(i <= j)

      {

         while((i <= n) && (list[i].len <= key)) i++;

         while((j >= m) && (list[j].len > key)) j--;

         if( i < j)

                swap(list[i],list[j]);

      }

     // 交换两个元素的位置

　　　 if(m != j)
      swap(list[m],list[j]);

     // 递归地对较小的数据序列进行排序

      quicksort(list,m,j-);

      quicksort(list,j+,n);

  }

}

int cmp(point x,point y)

{

    return x.len<y.len;

}

int find(int x)

{

    while(x!=pre[x]) x=pre[x];

    return x;

}

void kruskal()

{

    int i,mix,a,b;

    mix=;

    //sort(p,p+k,cmp);

    for(i = ; i < k ;i++)

    CDBG("%d ",p[i].len);

    quicksort(p,,k-);  //跟 sort 结果完全不一样

    for(i = ; i < k ;i++)

    CDBG("%d ",p[i].len);

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

        pre[i]=i;// 可以初始化为 -1 等值

    for(i=;i<k;i++)

    {

        a=find(p[i].x);

        b=find(p[i].y);

        if(a!=b)

        {

            if(p[i].len>mix)

                mix=p[i].len;

            pre[b]=a;

        }

    }

    cout<<mix<<endl;

}

void input()

{

    scanf("%d",&n);

    k=;

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

        {

            scanf("%d",&p[k].len);

            if(i != j && p[k].len != ){

                p[k].x=i;

                p[k].y=j;

                k++;  //过滤掉ii 点

            }

        }

}

int main()

{

    int T;

    #ifdef debug

    if(open_file() != )

        return -;

    #endif

    scanf("%d",&T);

    while(T--)

    {

        input();

        kruskal();

    }

    return ;

}

 void quicksort(int left, int right){

    if (left > right)

        return;

    int l = left;

    int r = right+;

    path v, temp;

    v = ipath[left];

    while (){

        while (l < r && ipath[--r].len >= v.len);

        while (l < r && ipath[++l].len <= v.len);

        if (l >= r) break;

        temp = ipath[l];

        ipath[l] = ipath[r];

        ipath[r] = temp;

    }

    ipath[left] = ipath[l];

    ipath[l] = v;

    quicksort(left, l - );

    quicksort(l + , right);

}

Prime:

参考: http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
/*
题目意思就是求最小生成树，并返回最长edge
求最小生成树一般有两种方法，prim算法 O[N^2]和kruskal算法 O[ElogE]，在这里我推荐使用prim算法，因为此题不是稀疏图，kruskal算法耗时较多（但也不会超时）
 prim算法的基本思想
1.清空生成树，任取一个顶点加入生成树
2.在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树
3.重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树
Prime()
{
 //开始默认把1加入点集里
 for(2~m)
 dist[i]=map[1][i];
 for(2~m)
 {
 //找跟相连的最短边
 for(2~m)
 {
 if(!visit[j] && dist[j]<inf) 
   index="j";
 }=""
 visit[index]="1";

 根据知道的点更新cost，这里方法有点像dijkstra，注意！！！=""
 for(2~m)="" {="" if(!visit[j]="" &&="" cost[j]="">map[index][j])
 cost[j]=map[index][j];
 } 
 } 
}
*/

#include<stdio.h>

#include<string.h>

#define debug

#if defined debug

#define CDBG(format,...) printf("File:"__FILE__", Line:%05d: "format"\n", __LINE__, ##__VA_ARGS__)

#else

#define CDBG(format,...) do{}while(0)

#endif

#define N 511

// n -> [3,500]

#define inf 0x3f3f3f3f

//distance -> [1,65536]

int villages[N][N];

int visited[N];

int lowcost[N];

int open_file(){

    FILE *fp ;

    if((fp = freopen("input3.txt","r",stdin)) == NULL){

        CDBG("error in freopen");

        return -;

    }

    CDBG("success in freopen");

    return ;

}

void reset_visited(int n){

    int i = ;

    for( i = ; i<= n; i++){ visited[i] = ; lowcost[i] = ;}

}

//下面2个方法都可以

int prim(int start_p,int n){

    int i,j,pos,min = ,result = ;

    reset_visited(n);

    //start at point 1

    visited[start_p] = ; pos = start_p;

    //set low array from point 1 to other point

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

        if(i != pos) {

            lowcost[i] = villages[pos][i];

            CDBG("set lowcost[%d] = %d",i,lowcost[i]);

        }

    //check n-1 times again ， 每次添加一个点到 最小树

    for(i = ; i < n; i++){ // 使用 while循环代替 for 容易有一些问题

        //find min distance 寻找下一个最短距离

        min = inf;

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

            if(visited[j] ==  && lowcost[j] < min)

                {

                    min = lowcost[j];//从未访问的点找到 最短距离的 点
　　　　　　　　　　　 pos = j;

                    CDBG("min = %d pos = %d j = %d",min,pos,j);

                }

        }

        CDBG("min = %d pos = %d ",min,pos);

        //add min distance;

        if(result < min)

        result = min;  // 找最小树的最长距离

        visited[pos] = ;

        //update  更新当前最小的点 到 所有未访问过的点 的距离

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

            if(visited[j] ==  && lowcost[j] > villages[pos][j])

            {

                lowcost[j] = villages[pos][j];

                CDBG("update lowcost[%d] = %d",j ,lowcost[j]);

            }

        }

    }

    return result;

}

int prim(int n)

{

    int u = ;

    int i,j,k,start,min,max;

    //memset(vis,0,sizeof(vis));

    reset_visited(n);

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

        if(i!=u)

            lowcost[i]=villages[][i];

    visited[]=true;

    k=;

    min=;max=;

    for(i=;i<n;i++)        //n-1条边

   {

        min=inf;

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

        if(lowcost[j]<min&&!visited[j])

        {

            min=lowcost[j];

            k=j;

        }

        if(min>max)

        max=min;

        visited[k]=true;

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

       if(lowcost[j]>villages[k][j]&&!visited[j])

        {

            lowcost[j]=villages[k][j];

        }

    }

    return max;

    //cout<<max<<endl;

}

void read_villages(int n){

    for(int i = ; i <= n; i++)

        for(int j = ; j <= n; j++)

            {

                villages[i][j] = ;

                scanf("%d",&villages[i][j]);

            }

}

void check_villages(int n){

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

        for(int j = ; j <= n; j++)

            printf("%d ",villages[i][j]);  // 应该是这个导致了 Output Limit Exceeded

    printf("\n");

    }

}

int main(){

    int T,n;

#ifdef debug

    if(open_file() != )

        return -;

#endif

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        read_villages(n);

        //check_villages(n);

        int ans=;

        ans = prim(,n); // 可以从任意一点开始

        //ans = prim(n);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

poj2485 kruskal与prim

最新文章

热门文章