POJ3041-Asteroids

전재 출처: 유유http://user.qzone.qq.com/289065406/blog/1299322465
 
문제 풀이 방향:
방진 을 특수 한 이분 도 (행렬 로 각각 두 개의 정점 집합 V1, V2, 그 중 | V1 | = | V2 |) 로 본다.
그 다음 에 각 줄 x 또는 각 열 y 를 하나의 점 으로 보고 장애물 (x, y) 은 x 와 y 를 연결 하 는 변 으로 볼 수 있다.이런 발상 으로 구도 해 보면문 제 는 가장 적은 점 (x 또는 y) 을 선택 하여 이런 점 에서 모든 변 과 인접 하 게 하 는 것 으로 바 뀌 었 다. 사실은 이것 이 가장 작은 커버 문제 이다.
 
2 분 그림 의 최대 일치 하 는 K ö nig 정리 재 활용:
최소 덮어 쓰기 수 = 최대 일치 수
 
(PS: 가장 작은 덮어 쓰기: 점 하 나 를 선택 하면 점 을 점 으로 하 는 모든 변 을 덮어 쓰 는 것 과 같 습 니 다. 그림 의 모든 변 을 덮어 쓰 려 면 최소한 의 점 을 선택해 야 합 니 다.)
 
따라서 본 문 제 는 자 연 스 럽 게 이분 도 를 구 하 는 가장 큰 일치 문제 로 바 뀌 었 다.
 
 
가장 큰 일치 하 는 알고리즘 을 구 하 는 것 은 모든 일치 하 는 것 을 찾 은 다음 에 가장 많은 일치 하 는 것 을 유지 하 는 것 이다.그러나 이 알고리즘 의 시간 복잡 도 는 변수의 지수 급 함수 이다.
따라서 더욱 효율 적 인 알고리즘 을 찾 아야 한다. 넓 은 길 로 최대한 일치 하 는 방법 (헝가리 알고리즘) 을 찾 아야 한다.
 
확장 로 의 정의 (확장 레일 또는 교차 레일 이 라 고도 함):
만약 에 P 가 그림 G 에서 두 개의 일치 하지 않 는 정점 을 연결 하 는 경로 이 고 M 에 속 하 는 변 과 M 에 속 하지 않 는 변 (즉 일치 하고 일치 하 는 변) 이 P 에서 교체 되 어 나타 나 면 P 는 M 에 비해 넓 어 지 는 경로 라 고 합 니 다.
 
증 광로 의 정의 에서 다음 과 같은 세 가지 결론 을 내 릴 수 있다.
1. P 의 경로 개 수 는 반드시 홀수 이 고 첫 번 째 변 과 마지막 변 은 모두 M 에 속 하지 않 습 니 다.
2. M 과 P 를 역 조작 하면 더 큰 일치 M 을 얻 을 수 있 습 니 다.
   (역 동작: P 의 일치 변 을 일치 하지 않 는 변 과 바 꿉 니 다)
3. M 은 G 의 최대 일치 이 고 M 이 존재 하지 않 는 확장 경로 P
 
헝가리 알고리즘 윤곽:
(1) M 을 비 워 두 기
(2) 확대 경로 P 를 찾 아 이동 또는 조작 을 통 해 M 대신 더 큰 일치 M '을 얻 습 니 다.
(3) 확장 경 로 를 찾 지 못 할 때 까지 반복 (2) 작업
 
 

//Memory Time 
//464K   47MS 

#include<iostream>
using namespace std;

int n,k;  //n    ，k    
int V1,V2;       //      
 /*                  V1、V2，   x∈V1， y∈V2*/
bool grid[501][501];  //      ：    
bool vis[501];     //  V2            
int link[501];     //   V2   y   V1       x   
int m;  //     

/*Hungary Algorithm*/

bool dfs(int x)
{
	for(int y=1;y<=V2;y++)
		if(grid[x][y] && !vis[y])  //x y  (  )     y    
		{
			vis[y]=true;   //    y    
			if(link[y]==0 || dfs(link[y])) //link[y]==0 :   y        M
			{                               //find(link[y] :    y              
				link[y]=x; //        M'( M  M')
				return true;  //         
			}
		}
	return false;  //    V1   x     
}

void search(void)
{
	for(int x=1;x<=V1;x++)
	{
		memset(vis,false,sizeof(vis)); //          
		if(dfs(x))  // V1    x       
			m++;
	}
	return;
}

int main(void)
{
	cin>>n>>k;
	V1=V2=n;

	int x,y;         //  (    )
	for(int i=1;i<=k;i++)
	{
		cin>>x>>y;
		grid[x][y]=true;   //      
	}

	/*     */

	search();

	/*Output*/

	cout<<m<<endl;

	return 0;
}