롤러 코스 터(이분 도 일치)
hdu_2063:롤러 코스 터
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 14852 Accepted Submission(s): 6544
Problem Description
RPG 걸 스 는 오늘 여러분 과 함께 놀이 공원 에 놀 러 가 꿈 에 그리 던 롤러 코스 터 를 탈 수 있 게 되 었 습 니 다.그러나 롤러 코스 터 는 한 줄 에 두 개의 좌석 만 있 고 성문 화 되 지 않 은 규칙 도 있다.즉,모든 여자 들 은 반드시 한 명의 남 자 를 찾 아 파트너 가 되 어 그녀 와 함께 타 야 한 다 는 것 이다.그러나 모든 여자 들 은 각자 의 생각 을 가지 고 있 습 니 다.예 를 들 어 Rabbit 는 XHD 나 PQK 와 만 파트너 가 되 고 Grass 는 linle 이나 LL 과 만 파트너 가 되 고 싶 습 니 다.PrincessSnow 은 수역 의 방탕아 나 가짜 쿠 아 와 파트너 가 되 고 싶 습 니 다.경비 문 제 를 고려 해 보스 유 는 파트너 를 찾 은 사람 에 게 만 롤러 코스 터 를 타 게 하기 로 했다.다른 사람들 은 헤헤,아래 에 서서 지 켜 보기 로 했다.똑똑 한 Acmer,최대 몇 쌍 의 그룹 이 롤러 코스 터 를 탈 수 있 는 지 계산 해 주 시 겠 어 요?
Input
데 이 터 를 입력 한 첫 줄 은 세 개의 정수 K,M,N 으로 각각 가능 한 조합 수,여자 의 수,남자 의 수 를 나타 낸다.0
Output
각 조 의 데이터 에 대해 하나의 정 수 를 출력 하면 롤러 코스 터 를 탈 수 있 는 최대 조합 수 를 나타 낸다.
Sample Input
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
Sample Output
3
Author
PrincessSnow
Source
RPG 특별 연습 경기
문제 풀이:하나의 표준 2 분 도 는 일치 하지만 2 분 도 에서 왼쪽 과 오른쪽 점 에 중복 되 는 번호 가 있어 서 는 안 되 므 로 왼쪽 점 이 0 부터 m-1 까지 라면 남 자 는 m 부터 번 호 를 매 겨 야 한다.
헝가리 알고리즘 의 사고방식 은 귀속 적 인 호출 을 사용 하 는 것 이다.여기 서 매번 증폭 로 를 찾 은 후에 허실 선 을 대조 해 야 하기 때문에 이런 해답 을 찾 아서 이전의 경 로 를 조작 하 는 행 위 를 역 추적 이 라 고 한다.역 추적 문 구 는 반드시 다음 과 같은 형식 으로 써 야 한다.
if(해답 찾기)
{
역 추적 작업;/여 기 는 맨 위의 조작 만 고려 하면 됩 니 다.뒤의 재 귀 를 통 해 이미 해결 되 었 다 고 가정 하면 dfs 와 유사 한 사고 입 니 다.
}
그래서 경 로 를 찾 는 핵심 코드 는:
if(rm[s]==-1||find(rm[s]))
{
rm[s] = s;
return 1;//되돌아오다
}
다음은 코드 를 드 립 니 다.
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 #define N 1010
6 int head[N];
7 struct Edge{
8 int to;
9 int next;
10 }edge[N*N];
11 int Enct;
12 void init()
13 {
14 memset(head,-1,sizeof(head));
15 Enct = 0;
16 }
17 void add(int from , int to)
18 {
19 edge[Enct].to = to;
20 edge[Enct].next = head[from];
21 head[from] = Enct++;
22 edge[Enct].to = from;
23 edge[Enct].next = head[to];
24 head[to] = Enct++;
25 }
26 bool vis[N*N];
27 int k , n , m ;
28 int rm[N*N];
29
30 bool list(int s)
31 {
32 for(int j = head[s] ; j != -1 ; j = edge[j].next)
33 {
34 int tm = edge[j].to;
35 if(vis[tm]==1) continue;
36 vis[tm] = 1;//
37 if(rm[tm]==-1||list(rm[tm])){
38 rm[tm] = s;
39 return 1;
40 }
41 }
42 return 0;
43 }
44 int MaxMatch()
45 {
46 int ans = 0;
47 for(int i = 0 ; i < m ; i++)
48 {
49 memset(vis,0,sizeof(vis));
50 vis[i] = 1;//
51 if(list(i)) ans++;
52 }
53 return ans;
54 }
55 int main()
56 {
57 while(~scanf("%d%d%d",&k,&m,&n))
58 {
59 init();
60 for(int i = 0 ;i < k ;i++)
61 {
62 int x, y;
63 scanf("%d%d",&x,&y);
64 add(x-1,y+m-1);// ，
65 }
66 int a ;
67 scanf("%d",&a);
68 memset(rm,-1,sizeof(rm));
69 int ans = MaxMatch();
70 printf("%d
",ans);
71 }
72 return 0;
73 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
