[병 찰 집 - 보 집 법] 분 기숙사 + 먹이 사슬

UPC 2020 년 봄 혼성 개인 훈련 5.14 일장
시간 제한: 1 Sec 메모리 제한: 128 MB 제목 설명 A 학 교 는 신기 한 숙박 제 도 를 가지 고 남녀 기숙 사 를 가리 지 않 고 모든 n 명의 학생 들 이 두 개의 기숙사 건물 로 통일 되 었 다.젊은이 로 서 학생 들 사이 에 애모 의 정 이 생기 는 것 은 정상이다.우 리 는 연모 치 로 두 학생 간 의 연모 정 도 를 나타 낸다. 만약 에 두 명의 연모 치가 c 인 학생 이 같은 기숙사 건물 에 배치 되면 그들 이나 그들 이 함께 있 고 영향력 이 c 인 조기 연애 사건 을 초래 할 것 이다.매년 말 정교 처 주임 인 당신 은 모든 조기 연애 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 을 만들어 교장 에 게 보고 합 니 다.공무 가 바 쁜 교장 은 리스트 에 있 는 첫 번 째 사건 의 영향력 만 보 러 갈 뿐 영향 이 크다 면 정교 처 주임 경질 을 검토 할 것 이다.n 명의 학생 간 의 애모 관 계 를 상세히 살 펴 본 후 스트레스 를 많이 받는다.학생 들 을 두 개의 기숙사 로 합 리 적 으로 나 누 어 조기 연애 사건 의 영향력 이 비교적 작 아 자신의 관직 을 지 켜 야 한다.같은 기숙사 건물 에 있 는 두 사람 사이 에 연모 관계 가 있다 고 가정 하면 그들 은 반드시 이 해 어느 때 에 함께 있 을 것 이다.그렇다면 교장 이 볼 수 있 는 그 조기 연애 사건 의 영향력 이 가장 작 을 까?이 최소 치 는 얼마 입 니까?첫 번 째 줄 의 정수 n 과 m 를 입력 하면 학생 의 수 와 애모 관계 의 대 수 를 나 타 냅 니 다.다음 m 행 에서 각 행위 의 3 개의 정수 ai, bi, ci 는 학생 ai 와 bi 사이 에 연모 관계 가 있 음 을 나타 내 고 연모 치 는 ci 이다.데이터 보증 1 ≤ ai ≤ bi ≤ n, 0 출력 출력 1 개 수 를 합 리 적 으로 배정 하기 위해 교장 이 본 그 조기 연애 사건 의 최소 영향력.만약 조기 연애 사건 이 발생 하지 않 았 다 면, 출력 0.샘플 입력 4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 샘플 출력 3512 알림 100% 데이터, n ≤ 20000, m ≤ 100000.문제 풀이 방향: 여기 서 아주 교묘 하 게 집중 보 집 법 으로 할 수 있 습 니 다. 사례 를 들 어 보 세 요. 먼저 연모 치 에 대한 내림차 순 으로 배열 되 고 큰 것 부터 작은 것 까지 첫 번 째 와 앞의 관계 가 모순 되 는 것 을 만 나 직접 출력 할 수 있 습 니 다. 그렇지 않 으 면 출력 0 이 좋 습 니 다. 코드 에서 사례 로 다시 구체 적 으로 설명 하 세 요. AC 소스:

/**
	     ，     ：
	1 2 28351
	3 4 12884
	1 3 6618
	2 3 3512
	1 4 2534
	2 4 1805
	1 2    ，3 4    ，1 3    ；2 3    ，            ，
	        ，             ，
	               ，  i i+n        ，             ，     ，1 2    ，  1 6   ，2 5   ；
	3 4    ，  3 8   ，4 7   ；1 3    ，  1 7   ，3 5   ；
	             1 4 6 7，2 3 5 8         ，   1 4 ，           ，
	         ，     
**/
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
typedef pair<int,int> PII;
priority_queue<int,vector<int>,greater<int> >q;
int n,m;
int pre[maxn];
struct node{
    int l,r,w;
}a[maxn];
bool cmp(node x,node y){
    return x.w>y.w;
}
int Find(int x){
    if(x==pre[x]) return x;
    else return pre[x]=Find(pre[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n;i++) pre[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        if(Find(a[i].l)==Find(a[i].r))   ///                 
        {
            printf("%d",a[i].w);
            return 0;
        }
        else{
            pre[Find(a[i].l+n)]=Find(a[i].r);
            pre[Find(a[i].r+n)]=Find(a[i].l);
        }
    }
    puts("0");   ///       0
    return 0;
}

여기에 예 제 를 하나 더 첨부 하여 전송 문 사고방식 1: 그리고 집합 보집 법 AC 소스 를 찾 습 니 다.

#include
using namespace std;
const int maxn = 1e6+ 7;
int n,k,ans;
int pre[maxn];   ///  1：         2：       3：  
int Find(int x){
    if(pre[x]==x) return x;
    else return pre[x]=Find(pre[x]);
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=3*n;i++) pre[i]=i;
    while(k--){
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        if(d==1){
            if(Find(x+n)==Find(y)||Find(x)==Find(y+n)) ans++;
            else pre[Find(x)]=Find(y),pre[Find(x+n)]=Find(y+n),pre[Find(x+2*n)]=Find(y+2*n);
        }
        else{
            if(Find(x)==Find(y)||Find(x)==Find(y+n)) ans++;
            else pre[Find(x+n)]=Find(y),pre[Find(x+2*n)]=Find(y+n),pre[Find(x)]=Find(y+2*n);
        }
    }
    cout << ans;
    return 0;
}

사고 2: 일반 및 검색 집합 + 사고 AC 소스:

#include 
using namespace std;
const int maxn = 1e6 +7;
int n,m;
int pre[maxn],d[maxn];
int ans=0;
int c,x,y;
int Find(int x){
    if(pre[x]!=x)
    {
        int t=Find(pre[x]);
        d[x]+=d[pre[x]];
        pre[x]=t;
    }
    return pre[x];
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) pre[i]=i;
    while(m--){
        cin >> c >> x >> y;
        if(x>n||y>n) ans++;
        else{
            int fx=Find(x),fy=Find(y);
            if(c==1)
            {
                if(fx == fy && (d[x]-d[y])%3) ans++;
                else if(fx != fy)
                {
                    pre[fx]=fy;
                    d[fx]=(d[y]-d[x])%3;
                }
            }
            else{
                if(fx == fy && (d[x]-d[y]-1)%3) ans++;
                else if(fx != fy)
                {
                    pre[fx]=fy;
                    d[fx]=(d[y]-d[x]+1)%3;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

모든 땀, 모든 노력 이 저 버 리 지 않 기 를 바 랍 니 다 ~ 화 이 팅 하 세 요 소년