E. Egor in the Republic of Dagestan(DAG 최단로+dp) 상세 정보

https://codeforces.com/contest/1407/problem/E
제목: 방향도를 주고 변마다 유형(0 또는 1)이 있다. 어떤 유형의 도시는 어떤 유형의 변으로만 갈 수 있다. 각 도시에 유형(0/1)을 지정해야 한다. 1에서 n까지의 최단거리가 가장 길고 심지어 1까지 n에 도달할 수 없다.
사고방식: 생각할 때 dp인 것 같고 반대로 가장자리를 만들어야 한다.이 문제는 꽤 오랫동안 보충했다.
우선 이것은 dp라는 것을 명확히 해야 한다. 그러면 dp는 정상적으로 정향으로 시작하지만 정향은 처리하기 어렵다. 왜?
예를 들어 1---(0,1)---->2----1(1,0)-------->3이 1에서 2노드로 옮겼을 때 2노드가 0/1을 얻으면 뒤에 있는 2뒤의 변권을 결정하고 2이 점에서 마지막에 어떤 색을 취해야 할지 잘 정하지 못한다.
|------(1,0)------->4
그러나 반대로 변을 만들면 변권 구조점의 색깔을 보장할 수 있다.예컨대
그리고 이 문제는 한 점이 동시에 1과 0으로 업데이트되어야만 이 그림이 반드시 최종적으로 연결될 수 있다는 것을 발견할 수 있다.
예를 들어 나 2라는 노드가 반대편에 0밖에 없다면 내가 그림에서 조작할 때 1이라고 하면 마지막에 정답은 -1이라고 할 수 있다.
그럼
b[x]: x점은 검은색이고 x점까지의 최단길이다.
w[x]: x점이 흰색일 때 x점의 최단로입니다.
이 두 개는 아까의 유도에서 얻을 수 있다.한 점이 w[x]와 b[x]에 모두 업데이트되어야 마지막에 종점에 도착할 수 있기 때문이다(반사 종점은 1번 노드이다)
그리고 이때 변권은 01이고 직접 bfs로 한다.
bfs이기 때문에 한 점을 먼저 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루 두루
그리고 점 하나가 0과 1에 두 번 갱신되기 때문에vis[]로 0과 1의 b[]/w[]에서 갱신되었는지 여부를 판정할 수 없습니다. 왜냐하면 갱신된 것은 갱신하지 않기 때문입니다.
그럼 이거 두 개만 빼도 돼요?
예를 들어 나는 b[x]=min(b[x], b[y]+1/w[y]+1)을 사용한다.
이 b[x]는 0x3f3f3f3f로 초기화되기 시작합니다.b[x]는 b[y]+1과 w[y]+1의 작은 것이 된다.
x--->z일 때 b[x]+1과 w[x]+1의 더 작은 업데이트 b[z], w[z]를 사용한다.
근데 사실은 아니야.제목은 최단로를 더 크게 만든다. 여기서 노드 x의 선택은 b[y]와 w[y] 중 더 큰 것을 선택하여 갱신해야 한다. 이렇게 하면 갱신된 최단로가 더 크다는 것을 보장한다.그래서 dp[x]가 하나 더 필요합니다.
dp[x] 설정: x를 임의의 색으로 하고 x점에 도달할 때의 최단로;
다음으로 전송:
b[y]=min(b[y],dp[x]+1);
w[y]=min(w[y],dp[x]+1);
dp[y]=max(w[y],b[y]);
dp[1]는 마지막으로 무한으로 1시까지 갈 수 있는지 없는지를 판정한다.만약 w[x]>=b[x]--->가 1을 출력한다면 그렇지 않으면 0이다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define debug(a) cout<g[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n>>m;
  for(LL i=1;i<=m;i++){
  	LL x,y,c;cin>>x>>y>>c;
  	g[y].push_back({x,c});
  }
  memset(w,0x3f,sizeof(w));
  memset(b,0x3f,sizeof(b));
  memset(dp,0x3f,sizeof(dp));
  w[n]=b[n]=dp[n]=0;
  queueq;
  q.push(n);
  while(!q.empty())
  {
  	LL t=q.front();q.pop();
	for(LL i=0;in) 
  {
  	cout<=b[i]) cout<<1;
		else cout<<0;	
	}
  }
  else{
  	cout<=b[i]) cout<<1;
		else cout<<0; 	
	}
	cout<

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

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

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

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

E. Egor in the Republic of Dagestan(DAG 최단로+dp) 상세 정보

좋은 웹페이지 즐겨찾기