NOI 2013 패스트푸드점

Description:
n n 개의 점, n n n 개의 변 의 그림 이 있 습 니 다. 점 을 구 해서 이 점 이 다른 점 까지 의 최대 거 리 를 최소 화 합 니 다 (주의: 이 점 은 가장자리 에 있 을 수 있 습 니 다).n ≤ 1 0 5 , L i ≤ 1 0 9 n\le10^5,L_i\le10^9 n≤105,Li​≤109
Solution:
  • n n 개의 점 n n 개의 변 의 그림 이기 때문이다.
  • 그러면 그것 은 기 환 나무 이다.
  • 우선 분류 토론 을 먼저 고려 할 것 이다.우 리 는 우선 고리 위 를 해결한다.
  • 점 이 링 에 있 을 때 우 리 는 최대 거 리 는 반드시 링 위 에서 이 점 과 대립 하 는 점 의 거리 + 대립 점 의 서브 나무의 최대 깊이 이 고 이런 대립 점 은 많아야 2 개가 있다 는 것 을 알 수 있다.
  • 대립 점 이 2 개 라 는 것 을 고려 할 때 이 두 대립 점 사이 의 변 이 쓸모없는 것 을 발견 하면 삭제 할 수 있다.
  • 그러면 이 를 통 해 우 리 는 고리 하 나 를 매 거 져 삭제 할 수 있다. 그러면 답 은 남 은 이 나무의 지름 을 2 로 나 누 는 것 이다.
  • 그러나 매 거 진 링 변, 이런 복잡 도 는?Θ ( n 2 ) \Theta(n^2) Θ(n2) 의.
  • 그러면 우 리 는 데이터 구 조 를 고려 하여 최적화 시킨다.
  • 삭제 할 링 변 (k, k + 1) (k, k + 1) (k, k + 1) (k, k + 1) 에 대해 우 리 는 지름 을 찾 고 두 번 dfs 에서 지름 에 대한 깨 우 침 을 찾 습 니 다. 우 리 는 k k k 점 에서 왼쪽으로 가장 먼 거 리 를 찾 고 이 점 에서 가장 먼 거 리 를 찾 습 니 다. 마찬가지 로 k + 1 k + 1 k + 1 k + 1 점 에서 오른쪽으로 찾 습 니 다.
  • 그렇다면 고리 에서 거 리 를 두 고 우 리 는 D i s t (i, j) = m x [i] + m x [j] + [j] + {d i s [j] [j] − d i s [i], i ≤ j L e n − d i s [j] + d i [i], i > j Dist (i, j) = mx [i]] + mx [j]] + mx [j] + mx [j] + \ \ \ \ \ \ \ \ dis[j] - dis[j], i \ \ \ \ '- dis[j] + dis[j], i > j \ \ \ \ \ \ end {cases} Dis(i, i, i, i, i \ \ \ \ \ \ \ \ \ j - dis[j - dis[j], i) = mx [i] + mx [j] + {dis [j] − dis [i], i ≤ jLen − dis [j] + dis [i], i > j
  • 우 리 는 선분 수 를 고려 하여 링 의 모든 점 에서 다른 점 까지 의 최대 거 리 를 유지 할 수 있다.
  • 이런 복잡 도 는Θ ( n log ⁡ n ) \Theta(n\log n) Θ(nlogn)

  • Code:
    #include
    using namespace std;
    #define REP(i,f,t) for(int i=(f),i##_end_=(t);i<=i##_end_;++i)
    #define SREP(i,f,t) for(int i=(f),i##_end_=(t);i=i##_end_;--i)
    #define ll long long
    templateinline bool chkmin(T&x,T y){return x>y?x=y,1:0;}
    templateinline bool chkmax(T&x,T y){return xinline void rd(T&x){
    	x=0;char c;
    	while((c=getchar())<48);
    	do x=(x<<1)+(x<<3)+(c^48);
    	while((c=getchar())>47);
    }
    
    const int N=2e5+2;
    
    int n;
    
    int qwq,head[N];
    struct edge{
    	int to,nxt;
    	ll w;
    }E[N<<1];
    void addedge(int x,int y,ll z){E[qwq]=(edge){y,head[x],z};head[x]=qwq++;}
    #define EREP(x) for(int i=head[x];~i;i=E[i].nxt)
    
    int dfn[N],low[N],tim;
    int stk[N<<1],top;
    bool vis[N];
    
    int chain[N],len;
    bool belong[N];
    
    ll ans;
    
    void tarjan(int x,int f){
    	dfn[x]=low[x]=++tim;
    	stk[++top]=x;
    	bool flag=1;
    	EREP(x){
    		int y=E[i].to;
    		if(y==f and flag){flag=0;continue;}
    		if(!dfn[y]) tarjan(y,x),chkmin(low[x],low[y]);
    		else chkmin(low[x],dfn[y]);
    	}
    	if(dfn[x]==low[x]){
    		if(stk[top]!=x){
    			do {
    				chain[++len]=stk[top];
    				belong[stk[top]]=1;
    			}while(x!=stk[top--]); 
    		}
    		else top--;
    	}
    }
    
    struct p70{
    	
    	bool mark[N<<1];
    	ll Mx,Id;
    	
    	void dfs1(int x,int f,ll d){
    		if(chkmax(Mx,d)) Id=x;
    		EREP(x){
    			if(mark[i])continue;
    			if(E[i].to!=f) dfs1(E[i].to,x,d+E[i].w);
    		}
    	}
    	
    	void dfs2(int x,int f,ll d){
    		if(chkmax(Mx,d)) Id=x;
    		EREP(x){
    			if(mark[i])continue;
    			if(E[i].to!=f) dfs2(E[i].to,x,d+E[i].w); 
    		}
    	}
    	
    	void solve(){
    		
    		ans=1e18;
    		
    		REP(p,1,len){
    			int x=chain[p],y=chain[p%len+1];
    			EREP(x){
    				if(E[i].to==y) {
    					mark[i]=mark[i^1]=1;
    					
    					Mx=Id=-1;
    					dfs1(1,0,0);
    					Mx=-1;
    					dfs2(Id,0,0);
    					
    					chkmin(ans,Mx);
    					
    					mark[i]=mark[i^1]=0;
    				}
    			}
    		}
    		
    		printf("%.1lf
    ",1.0*ans/2); } }p1; ll dep[N<<1],dis[N],sum[N<<1]; ll mx[N],Sum[N]; ll Dist(int x,int d){ if(!~x) return -1e18; return dep[x]+((d==1)?-sum[x]:sum[x]); } struct p100{ ll dfs(int x,int f,ll d,int id){ chkmax(dep[id],d); mx[x]=Sum[x]=0; EREP(x){ int y=E[i].to; if(y==chain[id%len+1]) dis[id]=E[i].w; if(y==f or belong[y])continue; ll t=dfs(y,x,d+E[i].w,id)+E[i].w; chkmax(Sum[x],mx[x]+t); chkmax(mx[x],t); } return mx[x]; } struct Tree{ #define lson L,mid,p<<1 #define rson mid+1,R,p<<1|1 #define family tree[p],tree[p<<1],tree[p<<1|1] struct node{ int L,R; int id1,id2; ll mx1,mx2; }tree[N<<2]; void Up(node &A,node L,node R){ if(L.mx1>R.mx1)A.mx1=L.mx1,A.id1=L.id1; else A.mx1=R.mx1,A.id1=R.id1; if(L.mx2>R.mx2)A.mx2=L.mx2,A.id2=L.id2; else A.mx2=R.mx2,A.id2=R.id2; } void build(int L,int R,int p){ tree[p].L=L,tree[p].R=R; if(L==R){ tree[p].mx1=Dist(L,1); tree[p].mx2=Dist(L,2); tree[p].id1=tree[p].id2=L; return; } int mid=(L+R)>>1; build(lson),build(rson); Up(family); } int query(int L,int R,int p,int op){ if(L>R)return -1; if(tree[p].L==L and tree[p].R==R) return op==1?tree[p].id1:tree[p].id2; int mid=(tree[p].L+tree[p].R)>>1; if(R<=mid) return query(L,R,p<<1,op); else if(L>mid) return query(L,R,p<<1|1,op); else { int l=query(lson,op),r=query(rson,op); return Dist(l,op)>Dist(r,op)?l:r; } } }T; void solve(){ REP(i,1,len){ dfs(chain[i],0,0,i); sum[i]=sum[i-1]+dis[i-1]; } REP(i,1,len){ dep[i+len]=dep[i]; if(i>1) sum[i+len]=sum[i+len-1]+dis[i-1]; else sum[i+len]=sum[len]+dis[len]; } ans=1e18; T.build(1,len<<1,1); REP(i,1,len){ int l1=T.query(i,i+len-1,1,1); int l2=T.query(i,i+len-1,1,2); int tmp; ll Mx=0; if(l1==l2){ int r1=T.query(i,l1-1,1,1); tmp=T.query(l1+1,i+len-1,1,1); if(Dist(tmp,1)>Dist(r1,1))r1=tmp; int r2=T.query(i,l2-1,1,2); tmp=T.query(l2+1,i+len-1,1,2); if(Dist(tmp,2)>Dist(r2,2))r2=tmp; Mx=Dist(l1,1)+Dist(r2,2); chkmax(Mx,Dist(l2,2)+Dist(r1,1)); } else Mx=Dist(l1,1)+Dist(l2,2); chkmin(ans,Mx); } REP(i,1,n) chkmax(ans,Sum[i]); printf("%.1lf
    ",1.0*ans/2); } }p2; int main(){ // freopen("foodshop.in","r",stdin); // freopen("foodshop.out","w",stdout); rd(n); memset(head,-1,sizeof head); REP(i,1,n){ int a,b;ll c; rd(a),rd(b),rd(c); addedge(a,b,c); addedge(b,a,c); } tarjan(1,0); if(n<=3000) p1.solve(); else p2.solve(); return 0; }

    Summary:
  • 기 환 수 에 대한 문 제 는 일반적인 고 리 를 뽑 아 고리 에 글 을 쓴다.
  • 분류 토론, 데이터 구조 (흔히 볼 수 있 는: 라인 트 리, 단조 로 운 대기 열, 단조 로 운 스 택) 유 지 는 모두 링 상의 문 제 를 해결 하 는 필연 적 인 작업 이다.
  • 좋은 웹페이지 즐겨찾기