pku 3522 slim span

#include
#include
using namespace std;

const int maxn=5005;
const int maxm=5005;
const int maxint=100000000;

int id[maxm],eu[maxm],ev[maxm],ew[maxm],n,m,pnt[maxn];
//eu[p]->ev[p]------ew[p]    第p条边的起点eu[p],终点ev[p],权值ew[p]
int cmp(const int &i,const int &j) {return ew[i]

int find(int x)
{
 if(x!=pnt[x])
  pnt[x]=find(pnt[x]);
 return pnt[x];
}

int main()
{
 int i,j,k,num,dis,an,max,min,p,ret;
      while(scanf("%d%d",&n,&m)&&n+m)
   {  // n 顶点的个数   m 边数 
    for(k=0;k    {
          scanf("%d%d%d",&eu[k],&ev[k],&ew[k]);               
          }
    if(m    //初始化
       for(i=1;i<=n;i++) pnt[i]=i;  //node[1..n]
       for(i=0;i    sort(id,id+m,cmp);
    an=maxint;
          //枚举 最小生成树
          for(i=0;i    {
             for(int ii=1;ii<=n;ii++) pnt[ii]=ii;
       int count=0;
       for(j=i;j    {     //&&ew[id[j]]-ew[id[i]]                  if(find(ev[id[j]])!=find(eu[id[j]]))
      {
       count++;
       pnt[find(eu[id[j]])]=find(ev[id[j]]);
       if(count==n-1)
       {
        if(ew[id[j]]-ew[id[i]]        break;
       }
      }
    }
    }

    if(an==maxint) printf("-1\n");
    else
    printf("%d\n",an);
   }
   return 0;
}

阅读(570) | 评论(0) | 转发(0) |

0

上一篇：pku 2104 select the kth number

下一篇：Jose 问题 3517