프 리 젠 테 이 션 및 응용 (oj 예제 설명 포함)

Matroid
introduction
이 글 은 주로 의 진과 그 응용 을 쓴다.의 진의 등장 은 욕심 산법 때 문 이 아니 지만 욕심 산법 에서 매우 중요 한 위 치 를 차지한다.
일부 개념

선형 관련 과 선형 은 무관 하 다. 선형 대수 에서 벡터 공간의 한 요소 에서 벡터 가 없 으 면 유한 한 다른 벡터 의 선형 조합 으로 표시 할 수 있 으 면 선형 무관 또는 선형 독립 (linearly independent) 이 라 고 부 르 고 반대로 선형 관련 (linearly dependent) 이 라 고 부른다.

집합 족: 설정 {Eα：α∈I E α ： α 8712 ° I {E \ alpha: \ alpha \ \ in I}} 은 집합 E 입 니 다.α E α {E \ alpha} 는 원소 의 집합 으로 집합 을 원소 로 하 는 집합 을 흔히 집합 류 또는 집합 족 이 라 고 부른다.α α {\ alpha} 을 지표 라 고 하고 I I {I} 은 전체 지표 로 구 성 된 지표 집합 이다.

프 리 젠 테 이 션 (matroid): 하나의 프 리 젠 테 이 션 은 다음 과 같은 조건 을 만족 시 키 는 순서 M = (S, T) 입 니 다.

S 는 유한 집합 이 고 T 는 S 의 비 빈 부분 집합 이 며 이런 부분 집합 을 독립 부분 집합 이 라 고 부른다.

유전성 이 있 습 니 다. 즉, B * 8712 ° * 8712 ° {\ in} T 이 고 A * 8838 ° {\ substeq} B 이면 A * 8712 ° * 8712 ° {\ in} T.

교환 성 이 있 습 니 다. A * 8712 ° * 8712 ° {\ in} T, B * 8712 ° * 8712 ° {\ in} T, 그리고 | A | 8712 ° * 8712 ° {\ in} B - A 는 A * 8746 ° * 8746 ° {\ cup} {x} * 8712 ° {\ in} T 를 교환 성 을 만족 시 킵 니 다.

그림 작성 진: 그림 작성 진 MG = (SG, TG) M G = (S G, T G) MG = (S G, T G) 이것 은 주어진 무방 향도 G = (V, E) 위 에 정 의 됩 니 다.

SG S G S_G 는 E, 즉 G 의 변 집합 으로 정의 합 니 다.

A 가 E 의 부분 집합 이 라면 A * 8712 ° TG * 8712 ° T G \ \ in TG 는 A 만 원 이 없다 고 생각 합 니 다.즉, 한 조 의 변 A 변 은 독립 적 이 고 서브 맵 GA G GA = (V, A) 하나의 숲 을 형성한다.

확장: 프 리 젠 테 이 션 M = (S, T) 을 지정 합 니 다. 만약 에 하나의 집합 A * 8712 ° 8712 ° \ inT 와 하나의 요소 x * 8713 ° 8713 ° < br > otinA 에 대해 x 를 A 에 가입 하면 독립 적 인 성질 을 유지 할 수 있 습 니 다. 그러면 x 는 A 의 확장 이 라 고 합 니 다.프 리 젠 테 이 션 의 독립 부분 집합 에 대해 확장 이 존재 하지 않 으 면 가장 크다 고 한다.

가중 작성 진: 만약 에 하나의 프 리 젠 테 이 션 M = (S, T) 이 하나의 가중치 함수 w 와 관련 되면 모든 요소 x * 8712 ° 8712 ° \ inS 에 0 가중치 w (x) 보다 엄격 한 권한 을 부여 하면 프 리 젠 테 이 션 M 은 가중 되 었 다 고 합 니 다.구 화 를 통 해 가중치 함수 w 를 S 의 모든 키 집합 A 로 확대 할 수 있 습 니 다. 예 를 들 어 w (e) 는 그림 작성 MG M G M 을 표시 합 니 다.G 중 변 e 의 가중치, 그러면 w (A) 는 A 중의 모든 변 의 가중치 의 합 을 집합 하 는 것 을 나타 낸다.

두 가지 정리

만약 G = (V, E) 가 무방 향도 라면 MG = (SG, TG) M G = (S G, T G) MG = (S G, T G) 는 의 진 이다.

의 진 에서 모든 최대 독립 부분 집합 은 같은 크기 를 가진다.

가중 작성 진의 욕심 알고리즘
욕심 산법 을 사용 하여 가장 좋 은 문 제 를 얻 을 수 있 는 많은 문 제 는 가중 작성 진 에서 가장 큰 가중치 독립 부분 집합 을 찾 는 문제 로 형식 화 될 수 있다.즉, 가중 의 진 M = (S, T) 을 지정 합 니 다. 우 리 는 독립 집합 A * 8712 ° 8712 ° \ inT 를 찾 아 W (A) 를 가장 크게 만 들 고 싶 습 니 다.우 리 는 이런 독립 적 이 고 가장 큰 권한 을 가 진 부분 집합 을 의 진의 가장 좋 은 부분 집합 이 라 고 부른다.모든 요소 x * 8712 ° 8712 ° \ inS 의 가중치 가 정확 하기 때문에 가장 좋 은 부분 집합 은 반드시 최대 독립 자신 입 니 다. 이것 은 항상 A 를 가능 한 한 크게 하 는 데 도움 이 됩 니 다.
다음은 모든 가중 작성 진 에 적용 되 는 알고리즘 을 제시 합 니 다.

GREEDY(M,w)
    A={}
    sort M.S into monotonicially decreasing order weight w
    for x in M.S, taken in monotonically decreasing order by weight w(x)
        if A+{X} in M.T
            A=A+{X}
    return A

의 진의 욕심 알고리즘 의 정확성 도 greedy choice property 와 optimal substruture 두 가지 측면 에서 증명 되 었 다.다음은 우리 가 각각 증명 한다.

greedy choice property 인용 1. (의 진 은 욕심 선택 성질 을 가지 고 있다) 가정 M = (S, T) 은 가중 의 진 이 고 가중 함수 w 이 며 S 는 가중치 단조 로 운 체감 순서에 따라 순 위 를 매 겼 다.x 는 S 에서 {x} 독립 된 요 소 를 만족 시 키 는 첫 번 째 요소 입 니 다 (존재 한다 면).이러한 x 가 존재 한다 면 S 의 가장 좋 은 부분 집합 A 는 x 를 포함한다.증명: B 가 가장 좋 은 부분 집합 이 라 고 가정 합 니 다. A 는 가장 좋 은 부분 집합 이 아 닙 니 다. B 는 x 를 y 로 바 꿉 니 다. x 는 내림차 순 정렬 의 첫 번 째 요소 이기 때문에 w (x) > w (y), B = A - {x} + {y} 그래서 w (B) = w (A) + w (y) < w (A) 가 성립 되 지 않 는 다 고 가정 합 니 다. 가장 좋 은 부분 집합 은 반드시 x 를 포함 합 니 다.

optimal substructure 인용 2. 령 M = (S, T) 은 가중 의 진 이 고 x 는 S 에서 처음으로 greedy 알고리즘 에 의 해 선 택 된 요소 이다. 그 다음 에 x 를 포함 한 최대 가중치 독립 부분 집합 을 찾 는 문 제 는 가중 의 진 M '= (S', T') 의 가장 큰 가중치 독립 부분 집합 을 찾 는 문제 로 귀결 된다. 그 중에서:

S’={y ∈ ∈ \inS:{x,y ∈ ∈ \inT}}

T’={B ⊂ ⊂ \subsetS-{x}:B ∪ ∪ \cup{x} ∈ ∈ \inT}

증명: 만약 에 A 가 M 의 임의의 x 를 포함 하 는 최대 가중치 독립 부분 집합 이 라면 A '= A - {x} 은 M' 의 독립 부분 집합 입 니 다.반면 모든 독립 부분 집합 A '는 M 의 독립 부분 집합 A = A' * 8746 ° 8746 ° \ cup {x} 을 생 성 할 수 있 습 니 다.두 가지 상황 에 대해 모두 w (A) = w (A ') + w (x) 가 있 기 때문에 M 의 x 를 포함 하 는 최대 가중치 부분 집합 은 반드시 M' 의 최대 가중치 부분 집합 을 생 성 할 것 이 고 그렇지 않 으 면 여전 하 다.
Example
최소 생 성 트 리 알고리즘
최소 생 성 트 리 문 제 는 무방 향 그림 에서 진행 된다.무방 향도 G = (V, E).

우 리 는 이러한 M = (S, T) 을 정의 할 수 있다.

S 는 변 집 E

L = {x: x ⊆ ⊆ \ subseteq E 및 x 로 구 성 된 그림 무 환}

다음은 이 M 이 진 을 작성 하 는 조건 을 만족 시 키 는 것 을 증명 한다. 똑 같이 무 방향 도 는 진 을 작성 하 는 것 임 을 증명 한다.

다음 에 우 리 는 가중 함 수 를 정의 하기 시 작 했 습 니 다. w (x) 는 변 x 의 길 이 를 나타 내 고 w '(x) = w0 - w (x), 그 중에서 w0 = max (w (x) + 1 로 w' (x) 가 0 보다 크 고 w '(x) 가 가장 클 때 w (x) 는 최소 치 를 얻 었 습 니 다.

그 다음 에 우 리 는 S 를 w '(x) 에 따라 오름차 순 으로 정렬 할 것 이다. 만약 에 x * 8712 ° 8712 ° \ inS 가 A 를 추가 할 수 있다 면 (여기 서 판단 해 야 할 그림 은 고리 가 없다) A = A * 8746 ° 8746 ° \ cup {x}

최대 독립 변 집합 A

획득

Accepted code

// poj 1258
#include
#include
using namespace std;

const int maxn=105;

struct Edge{
    int u,v,w,key;
    Edge(){}
    Edge(int uu,int vv,int ww):u(uu),v(vv),w(ww){
        key= 100000-ww;
    }

    bool operatorconst Edge& obj)const{
        return key>obj.key;
    }
}edge[maxn*maxn];

int f[maxn];

void Init(){
    for(int i=0;iint Find(int x){
    if(f[x]==x){
        return x;
    }else{
        return f[x]=Find(f[x]);
    }
}

void Union(int x,int y){
    int fx=Find(x),fy=Find(y);
    f[fy]=fx;
}


int main(int argc, char const *argv[])
{
    int n;
    while(~scanf("%d",&n)){
        Init();
        for(int i=0;ifor(int j=0;jint w;
                scanf("%d",&w);
                edge[i*n+j]=Edge(i,j,w);
            }
        }

        sort(edge,edge+n*n);

        long long int res=0;
        int cnt=0;

        for(int i=0;i1;i++){
            int u=edge[i].u,fu=Find(u);
            int v=edge[i].v,fv=Find(v);
            int w=edge[i].w;
            if(fu!=fv){
                cnt++;
                res+=w;
                Union(u,v);
                //printf("%d
",w);
            }
        }

        printf("%lld
",res);
    }
    return 0;
}

Referenence

Introduction to algorithm