[BZOJ 1006][HNOI 2008]신기 한 나라(현도 최소 염색)

제목 설명
전송 문
해제
참고 자료:http://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html
삼각 관계 만 만족 시 키 기 때문에 관계 에 따라 그림 을 만 든 후 현 도 를 알 수 있다.그러면 문 제 는 현도 의 최소 염색 으로 바 뀌 었 다.
알고리즘 과정:MCS 알고리즘 으로 현도 의 완벽 한 제거 서열 을 구한다.시퀀스 를 완벽 하 게 제거 한 후 한 번 앞으로 염색 하여 점 마다 염색 할 수 있 는 최소 색상 을 줍 니 다.최대 세 알고리즘 Maximum Cardinality Search 는 n 에서 1 까지 순서대로 레이 블(레이 블 i 의 점 은 완벽 하 게 시퀀스 를 제거 하 는 i 번 째)을 줍 니 다.size[i]를 설정 하면 i 번 째 점 이 몇 개의 표 시 된 점 과 인접 해 있 는 지 표시 하고 매번 size[i]의 가장 큰 표 시 된 점 을 선택 하여 표 시 를 합 니 다.
코드

#include
#include
#include
using namespace std;

const int max_n=1e4+5;
const int max_m=1e6+5;
const int max_e=max_m*2;

int n,m,x,y,ans;
int tot,point[max_n],nxt[max_e],v[max_e];
int flag[max_n],size[max_n],color[max_n],pt[max_n]; 

inline void addedge(int x,int y)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    for (int i=n;i>=1;--i)
    {
        int cur=0;
        for (int j=1;j<=n;++j)
            if (!flag[j]&&size[j]>=size[cur])
                cur=j;
        flag[cur]=1; pt[i]=cur;
        for (int j=point[cur];j;j=nxt[j]) size[v[j]]++;
    }
    memset(flag,0,sizeof(flag));
    for (int i=n;i>=1;--i)
    {
        for (int j=point[pt[i]];j;j=nxt[j])
            flag[color[v[j]]]=i;
        color[pt[i]]=1;
        while (flag[color[pt[i]]]==i)
            color[pt[i]]++;
        ans=max(ans,color[pt[i]]);
    }
    printf("%d
",ans);
}

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

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

LeetCode - 503. 다음 더 큰 요소 II (Next Greater Element II) [중간] - 분석 및 코드 (Java)

순환 배열 (마지막 요소 의 다음 요 소 는 배열 의 첫 번 째 요소) 을 지정 하고 모든 요소 의 다음 요 소 를 출력 합 니 다.숫자 x 의 다음 더 큰 요 소 는 배열 에 따라 순 서 를 옮 겨 다 니 는 것 ...

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

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

[BZOJ 1006][HNOI 2008]신기 한 나라(현도 최소 염색)

좋은 웹페이지 즐겨찾기