[NOIP 2010 향상 팀] 범인 수감.

제목 에서 제 시 된 관 계 는 무 방향 도 를 만 드 는 것 이 어렵 지 않다. 제목 의 요 구 는 무 방향 도 중의 점 을 두 부분 으로 나 누 어 이 두 부분 에서 서로 연 결 된 변 을 삭제 하고 삭 제 된 그림 의 변 권 최대 치 를 구 하 는 것 이다. 알고리즘 하 나 는 먼저 변 권 에 따라 어 릴 때 부터 정렬 까지 모든 변 을 욕심 내 어 고찰 하여 작은 '충돌 사건' 이 발생 하도록 하 는 것 이다.(즉, 이 두 결점 을 같은 부분 에 그 은 다음 에 이 변 을 삭제 해서 하나의 이분 도 를 구성 할 수 있 는 지, 만약 에 줄 이 된다 면 답 은 마지막 에 삭 제 된 이 변 의 변 권 이다. 그렇지 않 으 면 하나의 이분 도 를 형성 할 때 까지 계속 삭제 해 야 한다. 그러나 본 문제 N 과 M 의 수치 가 매우 크다. 이런 방법 은 모든 데 이 터 를 통과 할 수 있 을 까? 이런 알고리즘 의 시간 복잡 도 는 O (n * (n + m) 이다.모든 데 이 터 를 통과 할 수 없습니다. 최적화 가 필요 합 니 다. 문제 풀이 의 최대 치가 가장 적 고 cj 의 범 위 를 명 확 히 규정 하여 2 분 의 답 을 생각 합 니 다. 그러므로 [0, 10 ^ 9] 내 2 분 의 답 을 원 도 검사 에 가 져 와 가능 한 지 확인 하면 됩 니 다. 실현 시 BFS () 에 매개 변수 p, BFS (s, p) 를 추가 합 니 다.s 를 원점 으로 하여 모든 변 권 이 p 보다 큰 점 과 연결 되 어 2 분 의 그림 을 만 들 수 있 는 지 를 나타 낸다.(우리 학 교 는 STL 대열 이 느 려 서 손 으로 쓴 대열)

#include
#include
#include
#include
#include
#define maxn 20005
using namespace std;
int n,m;
vector<int>g[maxn],w[maxn];
int color[maxn];
int q[maxn],front,rear;

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back(b);
        w[a].push_back(c);

        g[b].push_back(a);
        w[b].push_back(c);
    }

}



bool BFS(int s,int p)
{
    rear=front=1;
    q[rear++]=s;
    color[s]=1;

    while(front!=rear)
    {
        int i=q[front++];
        for(int k=0;kint j=g[i][k],c=w[i][k];
            if(c<=p)continue;
            if(color[j]==color[i])return 0;
            if(color[j]==0)
            {
                color[j]=3-color[i];
                q[rear++]=j;
            }
        }
    }
    return 1;
}

bool check(int p)
{
    memset(color,0,sizeof(color));
    int ok=1;
    for(int i=1;i<=n;i++)if(color[i]==0)
    {
        ok=BFS(i,p);
        if(!ok)return false;
    }
    return true;
}
void solve()
{
    int B=0;
    for(int i=1;i<=n;i++)
    for(int k=0;kint A=0,ans;
    while(A<=B)
    {
        int C=(A+B)/2;
        if(check(C))
        {
            ans=C,B=C-1;
        }
        else
        {
            A=C+1;
        }
    }

    printf("%d",ans);
}

int main()
{
    //freopen("my.in","r",stdin);
    //freopen("my.out","w",stdout);
    init();
    solve();
}