HDU1102 Constructing Roads —

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1102

题解：

纯最小生成树，只是有些边已经确定了要加入生成树中，特殊处理一下这些边就可以了。

kruskal算法：

由于有些边已经确定，所以在调用kruskal()之前，就把这条边的两个顶点放在一个集合就可以了。

 #include<cstdio>//hdu1102 最小生成树 kruskal

 #include<algorithm>

 #define N 110

 using namespace std;

 struct node

 {

     int x,y,dis;

 }edge[N*N];

 int fa[N];

 bool cmp(node a, node b)

 {

     return a.dis<=b.dis;

 }

 int find(int x)

 {

     return fa[x]==x?x:find(fa[x]);

 }

 bool un(int x, int y)

 {

     x = find(x);

     y = find(y);

     if(x!=y)

     {

         fa[x] = y;

         return true;

     }

     return false;

 }

 int kruskal(int n,int sum)

 {

     int len = ,x,y,i;

     sort(edge,edge+sum,cmp);

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

     {

         x = edge[i].x;

         y = edge[i].y;

         if(un(x,y))

             len += edge[i].dis;

     }

     return len;

 }

 int main()

 {

     int n,m,i,j,x,y,dis,sum;

     while(scanf("%d",&n)!=EOF)

     {

         sum = ;

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

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

         {

             scanf("%d",&dis);

             if(i>=j) continue;

             edge[sum].x = i;

             edge[sum].y = j;

             edge[sum].dis = dis;

             sum++;

         }

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

             fa[i] = i;

         scanf("%d",&m);

         for(i = ; i<m; i++)//先处理以确定的边

         {

             scanf("%d%d",&x,&y);

             un(x,y);

         }

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

     }

    return ;

 }

prim算法：

在prim算法中就不能像kruskal算法那样先预处理了，而要在算法中运行。由于prim算法在每次松弛时总是找最小的点，题目中两条村庄的距离是非负数，那么我们可以把确定要加入生成树的边的两个顶点的距离设为-1，这样就能确保他们都加入到生成树中了。

注意：赋值或修改邻接矩阵的无向图时，正反两条边都要操作。

 #include<cstdio>//hdu1102 最小生成树 prim

 #include<algorithm>

 #define N 110

 #define INF  0x7fffffff

 using namespace std;

 int arc[N][N];

 int prim(int n)

 {

     int low[N];

     int k,i,j,min,len = ;

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

     {

         low[i] = arc[][i];

     }

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

     {

         min = INF;

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

         {

             if(low[j]!= && low[j]<min)

             {

                 min = low[j];

                 k = j;

             }

         }

         if(low[k]>)

             len += low[k];

         low[k] = ;

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

         {

             if(low[j]!= && arc[k][j]<low[j])

             {

                 low[j] = arc[k][j];

             }

         }

     }

     return len;

 }

 int main()

 {

     int n,q,u,v,i,j;

     while(scanf("%d",&n)!=EOF)

     {

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

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

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

         scanf("%d",&q);

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

         {

             scanf("%d%d",&u,&v);

             arc[v][u] = arc[u][v] = -;

             //正反向都要置为-1， 因为在松弛的过程中，两个方向都有可能

         }

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

     }

    return ;

 }

巴特西

HDU1102 Constructing Roads —— 最小生成树

最新文章

热门文章