[POJ 3041] Asteroids [네트워크 흐름 - 최소 덮어 쓰기]

제목:
N ∗ N N * N ∗ N 의 행렬 에는 K K K 개의 소행성 이 있 는데, 현재 줄 마다 하나의 무기 가 있 는데, 이 줄 이나 이 열 에 있 는 모든 소행성 을 제거 할 수 있 습 니 다. 행렬 에 있 는 모든 소행성 을 제거 할 수 있 는 무기 가 최소 몇 개 필요 하 냐 고 물 었 습 니 다.
생각:
이것 은 전형 적 인 가장 작은 덮어 쓰기 문제 로 이분 도 일치 알고리즘 이나 최대 흐름 알고리즘 으로 해결 할 수 있다.우 리 는 주로 인터넷 흐름 의 방법 을 토론 한다.
먼저 최대 흐름 D i n i c Dinic Dinic 의 기본 적 인 특성 을 살 펴 보고 잔 량 네트워크 에서 B F S BFS BFS 가 모든 노드 의 차원 을 구하 여 하나의 층 도 를 구성 했다.그리고 분 층 도 에서 D F S DFS DFS 는 증 폭 로 를 찾 아 거 슬러 올 라 갈 때 남 은 용량 을 실시 간 으로 업데이트 한다.잔 량 네트워크 에서 S S S 가 T T T 에 도달 하지 못 할 경우 알고리즘 이 종 료 됩 니 다.
따라서 최대 흐름 이라는 알고리즘 은 매우 중요 한 성질 을 가지 고 있 습 니 다. 즉, 최대 흐름 = = 최소 절단 = = 최대 일치 = = 최소 점 으로 덮어 쓰 고 대부분의 최대 흐름 응용 문 제 를 기본적으로 덮어 씁 니 다.
이제 우 리 는 이 문제 가 어떻게 그림 을 만 드 는 지 다시 돌 이 켜 보 자. 이 문 제 는 가장 적은 점 으로 모든 변 을 덮 고 전형 적 인 가장 작은 점 으로 문 제 를 덮 는 것 이다.따라서 우 리 는 이 를 최대 일치 로 바 꾸 었 다. 즉, 모든 점 은 한 번 만 선택 할 수 있 고 최대 몇 개의 변 을 선택 할 수 있 는 지 하 는 것 이다.따라서 (i, j) (i, j) (i, j) 위치 에 있 는 행성 에 대해 왼쪽 에 있 는 i i 개 점 과 오른쪽 에 있 는 j j 개 점 을 연결 시 키 고 그림 의 모든 변 류 량 은 1, 1 로 설정 하여 최대 흐름 을 달리 면 된다.
마지막 으로 엄밀 하지 않 은 '최대 일치 = = 최소 덮어 쓰기' 증명 을 다시 하 겠 습 니 다.즉, 그림 에서 선택 한 변 이 최대 일치 에 이 르 렀 을 때 선택 하지 않 은 변 이 존재 하지 않 고 변 의 두 점 이 동시에 선택 되 지 않 았 습 니 다.또한 각 점 은 한 번 만 선택 할 수 있 기 때문에 각 변 은 하나의 점 만 선택 한 것 을 대표 하고 이 점 들 의 집합 은 모든 변 을 덮 었 다.그다지 엄밀 하지 않 은 증명 은 단지 기억 에 유리 할 뿐이다.상세 한 증명 은 인터넷 에서 문 제 를 계속 찾 아 볼 수 있다.
코드:

#include 
#include 
#include 
#include 
#include  
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int inf = 1<<29,N = 1000+10,M = 300500;  //  1e4-1e5     

struct Edge{ 
	int to,next,v;
}e[M];
int n,m,s,t,k;  //              
int head[N],tot,dis[N],mp[N][N];
queue<int> q;

void init()   //        ！
{
	tot = 1; memset(head,0,sizeof head);  //     2~n，  2^1 = 3, 3^1 = 2;            
}

void add(int x,int y,int v)
{
	e[++tot].to = y; e[tot].next = head[x]; e[tot].v = v; head[x] = tot;
	e[++tot].to = x; e[tot].next = head[y]; e[tot].v = 0; head[y] = tot;  //             v 
}

bool bfs()
{

	memset(dis,0,sizeof dis);
	while(!q.empty()) q.pop();
	q.push(s); dis[s] = 1;
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		for(int i = head[x];i;i = e[i].next)
		{
			if(e[i].v && !dis[e[i].to]){
				q.push(e[i].to);


				dis[e[i].to] = dis[x]+1;
				if(e[i].to == t) return 1;  //      return 
			}
		}
	}
	return 0;
}

int dinic(int x,int flow) //     
{

	
	if(x == t) return flow;
	int rest = flow,k;  //rest       
	for(int i = head[x];i && rest; i = e[i].next)
	{
		if(e[i].v && dis[e[i].to] == dis[x]+1){
			k = dinic(e[i].to,min(rest,e[i].v));
			if(!k) dis[e[i].to] = 0;  //  ，         
			e[i].v -= k;
			e[i^1].v += k;  //     flow，                
			rest -= k; //k           
		}
	}
	return flow-rest;  //            
}

int solve()
{
	int flow = 0,maxflow = 0;
	while(bfs())
		while((flow = dinic(s,inf))) maxflow += flow;	
	return maxflow;
}

int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		init();
		s = 1, t = 1+n+n+1;
		rep(i,1,k){
			int xx,yy; scanf("%d%d",&xx,&yy);
			add(xx+1,yy+1+n,1);
		}
		rep(i,1,n) add(s,i+1,1), add(1+n+i,t,1);
		printf("%d
",solve());
	}
	return 0;
} 

/*
5 5
1 3
2 3
3 3
4 3
5 3
2
*/