HDU 3938 Portal
10263 ワード
Portal
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2027 Accepted Submission(s): 998
Problem Description
ZLGG found a magic theory that the bigger banana the bigger banana peel .This important theory can help him make a portal in our universal. Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge in the path. There may be lots of paths between two points. Now ZLGG owned L energies and he want to know how many kind of path he could make.
Input
There are multiple test cases. The first line of input contains three integer N, M and Q (1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,000). N is the number of points, M is the number of edges and Q is the number of queries. Each of the next M lines contains three integers a, b, and c (1 ≤ a, b ≤ N, 0 ≤ c ≤ 10^8) describing an edge connecting the point a and b with cost c. Each of the following Q lines contain a single integer L (0 ≤ L ≤ 10^8).
Output
Output the answer to each query on a separate line.
Sample Input
10 10 10 7 2 1 6 8 3 4 5 8 5 8 2 2 8 9 6 4 5 2 1 5 8 10 5 7 3 7 7 8 8 10 6 1 5 9 1 8 2 7 6
Sample Output
36 13 1 13 36 1 36 2 16 13
Source
2011 Multi-University Training Contest 10 - Host by HRBEU
Recommend
We have carefully selected several similar problems for you: 3935 3937 3931 3932 3933
分析:
タイトル:
あなたに1つの図をあげて、権力を持って、あなたに2点の間の距離がLの点の対の数より小さいことを聞きます
2点間距離の定義:
2点間のすべてのパスの中で、最も長いエッジの中で最も小さいエッジ(多くのパスの中で最も長いエッジの中で最も小さい値)は理解に注意します.
Lを昇順に並べ替え、入力した重み値に従ってエッジを昇順に並べ替える
理由:例えばL 1
L 1の答えにある値(前の値と重複しない部分でなければなりません)を加えるので、まず小さいLの答えを得て、それから小さいLの答えで大きいのを求めます
Lの答えは、L入力の順番で順番に出力されます.これがいわゆるオフライン化です
そして最初の最小Lから走り始め、このときも最小重み値のエッジから走り始めます.このコードの最も不思議なところは、2つの距離を得ることです.
理由:最初は重み値の昇順で並べ替えられていたので、このとき得られたエッジはセット内のすべてのエッジの中で最大、つまりすべてのパスの中で最も長いエッジの最小値です.最初は2つだったからです.
点は連通していないので、いったんこの辺を通って連通して、それではこの時歩くことができるのはこの1本の道だけで、あなたはきっと通ることができて、しかもこの辺は現在のすべての辺の中で最も長いあの辺で、だからこの辺は
2点间のいわゆる距离!!!
私は料理が上手で、はっきり言っていないかもしれませんが、コードを見てもいいです.主にforループと内部のwhileループの部分です.
理解しにくいし、奇妙だ.
code:
転載先:https://www.cnblogs.com/yinbiao/p/9464049.html
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2027 Accepted Submission(s): 998
Problem Description
ZLGG found a magic theory that the bigger banana the bigger banana peel .This important theory can help him make a portal in our universal. Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge in the path. There may be lots of paths between two points. Now ZLGG owned L energies and he want to know how many kind of path he could make.
Input
There are multiple test cases. The first line of input contains three integer N, M and Q (1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,000). N is the number of points, M is the number of edges and Q is the number of queries. Each of the next M lines contains three integers a, b, and c (1 ≤ a, b ≤ N, 0 ≤ c ≤ 10^8) describing an edge connecting the point a and b with cost c. Each of the following Q lines contain a single integer L (0 ≤ L ≤ 10^8).
Output
Output the answer to each query on a separate line.
Sample Input
10 10 10 7 2 1 6 8 3 4 5 8 5 8 2 2 8 9 6 4 5 2 1 5 8 10 5 7 3 7 7 8 8 10 6 1 5 9 1 8 2 7 6
Sample Output
36 13 1 13 36 1 36 2 16 13
Source
2011 Multi-University Training Contest 10 - Host by HRBEU
Recommend
We have carefully selected several similar problems for you: 3935 3937 3931 3932 3933
分析:
タイトル:
あなたに1つの図をあげて、権力を持って、あなたに2点の間の距離がLの点の対の数より小さいことを聞きます
2点間距離の定義:
2点間のすべてのパスの中で、最も長いエッジの中で最も小さいエッジ(多くのパスの中で最も長いエッジの中で最も小さい値)は理解に注意します.
Lを昇順に並べ替え、入力した重み値に従ってエッジを昇順に並べ替える
理由:例えばL 1
L 1の答えにある値(前の値と重複しない部分でなければなりません)を加えるので、まず小さいLの答えを得て、それから小さいLの答えで大きいのを求めます
Lの答えは、L入力の順番で順番に出力されます.これがいわゆるオフライン化です
そして最初の最小Lから走り始め、このときも最小重み値のエッジから走り始めます.このコードの最も不思議なところは、2つの距離を得ることです.
理由:最初は重み値の昇順で並べ替えられていたので、このとき得られたエッジはセット内のすべてのエッジの中で最大、つまりすべてのパスの中で最も長いエッジの最小値です.最初は2つだったからです.
点は連通していないので、いったんこの辺を通って連通して、それではこの時歩くことができるのはこの1本の道だけで、あなたはきっと通ることができて、しかもこの辺は現在のすべての辺の中で最も長いあの辺で、だからこの辺は
2点间のいわゆる距离!!!
私は料理が上手で、はっきり言っていないかもしれませんが、コードを見てもいいです.主にforループと内部のwhileループの部分です.
理解しにくいし、奇妙だ.
code:
#include
#include<set>
#include
#include
#include
#include
#include
using namespace std;
#define N 10005
#define M 50005
int pa[N];
int sum[N];
int n,m;
struct node1
{
int id,ans,l;
}query[N];
struct node2
{
int u,v,w;
}edge[M];
bool cmp1(node2 a,node2 b)
{
return a.w<b.w;
}
bool cmp2(node1 a,node1 b)
{
return a.id<b.id;
}
bool cmp3(node1 a,node1 b)
{
return a.l<b.l;
}
void init()
{
for(int i=1;i<=n;i++)
{
pa[i]=i;
sum[i]=1;//
}
}
int find_set(int x)
{
if(x!=pa[x])
pa[x]=find_set(pa[x]);
return pa[x];
}
int union_set(int x,int y)
{
int fx=find_set(x);
int fy=find_set(y);
int temp=0;
if(fx!=fy)
{
pa[fx]=fy;
temp=sum[fx]*sum[fy];//
sum[fy]+=sum[fx];//
}
return temp;// ， 0， L L
}
int main()
{
int q;
while(~scanf("%d %d %d",&n,&m,&q))
{
init();
for(int i=0;i)
{
scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
}
for(int i=0;i)
{
scanf("%d",&query[i].l);
query[i].id=i;// L
query[i].ans=0;
}
sort(edge,edge+m,cmp1);//
sort(query,query+q,cmp3);// L
int cnt=0;
for(int i=0;i)
{
while(edge[cnt].w<=query[i].l&&cnt// W ！！！
{
int x=edge[cnt].u;
int y=edge[cnt].v;
query[i].ans+=union_set(x,y);
cnt++;//cnt ++， L L
}
if(i>0)
query[i].ans+=query[i-1].ans;// L L ， while
}
sort(query,query+q,cmp2);// L
for(int i=0;i)
{
printf("%d
",query[i].ans);
}
}
return 0;
}
/*
：
， ， L
：
， （ ）
L ，
： L1*/
転載先:https://www.cnblogs.com/yinbiao/p/9464049.html