NYOJ118 求次小生成树

题目大意：中文题。

算法思路：求次小生成树。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 505
int t,n,m,a,b,c,sum,e,MAX,pr;
int maps[MAXN][MAXN],dist[MAXN],p[MAXN][MAXN],pre[MAXN];

bool visited[MAXN],used[MAXN][MAXN];
void prim(int s)
{
    int MIN,node;
    memset(visited,false,sizeof(visited));
    memset(used,false,sizeof(used));
    memset(p,0,sizeof(p));
    memset(dist,0x3f,sizeof(dist));
    memset(pre,0,sizeof(pre));
    for(int i=1; i<=n; i++)
    {
        used[i][i]=true;
        //dist[i]=maps[1][i];
       // pre[i]=1;
    }
    dist[1]=0;
    for(int i=1; i<=n; i++)
    {
        MIN=INF,node=-1;
        for(int j=1; j<=n; j++)
        {
            if(!visited[j]&&MIN>dist[j])
            {
                MIN=dist[j];
                node=j;
            }
        }
        if(node==-1)
            return;
        visited[node]=true;
        sum+=dist[node];

        pr=pre[node];
        p[pr][node]=p[node][pr]=dist[node];
        maps[pr][node]=maps[node][pr]=0;

        for(int j=1;j<=n;j++)
        {
            if(visited[j]&&j!=node)
                p[j][node]=p[node][j]=max(p[j][pr],dist[node]);
        }



        for(int j=1; j<=n; j++)
        {
              if(!visited[j]&&maps[node][j]&&dist[j]>maps[node][j])
                {
                    pre[j]=node;
                    dist[j]=maps[node][j];
                }

        }

    }

}
int main()
{

    scanf("%d",&t);
    while(t--)
    {
        memset(maps,0,sizeof(maps));
        MAX=-INF;
        sum=0;
        scanf("%d%d",&n,&m);

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            maps[a][b]=maps[b][a]=c;
        }
        prim(1);
        int res=INF;

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

            if(maps[i][j])
            {
                res=min(res,sum+maps[i][j]-p[i][j]);
            }

          }

      }

        if(res==sum)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

 

评论

1 楼 hellotieye 2016-08-19  

题目是什么意思？？？