글 읽기 - 어디서 틀렸는지 조언좀 부탁드립니다.

dydsj0920 6년 전 0

4%에서 계속 틀렸다고 나오는데요.. 어디가 잘못된건지 잘 모르겠습니다..

//스타 대결 - 나중에 시간 나면 내 방식대로 풀어보자..
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;


int a[102][102];
int n;
int source = 0, sink = 101;
bool check[102];

bool dfs(int x) {
	if (check[x]) return 0;
	check[x] = true;
	if (x == sink) {
		return true;
	}
	for (int i = 0; i <= sink; i++) {
		if (a[x][i] > 0) {
			if (dfs(i)) {
				a[x][i] -= 1;
				a[i][x] += 1;

				return true;
			}
		}
	}
	return false;
}

int flow() {
	int ans = 0;
	while (true) {
		memset(check, false, sizeof(check));
		if (!dfs(source)) {
			break;
		}
		ans += 1;
	}
	return ans;
}


int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	int s1 = 0, s2 = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[source][i]);
		s1 += a[source][i];
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &a[n + i][sink]);
		s2 += a[n + i][sink];
	}
	if (s1 != s2) {
		printf("-1\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][n + j] = 1;	//전부 1로 연결
		}
	}
	int ans = flow();	//flow 한번->엣지 몇개의  방향이 바뀌어 있다.
	if (s1 != ans || s2 != ans) {
		printf("-1\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			bool ans = false;
			if (a[i][n + j] == 0) {
				a[source][i] += 1;
				a[n + j][sink] += 1;
				memset(check, false, sizeof(check));
				if (!dfs(source)) {		//한번 더 탐색했을 때 sink까지 도달하지 못하면
					ans = true;			//crucial Link다!
				}
				else {
					a[i][n + j] = 0;	//한번 더 탐색했을 때 sink로 도달했다면 다시 이전 상태로 초기화
				}
				a[source][i] -= 1;
				a[n + j][sink] -= 1;
			}
			if (ans) {		//crucial Link라서 어쩔 수 없이 해당 선수끼리 경기를 해야한다.
				cout << '1';
			}
			else {			//한번 더 탐색했을때 sink에 도달했으므로 굳이 해당 선수끼리 경기를 안해도 된다.
				cout << '0';
			}
		}
		cout << '\n';
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 틀렸는지 조언좀 부탁드립니다.

dydsj0920 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말