The solution to this problem is Feluogu
Mmmm, okay, seeing this topic, we know that he is very suitable for the occasion. Now, we still need to pay attention to epidemic prevention. Please wear masks and protect yourself! !
Closer to home, everything is foreshadowed, and if you don’t, let’s take a look at the topic.
[NOIP2012 Improvement Team] Epidemic Control
Topic description
H has n cities, and these n cities are connected by n-1 two-way roads to form a tree. City No. 1 is the capital and the root node of the tree.
An outbreak of a highly dangerous infectious disease broke out in the capital of country H. In order to control the epidemic and prevent the epidemic from spreading to border cities (the cities represented by leaf nodes), the authorities decided to use the army to establish checkpoints in some cities, so that every path from the capital to the border cities has at least one checkpoint. Cities can also establish checkpoints. However, it is important to note that checkpoints cannot be established in the capital.
Now, there are troops stationed in some cities in country H, and a city can be stationed with multiple troops. An army can move between cities connected by roads and establish checkpoints in any city except the capital, and can only establish checkpoints in one city. The time required for an army to move from one city to another via a road is equal to the length of the road (unit: hours).
May I ask how many hours it will take to control the outbreak. Note: Different armies can move at the same time.
input format
The first line contains an integer $n$, which represents the number of cities.
The following n − 1 n-1 n−1 lines of 3 integers each, u , v , w u,v,w u,v,w, each two integers are separated by a space, indicating that there is a line from city u to city v with a length of w w w road. The data guarantees that the input is a tree, and the root node number is 1 1 1.
The next line is an integer m m m, represents the number of troops.
The next line consists of m integers, separated by a space, respectively representing the numbers of the cities where the m troops are stationed.
output format
An integer representing the minimum time required to control the outbreak. If the epidemic cannot be controlled, export − 1 -1 −1.
Example #1
Sample Input #1
4 1 2 1 1 3 2 3 4 3 2 2 2
Sample output #1
3
hint
[Explanation of input and output samples]
The first army was 2 2 Checkpoint 2 is set up, and the second army starts from 2 2 Move point 2 to point $3$ to set up a checkpoint, the time required is 3 3 3 hours.
[data range]
Make sure that the army will not be stationed in the capital.
- for 20 % 20\% 20% of the data, 2 ≤ n ≤ 10 2 \le n\le 10 2≤n≤10；
- for 40 % 40\% 40% of the data, 2 ≤ n ≤ 50 2 \le n\le 50 2≤n≤50， 0 < w < 1 0 5 0<w <10^5 0<w<105；
- for 60 % 60\% 60% of the data, 2 ≤ n ≤ 1000 2 \le n\le 1000 2≤n≤1000， 0 < w < 1 0 6 0<w <10^6 0<w<106；
- for 80 % 80\% 80% of the data, 2 ≤ n ≤ 1 0 4 2 \le n\le 10^4 2≤n≤104；
- for 100 % 100\% 100% data, 2 ≤ m ≤ n ≤ 5 × 1 0 4 2\le m\le n≤5\times 10^4 2≤m≤n≤5×104， 0 < w < 1 0 9 0<w <10^9 0<w<109.
NOIP 2012 Improvement Group Day 2 Question 3
Okay, you can see that the last sentence shows that this question is not easy, we have to take it seriously,
It can be seen from the title that this question is to let us output the shortest time to control the epidemic. We can use if else as the final conclusion. The overall code uses two points, dfs thinking
Look at the code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=6e4;
int n,m,t,tt=0,att=0,btt=0,ctt=0;
int d[N],qq[N],f[N][20];
int ver[2*N],ee[2*N],NN[2*N],ff[N];
bool ok,sta[N],asd[N];
ll ans,meme[N],ned[N],dist[N][20];
pair<ll,int> h[N];
queue<int> q;
void aa(int x,int y,int z)
{
ver[++tt]=y,ee[tt]=z,NN[tt]=ff[x],ff[x]=tt;
}//1. Input
void bfs()
{
q.push(1);
d[1]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int i=ff[x];i;i=NN[i])
{
int y=ver[i];
if(d[y])
continue;
d[y]=d[x]+1;
f[y][0]=x,dist[y][0]=ee[i];
for(int j=1;j<=t;j++)
{
f[y][j]=f[f[y][j-1]][j-1];
dist[y][j]=dist[y][j-1]+dist[f[y][j-1]][j-1];
}
q.push(y);
}
}
}//Multiplication preprocessing
bool dfs(int x)
{
bool pson=0;
if(sta[x])
return 1;
for(int i=ff[x];i;i=NN[i])
{
int y=ver[i];
if(d[y]<d[x])
continue;
pson=1;
if(!dfs(y))
return 0;
}
if(!pson)
return 0;
return 1;
}//dfs finds leaf nodes whose paths are not stationed
bool check(ll lim)
{
memset(sta,0,sizeof(sta));
memset(meme,0,sizeof(meme));
memset(ned,0,sizeof(ned));
memset(h,0,sizeof(h));
memset(asd,0,sizeof(asd));
att=0,btt=0,ctt=0;//initialization
for(int i=1;i<=m;i++)
{
ll x=qq[i],cnt=0;
for(int j=t;j>=0;j--)
if(f[x][j]>1 && cnt+dist[x][j]<=lim)
{
cnt+=dist[x][j];
x=f[x][j];
}
if(f[x][0]==1 && cnt+dist[x][0]<=lim)
h[++ctt]=make_pair(lim-cnt-dist[x][0],x);
else
sta[x]=1;
}//move up the army
for(int i=ff[1];i;i=NN[i])
if(!dfs(ver[i]))
asd[ver[i]]=1;//dfs finds leaf nodes whose paths are not stationed
sort(h+1,h+ctt+1);
for(int i=1;i<=ctt;i++)
if(asd[h[i].sss] && h[i].first<dist[h[i].sss][0])
asd[h[i].sss]=0;
else
meme[++att]=h[i].first;//Preliminary processing of the child nodes of the root node that need to be stationed
for(int i=ff[1];i;i=NN[i])
if(asd[ver[i]])
ned[++btt]=dist[ver[i]][0];//Find the node that still needs to be camped and store
if(att<btt)
return 0;
sort(meme+1,meme+att+1),sort(ned+1,ned+btt+1);
int i=1,j=1;
while(i<=btt && j<=att)
if(meme[j]>=ned[i])
{
i++,j++;
}
else
j++;
if(i>btt)
return 1;
return 0;//greedy matching
}
int main()
{
ll l=0,r=0,mid;
cin>>n;
t=log2(n)+1;
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
aa(x,y,z),aa(y,x,z);
r+=z;
}
bfs();Multiplication preprocessing
cin>>m;
for(int i=1;i<=m;i++)
scanf("%d",&qq[i]);
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
ok=1;
}
else
l=mid+1;
}//two points
if(!ok)
cout<<-1;
else
cout<<ans;//output
return 0;
}
Crab watching
Come on a little story
