hdu 1598と調査集+貪欲
3302 ワード
find the most comfortable road
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1906 Accepted Submission(s): 802
Problem Description
XX星には多くの都市があり、都市間では奇妙な高速道路SARS(Super Air Roam Structure---スーパーエアウォーク構造)を通じて交流が行われている.各SARSは上を走るFlycarに対して固定的なSpeedを制限している.また、XX星人はFlycarの「快適度」に対して特殊な要求を持っている.すなわち、乗る過程で最高速度と最低速度の差が小さいほど座るのが快適である.(SARSの制限速度の要求と理解して、flycarは瞬間的にスピードアップ/降速しなければならなくて、苦痛です)、
しかし、XX星人は时间にそんなに要求していません.都市间の最も快适な道を见つけてください.(SARSは双方向です).
Input
入力には、次のような複数のテストインスタンスが含まれます.
1行目には2つの正の整数n(1次の行は3つの正の整数StartCity,EndCity,speedであり、表面的にはStartCityからEndCityまでを示し、速度制限はspeedSARSである.speed<00000=10
次に正の整数Q(Q<11)であり、探索の個数を表す.
次にQ行には1行あたり2つの正の整数Start,Endがあり,探索の開始点を示す.
Output
各ルックアップには1行の印刷が必要であり、非負の整数のみが最適なルートの快適度の最も高速と最も低速の差を示す.始点と終点が到達できない場合、出力-1.
Sample Input
Sample Output
Author
ailyanlu
Source
HDU 2007-Spring Programming Contest - Warm Up (1)
Recommend
8600
まずエッジの速度を並べ替えて、毎回の要求に対して、2回forループ、エッジを列挙して、最後に図を連通させるのは最大で、1回目のループのは最小更新結果です具体的にはコードを参照してください
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1906 Accepted Submission(s): 802
Problem Description
XX星には多くの都市があり、都市間では奇妙な高速道路SARS(Super Air Roam Structure---スーパーエアウォーク構造)を通じて交流が行われている.各SARSは上を走るFlycarに対して固定的なSpeedを制限している.また、XX星人はFlycarの「快適度」に対して特殊な要求を持っている.すなわち、乗る過程で最高速度と最低速度の差が小さいほど座るのが快適である.(SARSの制限速度の要求と理解して、flycarは瞬間的にスピードアップ/降速しなければならなくて、苦痛です)、
しかし、XX星人は时间にそんなに要求していません.都市间の最も快适な道を见つけてください.(SARSは双方向です).
Input
入力には、次のような複数のテストインスタンスが含まれます.
1行目には2つの正の整数n(1
次に正の整数Q(Q<11)であり、探索の個数を表す.
次にQ行には1行あたり2つの正の整数Start,Endがあり,探索の開始点を示す.
Output
各ルックアップには1行の印刷が必要であり、非負の整数のみが最適なルートの快適度の最も高速と最も低速の差を示す.始点と終点が到達できない場合、出力-1.
Sample Input
4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2
Sample Output
1
0
Author
ailyanlu
Source
HDU 2007-Spring Programming Contest - Warm Up (1)
Recommend
8600
まずエッジの速度を並べ替えて、毎回の要求に対して、2回forループ、エッジを列挙して、最後に図を連通させるのは最大で、1回目のループのは最小更新結果です具体的にはコードを参照してください
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define INF 99999999
using namespace std;
struct node
{
int u,v,w;
};
node edge[1005];
int p[205];
bool operator<(node a,node b)
{
return a.w<b.w;
}
void make_set(int n)
{
int i;
for(i=0;i<=n;i++)
p[i]=i;
}
int find_set(int i)
{
int j=i;
while(j!=p[j])
j=p[j];
return p[i]=j;
}
int Union(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(x==y)
return 0;
else
{
p[x]=y;
return 1;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(edge,0,sizeof(edge));
int i;
for(i=0;i<m;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
int q;
sort(edge,edge+m);
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
int j;
int res=INF;
for(i=0;i<m;i++)
{
make_set(n);
for(j=i;j<m;j++)
{
Union(edge[j].u,edge[j].v);
if(find_set(u)==find_set(v))
{
if(edge[j].w-edge[i].w<res)
res=edge[j].w-edge[i].w;
break;
}
}
}
if(res==INF)
printf("-1
");
else
printf("%d
",res);
}
}
return 0;
}