베 기: 그림 G 에서 하나의 호의 집합 c {f} 을 삭제 하여 S 가 T 로 흐 르 지 못 하 게 하면 이 집합 은 그림 G 의 베 기 가 됩 니 다.C (S, T), S, T 를 점 집 으로 기록 하 다.
정방 향 절단: 집합 c 의 한 아크 f {u, v} (u 지향 v) 에 대해 u * 8712 ° S, v * 8712 ° T 는 정방 향 절단 변 이 됩 니 다.
역방향 절단 변: 집합 c 의 한 아크 f {u, v} (u 지향 v) 에 대해 u * 8712 ° T, v * 8712 ° S 는 역방향 절단 변 이 됩 니 다.
베 는 용량: C {S, T} 의 모든 정방 향 베 는 용량 과 베 는 용량.
최소 베 기: 용량 이 가장 작은 베 기 Ci {S, T} 은 그림 G 의 최소 베 기 입 니 다.
최대 흐름 최소 분할 정리: 그림 G 의 최대 흐름 = ci 의 용량.
기본 모델 1. 최소 충돌 수
모델: 이런 문 제 는 보통 초기 두 개의 집합 으로 모든 사람 이 첫 번 째 로 찬성 / 찬성 하지 않 고 타인 의 정 서 를 배려 하기 위해 '표 와' 비슷 한 행 위 를 하 며 마지막 에 자신의 뜻 을 위반 하 는 사람 이 가장 적다.
구성 방법: ①: S 는 모든 찬성 하 는 방향 으로 연결 되 고 용량 은 1 이다.②: 모든 찬성 하지 않 는 방향 T 는 방향 이 있 고 용량 은 1 이다.③: 모든 친구 간 에 이들 의 의사 가 다 르 면 찬성 하 는 방향 이 찬성 하지 않 는 쪽 은 방향 이 있 고 용량 은 1 이다.즉, 누군가가 자신의 뜻 을 어기 면 베 는 것 이다.최소 로 자 르 면 답 수 이다.
제목: BZOJ 1934, 2768 등.
2. 최대 권 폐 합자 도
정의: 한 그림 에서 우 리 는 일부 점 을 선택 하여 집합 을 구성 하고 V 로 기록 하 며 집합 중의 출 변 (즉, 집합 중의 점 이 밖으로 연 결 된 호) 을 선택 하고 가리 키 는 종점 (호 두) 도 V 에 있 으 면 우 리 는 V 를 닫 힌 그림 이 라 고 부른다.최대 권 폐 합 도 는 모든 폐 합 도 에서 중점 을 모 으 는 가중치 의 합 이 가장 큰 V 로 우 리 는 V 를 최대 권 폐 합 도 라 고 부른다.
모델: ① '무 환 도 (DAG) 문제 가 있 고 사건 간 의 필요 한 조건 관 계 를 나타 낸다. 한 사건 의 발생 에 필요 한 모든 전제 가 발생 해 야 한다.EXP: 수강 신청, 일부 과정 은 다른 과정 을 바탕 으로 해 야 합 니 다. 만약 에 과정 에 점 수 를 매기 면 가장 큰 권 리 를 가 진 폐 합 도 는 이익 이 가장 크 거나 효율 이 가장 높 은 수강 신청 계획 에 대응 해 야 합 니 다.② '동그라미 가 있 는 방향 도.EXP: 프로젝트 분할 문 제 는 프로젝트 간 상호 의존 관계 가 있 고 최대 권 폐쇄 도 로 해결 할 수 있 으 며 가장 먼저 완성 해 야 할 것 을 1 기로 선택 할 수 있 습 니 다.
구성 방법: ①: S 는 모든 정 권 점 에 용량 은 점 권 이다.②: 모든 마이너스 점 은 T 이 고 용량 은 점 권 절대 치 이다.③: 의존 관계 간 의 단 방향 연결, 용량 은 INF (u 를 선택 했다 면 반드시 v 를 선택해 야 한 다 는 뜻 이 고 INF 를 잘 랐 다 면 최소 로 자 르 지 않 았 을 것 이다).보통 정 권 점 은 수익 을 대표 하고 마이너스 점 은 원 가 를 대표 한다.정시 권 과 - 최소 절단 = 답.
증명: 다음 증명 인용 출처
， S ( S) 。
C, S N，T M。
C=M ( S M )+N ( N T )。 (C=x1+y1);( ， )。
N W。
W=N -N 。 (W=x2-y2);
W+C=x1+y1+x2-y2。
y1=y2， W+C=x1+x2;
x1 M ，x2 N 。
x1+x2= ( TOT).
W+C=TOT. W=TOT-C.
。
TOT ， W ， C ， ， S ( S)。 。
제목: BZOJ 1391, NOI 2006 최대 이익, GDKOI 2016 보물 찾기 등.
3. 최소 컷 팅
정의: 방향 이 없 는 (방향 이 있 는) 그림 G 에서 주어진 원점 s 와 종점 t 는 적어도 몇 개의 점 (구체 적 으로 어떤 점 을 삭제 해 야 하 는 지) 을 삭제 하여 s 와 t 가 연결 되 지 않도록 해 야 한다.이 문 제 는 점 연통 도 라 고도 하 는데, 가장 작은 할 집 이 라 고도 한다.
구성 방법: ①: 철거 점, 원 그림 의 중심 점 v 를 v '와 v' 로 분해 하고 v '에서 v' 까지 연결 하 며 용량 은 1 이다.②: 원 도 는 각각 방향 변 (x, y), x '에서 y' 까지 연결 되 고 용량 은 INF 이다.③: 방향 이 없 으 면 v '에서 v' 까지 연결 되 고 용량 은 INF 이다.
제목: POJ 1815.4. 매트릭스 형 / 격자 형
모델 링 방법: 보통 흑백 염색, 철거 등 방법 이 있다.일반적으로 이런 최소 분할 과 결합 하 는 문 제 는 수확 과 동시에 대가 가 있 기 때문에 가장 큰 권 폐 합 자 도 로 전환 할 수 있다.
제목 추천: HNOI 2013 인 절미, BZOJ 2132 링 프로젝트.
5. 최대 밀도 서브 맵 이분 답 ans. ans=sumEsumV sumE - ans * sumV 는 최대 치 를 취하 고 > = 0 이면 조건 을 만족 시 킵 니 다. 변 과 점 은 의존 관계 가 있 기 때문에 한 변 은 두 가지 에 의존 하기 때문에 가장 큰 권 폐 합 자 도 로 전환 할 수 있다. 변 은 정 권 1, 점 은 마이너스 ans.정 권 과 - 최소 절단 의 정 부 를 판단 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
