평론 차분 구속 시스템

4079 단어 알고리즘템 플 릿
계차 제약 시스템
프로필:
  • 배경 은 당신 에 게 몇 개의 부등식 을 주 는 것 입 니 다. 예 를 들 어 xi - xj ≤ b x i - x j ≤ b 는 x 의 존재 성 이나 최 적 화 를 판단 해 야 합 니 다.
  • 차이 점 제약 시스템 은 바로 이 문제 로 그림 이론 문제 로 전환 되 고 최 단 로 를 달 려 서 환 을 판단 하거나 최 적 거리 (최 적 화) 를 구 하 는 것 이다.
  • 여기 서 전환 하 는 원 리 는 삼각형 부등식, 즉 d (v) - d (u) ≤ cost (u, v) d (v) - d (u) ≤ c o s t (u, v) 로 하나의 비용 으로 cost (u, v) c o s t (u, v) 의 변 (u, v) (u, v) (u, v) (u, v) 로 만 들 수 있다.

    • 일반적인 동작:
  • 주제 의 의미 에 따라 부등식 을 찾 아 그림 을 만든다. (특히 주의: 문제 중의 숨겨 진 조건, 이것 은 매우 관건 적 이다) 그리고 이미 알 고 있 는 결론 에서 2 급 결론 을 내 린 부등식 으로 더욱 우수한 건축 변 을 만들어 야 할 수도 있다.
  • 판 환: 일부 문 제 는 그림 을 작성 한 후에 가장 좋 은 해 가 존재 하지 않 고 무한 감소 / 커지 는 네 거 티 브 링 / 정 환 이 존재 합 니 다. SPFA S P F A 를 이용 하여 대열 에 들 어 가 는 횟수 를 판단 해 야 합 니 다. 주의 하 세 요. 네 거 티 브 링 을 판단 할 때 Dijkstra D i j k s t a 를 사용 해 서 는 안 됩 니 다.
  • 최 치 거리 (최 적 화): ximax x i m a x 를 구 하 는 것 이 가장 짧 은 길 입 니 다.ximin x i m i n 을 구 하 는 것 은 가장 긴 길 을 구 하 는 것 이거 나 변 권 을 마이너스 로 바 꿀 수도 있 고 가장 짧 은 길 을 구 할 수도 있다.
  • 건축 도: ximin x i m i n 을 구 할 때 가장 긴 길 을 구 할 때 부등식 을 d (v) ≥ d (u) + k d (v) ≥ d (u) + k 로 바 꾸 면 k k k 의 변 (u, v) (u, v) 을 만 드 는 것 이다.마찬가지 로 ximax x i m a x 를 구 할 때 최 단 로 를 구 하 며 부등식 을 d (v) ≤ d (u) + k d (v) ≤ d (u) + k, 즉 k k k 의 변 (u, v) (u, v) 으로 전환한다.주의, 때로는 제목 이 d (v) < d (u) + k d (v) < d (u) + k 또는 d (v) > d (u) + k d (v) > d (u) + d (u) + k 만 제시 할 때, 이 때 는 좀 줄 여 등호, 즉 d (v) - d (u) ≤ k - 1 d (v) - d (u) ≤ k - 1 또는 d (v) - d (u) ≥ k + 1 을 가 져 와 야 한다.
  • 또한 그림 을 만 들 때 소스 S, S 연결 도 에 있 는 모든 점 을 설치 하고 변 권 은 0 으로 그림 의 연결 성 을 확보한다.

    • 코드 (템 플 릿):
    판 환:
    queue<int>Q;
int dis[N];
char vis[N];
int cnt[N];

void SPFA(){
    while(!Q.empty())Q.pop();
    memset(dis,0x3f3f3f3f,sizeof(dis));//      ，  ，    ，dis  -INF
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));

    Q.push(S);//  
    dis[S]=0; 
    vis[S]=1;
    cnt[S]=1;

    while(!Q.empty()){
        int x=Q.front();Q.pop();
        vis[x]=0;
        for(int i=0;iint)E[x].size();++i){
            int y=E[x][i].to;
            if(dis[y]>dis[x]+E[x][i].cost){//      ，  ，  max，     
                dis[y]=dis[x]+E[x][i].cost;
                if(!vis[y]){
                    Q.push(y);
                    vis[y]=1;
                    if(++cnt[y]>K)return 0;//  K     ，       K ，     ，    
                }
            } 
        }
    }
    return 1;
}

    가장 좋 은 방법:
    일반적으로 판 환 (판 해 의 존재 성) 과 동시에 가장 좋 은 해 를 구 했다. 해 가 있 으 면 출력 이다. 그렇지 않 으 면 보통 impossible (제목 에 따 르 면) 이다.여 기 는 더 이상 군말 하지 않 겠 다.
    Summary:
  • 개인 감각 차이 점 제약 시스템 은 비교적 인기 가 없 는 지식 점 이 고 응용 범위 가 비교적 좁다.
  • 부등식 이 어야 합 니 다. 이 알고리즘 을 사용 하 는 지 여 부 를 판단 하 는 관건 입 니 다.
  • 또한 가장 짧 은 길이 기도 하 다. 도 론 문제 에서 일부 문 제 는 더 많은 점 수 를 얻 을 수 있다.
    • CSS3 :nth-of-type() Selector
    #Day19 - 정렬과 정렬, 역순과 역순의 성능 비교

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage