1101 - A Secret Mission
All of you have heard about Evil Jack Diablo, the one who had stolen the whole problem set from the Good Judges last time. Once again he is making evil plans, but he does not know that Alice is on a secret mission. There will be several pairs of City of Evils on the way of Alice's mission.
There will be N evil cities (numbered by 1, 2, ..., N) connected by M bidirectional roads. There will be evil guards patrolling the roads. Since they are not much intelligent, the danger of travelling in each road is not the same. Alice is going to travel from city s to city t. You can safely assume that it's possible to travel from any city to another. John the legend programmer has estimated the danger of each road but since he is busy arranging contests, Alice is depending on you now. Danger of a path from city s to city t is defined as the maximum danger of any road on this path. As you are one of the most talented programmers, you will love to help Alice by finding the least dangerous paths to prevent Evil Jack from doing harms to the Judges.
Input
Input starts with an integer T (≤ 3), denoting the number of test cases.
Each case contains two integers N, M (2 ≤ N ≤ 50000, 1 ≤ M ≤ 105) denoting the number of cities and roads. Each of the next M lines contains three integers: xi, yi, di (1 ≤ xi, yi ≤ N, xi ≠ yi, 1 ≤ di ≤ 104) - the cities connected by the ith road and its degree of danger. Next line contains an integer q (1 ≤ q ≤ 50000). Each of the next q lines contains two integers: si and ti (1 ≤ si, ti ≤ N, si ≠ ti).
Output
For each test case, print the case number first. Then for each query si ti, print the least dangerous path in a line.
Sample Input
Output for Sample Input
2
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
2 1
1 2 100
1
1 2
Case 1:
20
20
Case 2:
100
Notes
Dataset is huge, use faster i/o methods.
---------------------------------------------EDITORIAL----------------------------------------------------------
THIS PROBLEM CAN BE SOLVED WITH LCA ,
MAIN PROBLEM IS HOW TO APPLY LCA ON GRAPH , SINCE GRAPH CONTAINS CYCLE SO CONCEPT OF LCA IS NOT APPLICABLE ON GRAPH ,
IN THE PROBLEM WE HAVE TO FIND MIN( FOR ALL PATH MAX IN THAT PATH)
IF WE CONVERT GRAPH TO MST THAN PROBLEM CAN BE SOLVED ,
BUT WHY MST OF GRAPH WILL WORK ?
SINCE WHILE CREATING MST WE REMOVE ONLY THOSE EDGE FORMING A CYCLE AND WE ALWAYS REMOVE THE EDGE WITH MAXIMUM WEIGHT OF THE CYCLE SO IN ANY CASE THAT EDGE WILL NOT CONTRIBUTE IN THE ANS SINCE IN THE GRAPH IF GRAPH IS CIRCULAR THAN THERE MUST BE 2 WAYS FROM EACH NODE TO REACH TO ANOTHER NODE , AND WE ALWAYS AVOID THAT EDGE BECAUSE ITS WEIGHT IS VERY HIGH .....
SO TILL NOW WE CONCLUDED THAT MST OF THE GRAPH WILL WORK,,
NOW THERE IS ONLY ONE PATH B/W ANY TWO NODES NOW WE HAVE TO FIND MAXIMUM B/W ANY TWO NODE ..
FIRST WE WILL FIND LCA OF 2 NODE ,
LET LCA OF A AND B IS C
MAX OF EDGE B/W( A,B )= MAX(MAX OF EDGE B/W( C,B ),MAX OF EDGE B/W( A,C ));;
NOW WE HAVE TO JUST FIND MAXIMUM OF EDGE B/W ANY NODE TILL ITS ALL PARENT , SINCE IN ANY CASE ITS SOME PARENT WILL BE THE LCA , WE CAN USE ANOTHER DP TABLE TO COMPUTE MAX FOR NODE TO ALL ITS PARENT
FOR(INT HEIGHT=1;HEIGHT<25;HEIGHT++)
{
FOR(INT I=1;I<=N;I++)
{
IF(DP_PAR[I][HEIGHT-1]!=-1)
DP_MAX[I][HEIGHT]=MAX(DP_MAX[DP_PAR[I][HEIGHT-1]][HEIGHT-1],DP_MAX[I] [HEIGHT-1]);
}
}
THIS DP_MAX[I][J] WILL CONTAIN THE MAXIMUM VALUE OF NODE FOR I TILL ITS (1<<J) TH PARENT THIS COMPUTATION IS SAME AS THE LCA COMPUTATION , IN LCA WE COMPUTE FOR
A NODE (1<<J) TH PARENT , HERE WE COMPUTED MAXIMUM IN FROM I TO ITS (1<<J)TH PARENT...
NOW WE HAVE TO FIND THE ANSWER
NOW WE JUST NEED TO DO BINARY RAISE OF A AND B TILL THERE LCA TO FIND MAX IN THERE PATH THIS WILL BE DONE ON THE DP_MAX[][] ARRAY
INT MAXIMUM(INT A,INT B,INT PAR)
{
IF(LEV[A]<LEV[B]) SWAP(A,B);
INT LG;
FOR(LG=1;(1<<LG)<=LEV[A];LG++);
LG--;
INT ANS=-1;// THIS IS THE MAXIMUM IN THERE PATH
FOR(INT I=LG;I>=0;I--)
{
IF(LEV[A]-(1<<I)>=LEV[B])
{
IF(ANS<DP_MAX[A][I])
ANS=DP_MAX[A][I];
A=DP_PAR[A][I];// MOVING A UPWARD
}
}
// FIRST RISE THE NODE WHICH IS BELOW , MAKE THEM AT THE SAME LEVEL
// COUT<<" AFTER SAME BASE ANS "<<ANS<<ENDL;
IF(A==B)
{
RETURN ANS;
}
ELSE
{
FOR(INT I=LG;I>=0;I--)
{
IF(DP_PAR[A][I]!=-1 && DP_PAR[A][I]!=DP_PAR[B][I])// MOVING BOTHA AND B UP
{
// SINCE WE ARE RAISING BOTH A AND B TO THERE PARENT SO WE NEED TO TAKE //MAXIM IN BETWEEN I TO (1<<J) AND THAN SHIFT SO THAT WE HAVE COVERED
// ALL MAX FROM I TO ITS PARENT TILL (1<<J)
ANS=MAX(ANS,DP_MAX[A][I]);
ANS=MAX(ANS,DP_MAX[B][I]);
A=DP_PAR[A][I];
B=DP_PAR[B][I];
}
}
// SINCE WE REACHED TO THE JUST BELOW THE PARENT SO WE NEED TO RETURN MAX
// OF ANS AND EDGE B/W THERE PARENTS
RETURN MAX(ANS,MAX(DP_MAX[A][0],DP_MAX[B][0]));
}
}
----------------------------------------------------------OR----------------------------------------------
Explanation.
First of all we realize that changing the given graph into an MST is an appropriate approach to this problem. Why?
Because though MST is not the minimum cost tree , but it removes the maximum weight edges , since the edges are only connected if needed, hence it is guaranteed that now if we are trying to join two edges then they are the local best connection. Hence replacing the graph with a MST will give us the minimum of all maximas for all pair of vertices.
Now after the tree is formed the question reduces to standard LCA question where
for finding the dangerous cost for any pair of node (p,q) we first calculate the danger level of the node (p,lca), and (q,lca) then return the max of two.
We use binary raise to travel till LCA.
========================CODE===========================================
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
vector<pair<pair<int,int> ,int> > v;
int dp_max[100010][25];
int dp_par[100010][25];
list<pair<int,int> > li[100010];
int rank[100010];
int parent[100010];
int lev[100010];
#define mp make_pair
int find(int a)
{
if(parent[a]!=parent[parent[a]])
{
parent[a]=find(parent[a]);
}
return parent[a];
}
int merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int dfs(int start,int par,int l)
{
lev[start]=l;
list<pair<int,int> >:: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(it->first!=par)
{
lev[it->first]=l+1;
dp_par[it->first][0]=start;
dp_max[it->first][0]=it->second;
dfs(it->first,start,l+1);
}
}
}
int binary_rais(int a,int b)// return lca of a,b
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
a=dp_par[a][i];// moving a upward
}
}
if(a==b) return a;
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return dp_par[a][0];
}
}
int maximum(int a,int b,int par)
{
if(lev[a]<lev[b]) swap(a,b);
int lg;
for(lg=1;(1<<lg)<=lev[a];lg++);
lg--;
int ans=-1;
for(int i=lg;i>=0;i--)
{
if(lev[a]-(1<<i)>=lev[b])
{
if(ans<dp_max[a][i])
ans=dp_max[a][i];
a=dp_par[a][i];// moving a upward
}
}
// cout<<" after same base ans "<<ans<<endl;
if(a==b)
{
return ans;
}
else
{
for(int i=lg;i>=0;i--)
{
if(dp_par[a][i]!=-1 && dp_par[a][i]!=dp_par[b][i])// moving botha and b up
{
ans=max(ans,dp_max[a][i]);
ans=max(ans,dp_max[b][i]);
a=dp_par[a][i];
b=dp_par[b][i];
}
}
return max(ans,max(dp_max[a][0],dp_max[b][0]));
}
}
int main()
{
int t;
cin>>t;
int cas=1;
while(t--)
{
cout<<"Case "<<cas++<<":"<<endl;
memset(dp_max,-1,sizeof dp_max);
memset(dp_par,-1,sizeof dp_par);
memset(lev,0,sizeof lev);
v.clear();
for(int i=0;i<100010;i++)
{
li[i].clear();
}
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<100010;i++)
{
rank[i]=1;
parent[i]=i;
}
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
// cin>>a>>b>>c;
v.push_back(mp(mp(c,a),b));
}
sort(v.begin(),v.end());
for(int i=0;i<m;i++)
{
int a=v[i].first.second;
int b=v[i].second;
int cost=v[i].first.first;
if(find(a)!=find(b))
{
li[a].push_back({b,cost});
li[b].push_back({a,cost});
merge(a,b);
}
}
dp_par[1][0]=0;
dp_max[1][0]=0;
dfs(1,0,1);
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
dp_par[i][height]=dp_par[dp_par[i][height-1]][height-1];
}
}
for(int height=1;height<25;height++)
{
for(int i=1;i<=n;i++)
{
if(dp_par[i][height-1]!=-1)
dp_max[i][height]=max(dp_max[dp_par[i][height-1]][height-1],dp_max[i][height-1]);
}
}
int q;
cin>>q;
while(q--)
{
int a,b;
scanf("%d %d",&a,&b);
int par=binary_rais(a,b);
printf("%d\n",maximum(a,b,par));
}
}
}
No comments:
Post a Comment