HDU-2819 Swap 다이어그램 일치

4882 단어 swap
출력 교환을 몇 번 하지 않았기 때문에 시스템 error를 몇 번 공헌하지 않았습니다.이 문제는 줄마다 1에 대응하는 위치를 찾아 정렬하면 된다.
코드는 다음과 같습니다.
#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;
}

좋은 웹페이지 즐겨찾기