테마 모음 (지속 업데이트)

0. 병 집
무엇이 병 찰 집 입 니까?그리고 집합 은 트 리 형 데이터 구조 로 서로 교차 하지 않 는 집합 과 조회 문 제 를 처리 하 는 데 사용 된다.일반적인 조작

초기 화 (init)

각 점 이 있 는 집합 을 자신 으로 초기 화하 다.일반적으로 이 절 차 는 이 데이터 구 조 를 사용 할 때마다 한 번 만 실행 되 고 어떤 실현 방식 이 든 시간 복잡 도 는 O (N) 이다.

void init()
{
	for(int i=1;i<=n;i++)
		father[i]=i;
}

찾기 (getfather)

요소 가 있 는 집합, 즉 루트 노드 를 찾 습 니 다.

int getfather(int x)
{
	if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}

여기 서 경 로 를 압축 하 는 방법 으로 i 가 속 한 집합 을 루트 노드 로 바 꾸 면 다음 에 다시 검색 할 때 O (1) 의 시간 안에 결 과 를 얻 을 수 있 습 니 다.

합병 (merge)

두 원소 가 있 는 집합 을 하나의 집합 으로 합치다.일반적으로 합병 하기 전에 두 요소 가 같은 집합 에 속 하 는 지 판단 해 야 한다. 이것 은 위의 '찾기' 작업 으로 이 루어 질 수 있다.

void merge(int a,int b)
{
	int f1=getfather(a);
	int f2=getfather(b);
	if(f1!=f2)
	{
		father[f1]=f2;//   father[f2]=f1;
		    ;
	}
}

권한 을 가지 고 조사 집

검색 (getfather) 을 바탕 으로 최적화:

int getfather(int x)
{
	if(father[x]==x)return x;
    else
    {
    	int t=father[x];//     
    	father[x]=getfather(father[x]);
    	dis[x]+=dis[t];//     x       
    	return father[x];
    }
}

이곳 의 dis 배열 은 각 점 에서 조상 까지 의 거 리 를 나타 낸다.
1. 최소 생 성 트 리
선로 계획 시간 제한: 1 Sec 메모리 제한: 128 MB 제목 은 n 개 마을 간 에 통신 선 로 를 가설 하여 임의의 두 마을 간 에 모두 통신 할 수 있 도록 설명 한다.두 마을 a, b 간 통신 이 가능 하 며, 그들 사이 에 하나의 통신 라인 이 존재 하거나 마을 c 가 존재 하면 a, c 와 b, c 간 에 모두 통신 이 가능 합 니 다.마을 간 에 통신 선 을 가설 하 는 대 가 를 주 고 최소 의 총 대 가 를 구하 다.첫 줄 에 두 개의 정수 n, m 를 포함 하고 마을 수량 과 통신 선 로 를 가설 할 수 있 는 마을 대 수 를 입력 하 십시오.아래 m 줄, 각 줄 의 세 개의 정수 a, b, c 는 마을 a, b 사이 에 선 로 를 가설 하 는 대 가 는 c (마을 은 0 부터 번호) 임 을 나타 낸다.하나의 정수, 최소 총 대 가 를 출력 하 다.샘플 입력 복사

3 3
0 1 1
1 2 1
2 0 3

샘플 출력 복사

2

50% 의 데이터 에 대해 n < = 100, m < = n ^ 2 는 모든 데이터 에 대해 1 < = n < = 10 ^ 5;n - 1 < = m < = 10 ^ 5, 모든 대 가 는 [0, 10 ^ 6] 범위 내 에서 문제 가 해 결 될 것 을 보증 합 니 다.
최소 생 성 트 리 kruskal 알고리즘 + 템 플 릿 문 제 를 찾 습 니 다. WA 의 점 은 출발점 좌표 가 종점 좌표 보다 작 음 을 보장 하 는 것 도 아니 고 선택 father[f1]=f2 또는 father[f2]=f1 도 아 닙 니 다. 마을 대 수 를 읽 을 때 1 부터 m 까지 입 니까? 0 에서 m - 1 까지 입 니까? 마지막 총 대 가 는 long long 형 일 수 있 습 니 다.처음에 나 는 모든 총 대 가 를 [0, 10 ^ 6] 범위 내 에서 91% 의 데 이 터 를 통과 할 수 밖 에 없다 고 잘못 보 았 다.

#include
#include
using namespace std;
typedef struct village
{
    int Start,End,Weight;
}v;
int father[100005];
v vil[100005];
int getfather(int x)
{
    if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}
int cmp(const void*a,const void*b)
{
    v*x=(v*)a;
    v*y=(v*)b;
    return x->Weight-y->Weight;
}
int main()
{
    int n,m,edge=0,a,b,c;
    long long int cost=0;
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n-1;i++)father[i]=i;
    for(int i=0;i<=m-1;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        vil[i].Start=a;
        vil[i].End=b;
        vil[i].Weight=c;
    }
    int f1,f2;
    qsort(vil,m,sizeof(vil[0]),cmp);
    for(int i=0;i<=m-1;i++)
    {
        f1=getfather(vil[i].Start);
        f2=getfather(vil[i].End);
        if(f1!=f2)
        {
            father[f1]=f2;
            edge++;
            cost+=vil[i].Weight;
            if(edge==n-1)break;
        }
    }
    printf("%lld",cost);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:65 ms
    Memory:3852 kb
****************************************************************/

2. 최대 생 성 트 리
sunflower 시간 제한: 1 Sec 메모리 제한: 128 MB 제목 은 작은 N 이 작은 T 집의 화원 에 자주 산책 하 는 것 을 묘사 합 니 다. 작은 T 집의 화원 은 N 개의 긴 정자 와 M 개의 도로 가 정 자 를 연결 하고 있 지만 작은 T 의 화원 은 너무 복잡 합 니 다. 작은 N 은 길 치 로 자주 들 어간 후에 찾 을 수 없 는 길 로 계속 링 안 을 돌 고 있 습 니 다.그래서 작은 N 은 작은 T 에 게 그 중의 일부 길 을 해 바라 기 를 심 어 나머지 길 에 고리 가 생기 지 않도록 해 야 한다.해 바라 기 는 심기 가 불편 하기 때문에 i 번 도로 길이 인 Li 는 Li 개의 해 바라 기 를 심 어야 한다. 그래서 T 는 그 가 최소한 몇 개의 해 바라 기 를 심 어야 작은 N 의 요 구 를 만족 시 킬 수 있 는 지 알 고 싶다.첫 번 째 줄 의 정수 N, M 을 입력 하면 화원 의 정자 수 와 도로 수 를 나타 낸다.다음 M 줄 은 줄 당 3 개의 정수 A, B, C 로 A 와 B 를 연결 하 는 길이 가 C 인 도로 가 있다 는 것 을 나타 낸다.작은 T 가 최소한 심 어야 할 해바라기 수 를 나타 내 는 한 줄 의 정 수 를 출력 합 니 다.샘플 입력 복사

5 5
1 2 5
1 4 4
3 4 3
2 3 2
3 5 1

샘플 출력 복사

2

제시 100% 의 데이터 에 대하 여 1 ≤ N ≤ 10 ^ 5, 1 ≤ M ≤ 2×10 ^ 5, 0 류 는 '파 권 법' 의 원리 에 비해 문 제 는 연관 성 을 바 꾸 지 않 는 전제 에서 매번 가중치 가 가장 작은 변 을 삭제 하고 삭제 할 수 없 을 때 까지 최대 로 트 리 문 제 를 생 성 하 는 것 과 같다.kruskal 알고리즘 의 정렬 방식 을 가중치 에서 작은 순서 로 바 꾸 기만 하면 됩 니 다.

#include
#include
using namespace std;
typedef struct Edge
{
    int Start,End,cost;
}edge;
int cmp(const void*a,const void*b)
{
    edge*x=(edge*)a;
    edge*y=(edge*)b;
    return y->cost-x->cost;
}
edge road[200005];
int father[100005];
int n,m,a,b,c,cnt=0;
int getfather(int v)
{
    if(father[v]==v)return v;
    else return father[v]=getfather(father[v]);
}
int main()
{
    long long int sum=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        road[i].Start=a;
        road[i].End=b;
        road[i].cost=c;
        sum+=road[i].cost;
    }
    qsort(road+1,m,sizeof(road[1]),cmp);//           
    for(int i=1;i<=n;i++)father[i]=i;
    long long int sum1=0;
    int fat1,fat2;
    for(int i=1;i<=m;i++)
    {
        fat1=getfather(road[i].Start);
        fat2=getfather(road[i].End);
        if(fat1!=fat2)
        {
            sum1+=road[i].cost;
            father[fat2]=fat1;
            cnt++;
            if(cnt==n-1)break;
        }
    }
    printf("%lld",sum-sum1);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:128 ms
    Memory:6196 kb
****************************************************************/

3. 연통 도 문제
tunnel 시간 제한: 1 Sec 메모리 제한: 128 MB 제목 은 한 마을 이 자신의 지하철 노선 망 을 구축 하 는 데 착수 하고 있다 는 것 을 설명 한다.마을 은 많은 작은 섬 에 자리 잡 고 있 으 며 작은 섬 사 이 는 터널 이나 다 리 를 통 해 연결된다.지하철 은 기 존의 교량 과 터널 을 바탕 으로 건설 되 었 다.지하철 은 주로 지하 에 있 기 때문에 다 리 를 적 게 쓸 수록 좋다.마을 주민 들 은 지하철 로 만 두 개의 작은 섬 사 이 를 오 가 며 여행 할 수 있 기 를 바란다.다행히도 우 리 는 이 요 구 를 충족 시 킬 터널 과 다리 가 충분 하기 때문에 새로운 터널 이나 다 리 를 건설 할 필요 가 없다.당신 의 임 무 는 이런 지하철 노선 망 을 구축 하려 면 적어도 몇 개의 다 리 를 사용 해 야 한 다 는 것 을 계산 하 는 것 입 니 다.입력 입력 은 K + M + 1 줄 을 포함 합 니 다.첫 줄 은 N, M, K 세 개 를 포함 하 는데 그 중에서 N 은 작은 섬 수량 이 고 M 은 터널 수량 이 며 K 는 교량 수량 이다.아래 M 줄 은 각 줄 에 두 개의 숫자 가 있 는데 해당 하 는 터널 이 연 결 된 작은 섬의 번 호 를 나타 내 고 번 호 는 1 에서 N 까지 이다.K 행 을 내 려 가면 줄 마다 똑 같은 방식 으로 다 리 를 묘사 합 니 다.최소 필요 한 교량 수 를 출력 하 다.샘플 입력 복사

6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6

샘플 출력 복사

2

제시 100% 의 데이터 에 대하 여 1 ≤ N ≤ 10000, 1 ≤ K ≤ 12000, 1 ≤ M ≤ 12000 은 흑체 부분 에서 알 고 있 으 며, 최종 적 으로 얻 은 그림 은 반드시 연통 도 이 므 로 터널 을 진행 하고 수집 하여 약간의 연통 분기 만 얻 고, 연통 분기 수 (각 점 의 조상 노드 는 현재 노드) - 1 을 통계 하면 답 을 얻 을 수 있다.

#include
typedef struct node
{
    int Start,End;
}edge;
edge tunnel[12005];
edge bridge[12005];
int father[10005];
int k,n,m;
int getfather(int x)
{
    if(father[x]==x)return x;
    else return father[x]=getfather(father[x]);
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&tunnel[i].Start,&tunnel[i].End);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d",&bridge[i].Start,&bridge[i].End);
    }
    for(int i=1;i<=n;i++)father[i]=i;
    int f1,f2;
    for(int i=1;i<=m;i++)
    {
        f1=getfather(tunnel[i].Start);
        f2=getfather(tunnel[i].End);
        if(f1!=f2)father[f2]=f1;
    }
    for(int i=1;i<=n;i++)
        if(father[i]==i)cnt++;
    printf("%d",cnt-1);
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:11 ms
    Memory:1344 kb
****************************************************************/

4. 고리 유 무 판단
무선 방송 시간 제한: 2 Sec 메모리 제한: 256 MB 의 한 방송 사 는 한 지역 에 무선 방송 발사 장 치 를 설치 해 야 한다.이 지역 에는 n 개의 작은 마을 이 있 는데 마을 마다 송신기 한 대 를 설치 하고 각자 의 프로그램 을 방송 해 야 한다.그러나 이 회 사 는 FM 104.2 와 FM 98.6 두 밴드 의 권한 만 수 여 받 았 고 같은 밴드 의 발사 기 회 를 이용 해 서로 방해 했다.각 송신기 의 신호 커버 범 위 는 원심, 20km 를 반경 으로 하 는 원형 구역 으로 알려 져 있 기 때문에 20km 이하 의 두 마을 에서 같은 파 도 를 사용 하면 파 단 간섭 으로 프로그램 을 제대로 듣 지 못 한다.현재 20km 이하 의 작은 마을 목록 을 제시 해 이 회사 가 전 지역 주민 들 이 방송 프로그램 을 정상적으로 들 을 수 있 는 지 판단 해 보 자.첫 번 째 행위 의 정수 n, m 를 입력 하 십시오. 각각 작은 마을 의 개수 와 그 다음 20km 이하 의 작은 마을 의 수 입 니 다.다음 m 행 은 줄 당 2 개의 정 수 를 나타 내 며 두 마을 의 거 리 는 20km 이하 (번 호 는 1 부터) 임 을 나타 낸다.출력 이 요 구 를 만족 시 킬 수 있다 면 출력 1, 그렇지 않 으 면 출력 - 1.샘플 입력 복사

4 3
1 2
1 3
2 4

샘플 출력 복사

1

제한 1 ≤ n ≤ 10000 1 ≤ m ≤ 30000 은 주어진 20km 마을 목록 의 공간 특성 을 고려 할 필요 가 없다. 예 를 들 어 삼각형 부등식 을 만족 시 키 는 지, 전달 성 을 이용 하여 더 많은 정 보 를 내 놓 을 수 있 는 지 등 이다.
20km 미 만 을 연결 관계 로 보고 주어진 모든 점 을 얻어 그림 을 만 들 수 있다. 그림 에 고리 가 존재 하지 않 거나 길이 가 짝수 인 고리 가 존재 할 때 요 구 를 만족 시 킬 수 있 고 나머지 상황 에서 요 구 를 만족 시 키 지 못 하기 때문에 문 제 는 고리 와 고리 의 길이 문 제 를 찾 는 것 으로 바 뀌 었 다.회로 에 고리 가 존재 하 는 지 판단 하고 수집 할 수 있 으 며 두 점 (출발점, 종점) 의 조상 결점 이 동시에 하나의 고 리 를 구성 할 수 있다.dis 배열 을 이용 하여 결점 에서 조상 까지 의 거 리 를 기록 하고 한 변 의 두 점 에 대해 규칙 을 찾 아 보면 두 점 에서 조상 까지 의 거리 차이 가 짝수 일 때 현재 의 변 을 더 하면 링 의 길 이 를 홀수 로 얻 을 수 있다.반대로 두 점 에서 조상 까지 의 거리의 차 이 는 홀수 일 때 현재 의 변 을 더 하면 마침 고리 의 길 이 는 짝수 이다.

#include
using namespace std;
int father[10005];
typedef struct Node
{
    int Start,End;
}node;
node town[30005];
int dis[10005]={0};//           
bool cir=false;//      
bool flag=false;//           
//   
int getfather(int x)//     
{
    if(father[x]==x)return x;
    else
    {
        int t=father[x];
        father[x]=getfather(father[x]);
        dis[x]+=dis[t];//          
        return father[x];
    }
}
int main()
{
    int n,m,a,b;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)father[i]=i;//   ，           
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        if(a>b)
        {
            int t=a;
            a=b;
            b=t;
        }
        town[i].Start=a;
        town[i].End=b;
    }
    int f1,f2;
    for(int i=1;i<=m;i++)
    {
        f1=getfather(town[i].Start);
        f2=getfather(town[i].End);
        if(f1==f2)//    ，     
        {
            cir=true;
            if((dis[town[i].Start]-dis[town[i].End])%2==0)flag=true;//       
        }
        else//    
        {
            father[f1]=f2;//     
            dis[f1]=dis[town[i].End]+1-dis[town[i].Start];//    
        }
    }
    if(cir==false)printf("1");//     
    else if(flag==false)printf("1");//           
    else printf("-1");//           
    return 0;
}
/**************************************************************
    Language: C++
    Result:   
    Time:4 ms
    Memory:4816 kb
****************************************************************/