BZOJ3362 [Usaco 2004 Feb] Navigation Nightmare 탐색 악몽

제목 대의: 자전거 뇌보.
사고방식: 두 차원의 권한을 유지하고 수집하면 된다.
제목에 대한 한 무더기의 관계에 주의하라. 우리는 반드시 두 쌍의 관계를 추가해야 한다.
Code: #include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std;
#define N 40010 int n, m; struct UnionSet {      int root[N], dis[N];      void reset() {          int i;          for (i = 1; i <= n; ++i)              root[i] = i, dis[i] = 0;      }      int find( int x) {          static int stack[N];          int top = 0;          for (; x != root[x]; x = root[x])              stack[++top] = x;          for ( int i = top - 1; i >= 1; --i)              dis[stack[i]] += dis[stack[i + 1]], root[stack[i]] = x;          return x;      } }Set[2];
#define K 10010 struct Ask {      int u, v, tclock, lab;      void read( int _) {          lab = _;          scanf ( "%d%d%d" , &u, &v, &tclock);      }      bool operator < ( const Ask &B) const {          return tclock < B.tclock;      } }S[K]; int ans[K];
#define M 40010 int u[M], v[M], d[M]; bool vec[M];
#define _abs(x) ((x)>0?(x):-(x))
int main() {      #ifndef ONLINE_JUDGE      freopen ( "tt.in" , "r" , stdin);      #endif           scanf ( "%d%d" , &n, &m);           register int i, j;           int a, b, x;      char s[10];      for (i = 1; i <= m; ++i) {          scanf ( "%d%d%d%s" , &a, &b, &x, s);          d[i] = x;          if (s[0] == 'E' )              u[i] = a, v[i] = b, vec[i] = 0;          else if (s[0] == 'W' )              u[i] = b, v[i] = a, vec[i] = 0;          else if (s[0] == 'N' )              u[i] = a, v[i] = b, vec[i] = 1;          else              u[i] = b, v[i] = a, vec[i] = 1;      }           int Q;      scanf ( "%d" , &Q);      for (i = 1; i <= Q; ++i)          S[i].read(i);      sort(S + 1, S + Q + 1);           Set[0].reset(), Set[1].reset();           int ra, rb;      j = 1;      for (i = 1; i <= m; ++i) {          ra = Set[vec[i]].find(u[i]);          rb = Set[vec[i]].find(v[i]);          Set[vec[i]].root[ra] = rb;          Set[vec[i]].dis[ra] = d[i] + Set[vec[i]].dis[v[i]] - Set[vec[i]].dis[u[i]];                   ra = Set[1 - vec[i]].find(u[i]);          rb = Set[1 - vec[i]].find(v[i]);          Set[1 - vec[i]].root[ra] = rb;          Set[1 - vec[i]].dis[ra] = Set[1 - vec[i]].dis[v[i]] - Set[1 - vec[i]].dis[u[i]];                   for (; S[j].tclock == i; ++j) {              ra = Set[0].find(S[j].u), rb = Set[0].find(S[j].v);              if (ra != rb) {                  ans[S[j].lab] = -1;                  continue ;              }              ans[S[j].lab] += _abs(Set[0].dis[S[j].u] - Set[0].dis[S[j].v]);              ra = Set[1].find(S[j].u), rb = Set[1].find(S[j].v);              if (ra != rb) {                  ans[S[j].lab] = -1;                  continue ;              }              ans[S[j].lab] += _abs(Set[1].dis[S[j].u] - Set[1].dis[S[j].v]);          }      }           for (i = 1; i <= Q; ++i)          printf (

"%d
"

, ans[i]); return 0; }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

BZOJ3362 [Usaco 2004 Feb] Navigation Nightmare 탐색 악몽

좋은 웹페이지 즐겨찾기