HDU-2819 Swap 다이어그램 일치
4882 단어 swap
코드는 다음과 같습니다.
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstring>
#define MAXN 105
using namespace std;
int N, G[MAXN][MAXN], marry[MAXN], visit[MAXN];
int r1[MAXN], r2[MAXN], count;
int path(int u)
{
for (int i = 1; i <= N; ++i) {
if (!G[u][i] || visit[i])
continue;
visit[i] = 1;
if (!marry[i] || path(marry[i])) {
marry[i] = u;
return 1;
}
}
return 0;
}
void Accepted()
{
int x;
for (int i = 1; i <= N; ++i) {
x = i;
for (int j = i; j <= N; ++j) {
if (marry[j] < marry[x]) {
x = j;
}
}
if (x != i) {
r1[++count] = i, r2[count] = x;
int t = marry[i];
marry[i] = marry[x];
marry[x] = t;
}
}
}
int main()
{
int x, cnt;
while (scanf("%d", &N) == 1) {
cnt = 0;
count = 0;
memset(G, 0, sizeof (G));
memset(marry, 0, sizeof (marry));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
scanf("%d", &x);
if (x) {
G[i][j] = 1;
}
}
}
for (int i = 1; i <= N; ++i) {
memset(visit, 0, sizeof (visit));
if (path(i))
++cnt;
}
if (cnt != N)
puts("-1");
else {
Accepted();
printf("%d
", count);
for (int i = count; i >= 1; --i)
printf("R %d %d
", r1[i], r2[i]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0908 Chapter 03. 자바 객체지향 프로그래밍헤더,필드,메소드,생성자 Arrays.toString(배열변수); 사용 (impot java.util.Arrays; 해줘야함) toString 객체 역할을하지만 객체아니어서 오버라이딩 불가 객체안의 데이터를 스트링으...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.