code vs 체크 수 3

1907 체크 수 3
 시간 제한: 2 s
 공간 제한: 256000 KB
 제목 레벨: 마스터 마스터 마스터
해제
 실행 결과 보기
제목 설명 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
분류 태그 Tags 이것 을 누 르 면 펼 쳐 집 니 다. 
문제 풀이: 최소 절단.
이 문 제 는 최소 절단 을 이용 하 는 것 이 최대 흐름 과 같다.어떻게 그림 을 만 드 느 냐 가 관건 이다. 처음에는 생각 하지 못 했 는데 신 번 의 지 도 를 받 아 깨 달 았 다.
먼저 체크 를 흑백 으로 염색 하 는 것 이 바로 흑백 이 교차 하 는 분포 이다. 모든 블랙 칸 과 인접 한 것 은 흰색 칸 이 고 모든 흰색 칸 과 인접 한 것 은 검은색 칸 이다. 그 다음 에 원점 에서 그래서 검은색 칸 으로 연결 되 고 용량 은 검은색 칸 의 가중치 이 며 모든 흰색 칸 에서 합 점 으로 연결 되 며 용량 은 흰색 칸 의 가중치 이다. 그 다음 에 모든 블랙 칸 에서 모든 인접 한 흰색 칸 으로 연결 되 고 용량 은 INF 이다.그리고 마지막 으로 최대 흐름 을 달리 면 됩 니 다.
왜 일 까요?최소 절단 은 최대 흐름 과 같다.우리 가 선택 한 격자 가 서로 연결 되 지 않 고 가장 크 면 버 리 는 변 이 가능 한 한 적어 야 하기 때문이다.인접 한 점 은 하나만 선택 할 수 있 기 때문에 모든 흐 를 수 있 는 경 로 는 제한 흐름 을 통 해 흑백 점 중 작은 것 만 선택 하여 버 리 는 것 이 가장 적다.

#include
#include
#include
#include
#include
using namespace std;
int n,m,a[1000][1000],sum;
int point[10000],next[20000],v[20000],remain[20000],tot=-1;
int num[10000],cur[10000],deep[10000],laste[10000];
const int inf=1e9;
void add(int x,int y,int z)
{
  tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z;
  tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;
}
int addflow(int s,int t)
{
  int minn=inf,now=t;
  while(now!=s)
   {
   	minn=min(minn,remain[laste[now]]);
   	now=v[laste[now]^1];
   }
  now=t;
  while(now!=s)
   {
   	remain[laste[now]]-=minn;
   	remain[laste[now]^1]+=minn;
   	now=v[laste[now]^1];
   }
  return minn;
}
void bfs(int s,int t)
{
  for (int i=s;i<=t;i++)  deep[i]=t;
  deep[t]=0; queue p; p.push(t);
  while(!p.empty())
   {
   	int now=p.front(); p.pop();
   	for (int i=point[now];i!=-1;i=next[i])
   	 if (remain[i^1]&&deep[v[i]]==t)
   	  deep[v[i]]=deep[now]+1,p.push(v[i]);
   }
}
int isap(int s,int t)
{
  int ans=0,now=s;
  bfs(s,t);
  for (int i=s;i<=t;i++)   num[deep[i]]++;
  for (int i=s;i<=t;i++)   cur[i]=point[i]; 
  while(deep[s]0)  add((i-1)*m+j,(i-2)*m+j,inf);
   	 	  	 if (i+1<=n) add((i-1)*m+j,i*m+j,inf);
   	 	  	 if (j-1>0)  add((i-1)*m+j,(i-1)*m+j-1,inf);
   	 	  	 if (j+1<=m)  add((i-1)*m+j,(i-1)*m+j+1,inf);
   	 	  } 
   	 	 else
   	 	  add((i-1)*m+j,n*m+1,a[i][j]);
   	 }
   	else
   	 {
   	 	for (int j=1;j<=m;j++)
   	 	 if (j%2==0)  
   	 	  {
   	 	  	 add(0,(i-1)*m+j,a[i][j]);
   	 	  	 if (i-1>0)  add((i-1)*m+j,(i-2)*m+j,inf);
   	 	  	 if (i+1<=n) add((i-1)*m+j,i*m+j,inf);
   	 	  	 if (j-1>0)  add((i-1)*m+j,(i-1)*m+j-1,inf);
   	 	  	 if (j+1<=m)  add((i-1)*m+j,(i-1)*m+j+1,inf);
   	 	  } 
   	 	 else
   	 	  add((i-1)*m+j,n*m+1,a[i][j]); 
   	 }
   }
  printf("%d",sum-isap(0,n*m+1));
}