Asteroids--POJ 3041
6188 단어 poj
2. 문제 풀이 사고방식: 풀이 최소 집합 덮어쓰기, 즉 풀이 최대 2분의 일치, 헝가리 알고리즘의 간단한 응용.
3. 주의사항: 헝가리 알고리즘의 귀속 과정을 모의한다.
4. 구현 방법:
#include
<
iostream
>
using
namespace
std;
#define
Max 510
int
n,k,match[Max];
bool
map[Max][Max],vis[Max];
bool
DFS(
int
s)
{
int
i;
for
(i
=
1
;i
<=
n;i
++
)
{
if
(map[s][i]
&&
!
vis[i])
{
vis[i]
=
1
;
if
(match[i]
==
0
||
DFS(match[i]))
{
match[i]
=
s;
return
true
;
}
}
}
return
false
;
}
int
main()
{
int
i,r,c,ans
=
0
;
cin
>>
n
>>
k;
for
(i
=
0
;i
<
k;i
++
)
{
cin
>>
r
>>
c;
map[r][c]
=
1
;
}
for
(i
=
1
;i
<=
n;i
++
)
{
memset(vis,
0
,
sizeof
(vis));
if
(DFS(i))
ans
++
;
}
cout
<<
ans
<<
endl;
return
1
;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
