[NOI2014T2] 마법 의 숲 - LCT 유지 보수 최소 생 성 트 리

테스트 주소: 마법 의 숲 방법: 이 문 제 는 정말 신 입 니 다. 최소 생 성 나 무 를 생각 했 지만 그 중의 한 변 수 를 매 거 하 는 방법 만 생각 했 습 니 다. 원래 LCT 는 이렇게 사용 할 수 있 었 습 니 다............................................이 문제 의 표준 해법 은 LCT 로 최소 생 성 트 리 를 유지 하 는 것 이다.우 리 는 이 문 제 를 얼핏 보면 수호 정령 이 하나 밖 에 없다 면 최소 생 성 트 리 를 만 들 거나 SPFA 와 유사 한 BFS 를 뛰 면 된다. 그러나 이 문 제 는 두 가지 수호 정령 이 존재 한다. 정 답 은 두 가지 수호 정령 사용량 의 합 이다. 이 럴 때 우 리 는 다른 방법 을 고려 해 야 한다.어떤 학생 들 은 두 번 째 로 정령 을 지 키 는 수량 을 생각 하고 두 번 째 로 뛰 는 것 에 대해 가장 작은 나 무 를 만 든 다음 에 blablabla 를 만 들 수도 있다.유감스럽게도 이런 생각 은 틀 렸 고 반 례 는 쉽게 찾 아 낼 수 있다.그러면 우 리 는 첫 번 째 수호 정령 의 수량 을 매 거 진 후에 최소 생 성 트 리 를 달 릴 수 있 습 니 다. 그러면 시간 복잡 도 는 O (max (ai) M) 이 고 모든 데 이 터 를 통과 할 수 없습니다.생각해 보 니 최소 생 성 나 무 를 달 릴 때마다 뜯 어 재 구축 하면 서 구축 한 정 보 를 낭비 하 게 된다.이전의 정 보 를 충분히 이용 하려 면 다음 과 같은 방법 을 사용 할 수 있 습 니 다. 먼저 모든 변 에 대해 ai 를 누 르 고 작은 것 에서 큰 것 으로 정렬 한 다음 에 한 변 을 추가 합 니 다. 한 변 을 추가 하기 전에 변 의 두 점 이 연결 되 었 는 지 확인 하고 연결 되 지 않 으 면 이 변 을 직접 연결 합 니 다. 그렇지 않 으 면 이미 구 축 된 나무 중의 이 두 점 간 의 경로 에서 가장 큰 bi 를 물 어보 십시오.만약 이 최대 치가 추가 할 변 의 bi 보다 크다 면 원래 의 변 을 없 애고 새 변 을 추가 하 십시오. 그렇지 않 으 면 움 직 이지 않 습 니 다.사 이 드 를 추가 한 후 점 1 과 점 N 이 연결 되 는 지 확인 합 니 다. 연결 되면 이 두 점 사이 의 경로 에서 가장 큰 bi 에 방금 추 가 된 변 의 ai 를 추가 하여 답 을 업데이트 하면 됩 니 다.분명 한 것 은 추가 할 변 의 ai 가 이미 알 고 있 는 답 보다 더 크 면 바로 물 러 나 는 것 이다. 이 가지치기 가 많은 시간 을 절약 할 수 있 는 것 으로 알려 졌 다.이상 의 방법 은 실현 가능 한 것 이다. 관건 은 세 가지 점 에 있다. 하 나 는 두 점 간 의 연관 성 을 판단 하 는 것 이 고, 다른 하 나 는 변 의 삭제 와 삽입 이다. 셋째, 문의 경로 의 변 권 최대 치 이다.그러면 우 리 는 LCT 로 지 킬 수 있 습 니 다. LCT 가 직접 변 권 을 지 키 는 것 이 매우 번 거 롭 기 때문에 우 리 는 변 권 을 점 으로 바 꿀 수 있 습 니 다. 점 권 은 원래 의 변 권 으로 원래 의 두 점 을 연결 할 수 있 습 니 다. 원래 의 점 권 은 모두 0 입 니 다. 그러면 등가 의 그림 을 얻 을 수 있 습 니 다.이상 알고리즘 의 복잡 도 는 O (Mlog (N + M) 로 모든 데 이 터 를 통과 할 수 있 습 니 다.2 번 을 저 지 른 곳: 많이 갔 어 요. 이런 코드 의 양 이 많은 문 제 를 너무 오래 쓰 지 않 았 어 요. 특히 LCT 는 실 현 된 많은 디 테 일 을 잊 어 버 렸 어 요. 한참 을 바 꿨 어 요. 그리고 조작 의 논리 적 순 서 를 뒤 집 는 거 예요. 먼저 건 드 린 아이의 노드 를 바 꿔 야 해 요. 그렇지 않 으 면 현학 의 오 류 를 일 으 켜 100 점 에서 10 점 까지 의 비약 을 초래 할 수 있어 요.맞다다음은 본인 코드 입 니 다.

#include 
#include 
#include 
#include 
#include 
#define inf 1000000000
using namespace std;
int n,m,ans=inf;
int pre[150010]={0},ch[150010][2]={0},val[150010]={0},mx[150010]={0},mp[150010];
struct edge {int x,y,a,b;} e[100010];
bool rev[150010]={0},rt[150010];

bool cmp(edge a,edge b) {return a.avoid reverse(int x)
{
  rev[x]^=1;
  swap(ch[x][0],ch[x][1]);
}

void pushdown(int x)
{
  if (rev[x])
  {
    rev[x]=0;
    reverse(ch[x][0]);
    reverse(ch[x][1]);
  }
}

void pushup(int x)
{
  if (val[x]>mx[ch[x][0]]&&val[x]>mx[ch[x][1]]) mx[x]=val[x],mp[x]=x;
  else if (mx[ch[x][0]]>mx[ch[x][1]]) mx[x]=mx[ch[x][0]],mp[x]=mp[ch[x][0]];
       else mx[x]=mx[ch[x][1]],mp[x]=mp[ch[x][1]];
}

void rotate(int x,bool f)
{
  int y=pre[x];
  ch[y][!f]=ch[x][f];
  pre[ch[x][f]]=y;
  ch[x][f]=y;
  if (rt[y]) rt[y]=0,rt[x]=1;
  else ch[pre[y]][ch[pre[y]][1]==y]=x;
  pre[x]=pre[y];
  pre[y]=x;
  pushup(y),pushup(x);
}

void Push(int x)
{
  if (!rt[x]) Push(pre[x]);
  pushdown(x);
}

void Splay(int x)
{
  Push(x);
  while(!rt[x])
  {
    if (rt[pre[x]]) rotate(x,ch[pre[x]][0]==x);
    else
    {
      int y=pre[x],z=pre[pre[x]];
      bool f=(ch[z][1]==y);
      if (ch[y][f]==x) rotate(y,!f),rotate(x,!f);
      else rotate(x,f),rotate(x,!f);
    }
  }
  pushup(x);
}

void access(int x)
{
  int y=0;
  do
  {
    Splay(x);
    rt[ch[x][1]]=1,rt[ch[x][1]=y]=0;
    pushup(x);
    x=pre[y=x];
  }while(x);
}

void move(int x)
{
  access(x);
  Splay(x);
  reverse(x);
}

void link(int ed,int a,int b)
{
  move(a);
  move(b);
  pre[a]=pre[b]=ed;
}

void cut(int ed,int a,int b)
{
  move(ed);
  access(ed);
  Splay(a),Splay(b);
  pre[a]=pre[b]=0;
}

int find_root(int x)
{
  int now=x;
  while(ch[now][0]) now=ch[now][0];
  return now;
}

bool check(int x,int y)
{
  int rx,ry;
  access(x);Splay(x);rx=find_root(x);
  access(y);Splay(y);ry=find_root(y);
  return rx==ry;
}

void query(int x,int y,int &mxd,int &mxi)
{
  move(x);
  access(y);
  Splay(y);
  mxd=mx[y];
  mxi=mp[y];
}

void work()
{
  sort(e+1,e+m+1,cmp);
  for(int i=1;i<=n+m;i++)
  {
    rt[i]=1;mx[i]=val[i]=0;mp[i]=i;
    if (i>n) mx[i]=val[i]=e[i-n].b;
  }

  for(int i=1;i<=m;i++)
  {
    int mxd,mxi;
    if (check(e[i].x,e[i].y))
    {
      query(e[i].x,e[i].y,mxd,mxi);
      if (mxd>e[i].b)
      {
        cut(mxi,e[mxi-n].x,e[mxi-n].y);
        link(n+i,e[i].x,e[i].y);
      }
    }
    else link(n+i,e[i].x,e[i].y);
    if (check(1,n))
    {
      query(1,n,mxd,mxi);
      ans=min(ans,e[i].a+mxd);
    }
    if (e[i].a>ans) break;
  }
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
    scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);

  work();

  if (ans==inf) printf("-1");
  else printf("%d",ans);
  return 0;
}