hdu 1598 暴力+并查集

#include<stdio.h>

#include<stdlib.h>

#define N 300

int pre[N];

int find(int u) {

if(u!=pre[u])

pre[u]=find(pre[u]);

return pre[u];

}

struct node {

int u,v,speed;

}ma[1100];

int cmp(const void *a,const void *b) {

return (*(struct node *)a).speed-(*(struct node *)b).speed;

}

int main() {

int q,max,min,i,j,s,t,n,m,cha,flag,a,b;

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

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

scanf("%d%d%d",&ma[i].u,&ma[i].v,&ma[i].speed);

scanf("%d",&q);

qsort(ma,m,sizeof(ma[0]),cmp);

while(q--) {

scanf("%d%d",&s,&t);

cha=1000000;

for(i=0;i<m;i++) {

flag=0;

min=1000000;

max=-1;

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

pre[j]=j;

for(j=i;j<m;j++) {

a=find(ma[j].u);

b=find(ma[j].v);

if(a!=b) {

pre[a]=b;

if(max<ma[j].speed)max=ma[j].speed;

if(min>ma[j].speed)min=ma[j].speed;

}

if(find(s)==find(t)) {flag=1;break;}

}

if(max-min<cha&&flag==1)

cha=max-min;

}

if(cha==1000000)printf("-1\n");

else printf("%d\n",cha);

}

}

return 0;

}

巴特西

hdu 1598 暴力+并查集

最新文章

热门文章