★ 격자 취 수 32 분 그림 의 최대 점 권 독립 집합

제목 설명 Description
< 문제 설명: m * n 개의 격자 가 있 는 바둑판 에서 각 격자 에 정수 가 있 습 니 다.현 재 는 격자 에서 수 를 뽑 아 임의의 두 개의 숫자 가 있 는 격자 가 공공 변 이 없 도록 하고 꺼 낸 수의 총계 가 가장 크다.요 구 를 만족 시 키 는 취 수 알고리즘 을 시험 적 으로 설계 하 다.< 프로 그래 밍 임무: 주어진 격자 바둑판 에 대해 취 수 요구 에 따라 프로 그래 밍 하여 총 과 최대 의 수 를 찾 습 니 다.
입력 설명 Input Description
첫 줄 에는 두 개의 정수 m 와 n 이 있 는데 각각 바둑판 의 줄 수 와 열 수 를 나타 낸다.다음 m 줄 은 줄 마다 n 개의 정수 가 있어 바둑판 격자 중의 수 를 나타 낸다.
출력 설명 Output Description
취 수의 최대 합계 출력
샘플 입력 Sample Input
3 3 1 2 3 3 2 3 2 3 1
샘플 출력 Sample Output
11
데이터 범위 및 알림 Data Size & Hint
n,m<=30
제목 은 여기에 제출 할 수 있 습 니 다:http://wikioi.com/homework/23/
분석: 2 분 그림 의 최대 점 권 독립 집합 모델 은 행렬 안의 각 점 을 두 개의 점 으로 나 누 었 다. i 와 i + n * m, 그리고 S 는 각 i 에 게 변 을 만 들 었 고 권 치 는 이 점 의 값 이 었 다. 그 다음 에 각 i + n * m 는 외환 점 T 에 변 을 만 들 었 다. 권 치 는 이 점 의 값 이 고 각 점 은 그 주변 네 개의 점 에 변 을 만 들 었 다. 권 치 는 무한대 이 고 최대 흐름 을 달리 면 된다.
코드:

//Isap  ，   O(n^2m)
#pragma comment(linker,"/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include