正文

【类克鲁斯卡尔做法+枚举最小边】【HDU1598】【find the most comfortable road】

IP云
IP云V管理员/3 阅读
09/25
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

 给你一个图，有边权，K个询问：u到v 的路径中   边权最大值-边权最小值的最小值是多少

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题解（非自己想出）：把边排序 枚举最小边，然后类似克洛斯卡尔，不断加边 更新ANS值（F[i][j]） 复杂度Q*E^2  
如果Q变大 可以选择 E*E*N 预处理所有点

为何我自己没想到？：太拘泥于用深搜的想法去解决，这种跟边权最大值最小值的题目应该多考虑排序边

解法2：
二分差值，枚举最小边，再克鲁斯卡尔

复杂度（Q*log(max-min)*E*E）
复杂度显然不如 解法1



代码：

/*
WA1:忘记不能到达输出-1*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
struct Edge
{
int s,t,w;
};
int n,m;
Edge A[1100];
int father[300];
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
void input()
{
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&A[i].s,&A[i].t,&A[i].w);
}
}
void Clear()
{
for(int i=1;i<=299;i++)
father[i]=i;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if(x!=father[x])
father[x]=find(father[x]);
return father[x];
}
void Union(int a,int b)
{
int aa=find(a),bb=find(b);
father[aa]=bb;
}
void solve()
{
sort(A+1,A+m+1,cmp);
int Q,u,v; cin>>Q;
for(int k=1;k<=Q;k++)
{
cin>>u>>v;
int ok=0;
int ans=100000000;
for(int i=1;i<=m;i++)
{
Clear();
for(int j=i;j<=m;j++)
{
Union(A[j].s,A[j].t);
if(find(u)==find(v)) {
ans=min(ans,A[j].w-A[i].w);
break;
}
}
}
if(ans==100000000) printf("-1\n"); else printf("%d\n",ans);
}
}
int main()
{
// init();
while(cin>>n>>m)
{
input();
solve();
}
}