HDU 2063 롤러코스터 2분도 문제풀이
1420 단어 HDU
그래서 전형적인 이분도 문제다.
헝가리 알고리즘을 사용하여 두 함수로 쓰면 뚜렷하다.
이 프로그램은 또한 분배 방출 프로그램을 가지고 있는데, 물론 oj는 일반적으로 필요로 하지 않는다.근데 좋은 프로그램은 꼭.
#include <stdio.h>
#include <stdlib.h>
int K, M, N, a, b;
int *linker;
bool **gra, *used;
void initGraph()
{
gra = (bool **) malloc(M * sizeof(bool*));// bool* bool
for (int i = 1; i < M; i++)
gra[i] = (bool *) calloc(N, sizeof(bool));
}
void freeGraph()
{
for (int i = 1; i < M; i++)
free(gra[i]);
free(gra);
}
bool hunDFS(int u)
{
for (int v = 1; v < N; v++)
{
if (gra[u][v] && !used[v])
{
used[v] = true;
if (!linker[v] || hunDFS(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary()
{
int ans = 0;
linker = (int *) calloc(N, sizeof(int));
for (int i = 1; i < M; i++)
{
used = (bool *) calloc(N, sizeof(bool));
if (hunDFS(i)) ans++;
free(used);
}
free(linker);
return ans;
}
int main()
{
while (scanf("%d %d %d", &K, &M, &N) != EOF && K)
{
M++, N++;// 1 ，0
initGraph();
while (K--)
{
scanf("%d %d", &a, &b);
gra[a][b] = true;
}
printf("%d
", hungary());
freeGraph();
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
