낙 곡 P2756 조종사 배합 방안 문제 (Dinic 알고리즘 템 플 릿)

제목 배경
제2차 세계 대전 때...
제목 설명
영국 로 열 공군 은 점령 국 에서 대량의 외국 국적 의 비행 사 를 모집 했다.로 열 공군 이 파견 한 모든 비행 기 는 항행 기능 과 언어 적 으로 서로 협조 할 수 있 는 조종사 2 명 을 배치 해 야 하 며, 이 중 1 명 은 영국 조종사 이 고, 다른 1 명 은 외국 국적 조종사 다.많은 조종사 중에서 외국 국적 의 조종사 한 명 은 다른 몇몇 영국 조종사 들 과 잘 협조 할 수 있다.어떻게 짝 짓 기 비행 사 를 선택해 야만 한 번 에 가장 많은 비행 기 를 파견 할 수 있 습 니까?주어진 외국 국적 의 조종사 와 영국 조종사 의 협조 상황 에 대해 하나의 알고리즘 을 시험 적 으로 설계 하여 최 적의 조종사 배합 방안 을 찾 아 황실 공군 이 한 번 에 가장 많은 비행 기 를 파견 할 수 있 도록 한다.
주어진 외국 국적 의 조종사 와 영국 조종사 의 협조 상황 에 대해 프로 그래 밍 은 최 적의 조종사 배합 방안 을 찾 아 로 열 공군 이 한 번 에 가장 많은 비행 기 를 파견 할 수 있 도록 한다.
입 출력 형식
입력 형식:
첫 줄 에는 두 개의 정수 m 와 n 이 있다.n 은 황실 공군 의 조종사 총수 (n < 100) 이다.m 는 외국 국적 의 조종사 수 (m < = n) 다.외국 국적 의 조종사 번 호 는 1 ~ m 이다.영국 조종사 번 호 는 m + 1 ~ n 이다.
다음 줄 마다 2 개의 정수 i 와 j 가 있 는데 외국 국적 의 조종사 i 가 영국 조종사 j 와 협조 할 수 있다 는 것 을 나타 낸다.마지막 으로 2 개. - 1 로 끝.
출력 형식:
첫 번 째 줄 은 최고의 조종사 배합 방안 으로 한 번 에 가장 많이 파 견 될 수 있 는 비행기 수 M 이다.다음 M 행 은 최고의 조종사 배합 방안 이다.각 줄 에 2 개의 정수 i 와 j 가 있 는데 최 적 조종사 배합 방안 에서 조종사 i 와 조종사 j 가 짝 을 이 루 었 음 을 나타 낸다.원 하 는 최고의 조종사 배합 방안 이 존재 하지 않 는 다 면 'No Solution!' 을 출력 한다.
입 출력 샘플
샘플 입력 \ # 1: 

5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

출력 샘플 \ # 1: 

4
1 7
2 9
3 8
5 10 

이전에 이 문 제 를 헝가리 알고리즘 으로 한 번 풀 어 본 적 이 있 는데, 나중에 토론 구역 의 주 의 를 통 해 이 문 제 는 원래 인터넷 흐름 의 문 제 였 다 는 것 을 알 게 되 었 다.Σ(っ °Д °;)っ)
마침 인터넷 흐름 을 배우 기 시작 하 자마자 템 플 릿 을 만 들 었 다.
이 문 제 는 Dinic 알고리즘 으로 푸 는 관건 은 그림 을 어떻게 만 드 느 냐 에 있다.
그 다음 에 스스로 출발점 의 종점 을 정의 하고 출발점 과 모든 외국 국적 의 비행 사 를 연결 한 다음 에 종점 과 모든 로 열 비행 사 를 연결 시 키 고 마지막 으로 템 플 릿 을 한 번 만 설치 하면 된다.

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 205;
const int INF = 50000;
int n,m; //n         ,m       
int tot; // n+m
ll sum=0;//       
int mp[maxn][maxn];//    0,    tot
int dis[maxn];//  
bool bfs(){ //s       
	queue q;
	int tmp;
	memset(dis,-1,sizeof(dis));//  bfs       
	q.push(0);
	dis[0]=1;//        1 
	while(!q.empty()){
		tmp = q.front();
		q.pop();
		for(int i=1;i<=tot;i++)
			if(mp[tmp][i]>0 && dis[i]==-1){
				q.push(i);
				dis[i] = dis[tmp]+1;
			}
	}
	if(dis[tot]>0) return true;
	return false;
}
int dfs(int s,int mx){//s     ,mx     
	if(s == tot) return mx;
	int tmp;
	for(int i=1;i<=tot;i++){
		if(mp[s][i] > 0 && dis[i] == dis[s]+1 && (tmp = dfs(i,min(mx,mp[s][i]))) ){
			mp[s][i] -= tmp;
			mp[i][s] += tmp;
			return tmp;
		}
	}
	return 0;
}
int main(){
	int x,y;
	cin>>m>>n;//      ,    
	tot = m+n+1;
	memset(mp,-1,sizeof(mp));
	memset(dis,-1,sizeof(dis));
	while(cin>>x>>y){ //    ,     
		if(x == -1) break;
		mp[x][y] = 1;
		mp[y][x] = 0;
		mp[0][x] = 1;  //    
		mp[y][tot] = 1;//   
	}
	while(bfs()){
		int s = dfs(0,INF);
		sum+=s;
	}
	cout<