글 읽기 - 4%에서 틀립니다 ㅠㅠ 반례가 뭘까요 ...

rottoy 4년 전 0

코드를 작성하고 난 뒤에야 SCC라는 것을 확인했는데 제 알고리즘에 반례가 있을까요? 시간초과도 아니고 틀렸습니다가 뜹니다 ...

#include<iostream>
#include<algorithm>
#include<queue>
#include<memory.h>
#define f first
#define s second
using namespace std;
pair<int, int> a[101];
int origin[101];
char c[101][101];
int b[101][101];
bool ans[101];
bool chk[101];
bool visited[101];

int n;
bool ispossible(int now, int next) {
	if (now == next) return false;
	memset(visited, false, sizeof(visited));
	queue<int> q;
	q.push(now);
	visited[now] = true;

	while (!q.empty()) {
		int x = q.front(); q.pop();
		if (x == next) { return true; }
		for (int i = 1; i <= n; i++) {
			if (visited[i] == true)continue;
			if (b[x][i] == 0)continue;
			visited[i] = true;
			q.push(i);
		}
	}
	return false;
}
int main() {

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		a[i].first = x; a[i].second = i; origin[i] = x;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> c[i][j]; b[i][j] = int(c[i][j] - 48);

		}
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		int idx = a[i].second;
		if (chk[idx])continue;
		for (int j = 1; j <= n; j++) {
			if (ispossible(idx, j) && ispossible(j, idx)) {
				//cout << idx <<" "<<j<<"\n";
				ans[idx] = true; chk[idx] = true; chk[j] = true;
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (ans[i]) res += origin[i];
	}
	cout << res;
	return 0;
}

wpqldmlrna 4년 전 1

반례

입력 :

5
1 2 3 4 5
00000
00000
00000
00000
00000

정답 : 15

해당 코드 출력 : 0

rottoy 4년 전 0

감사합니다 ........

고립된 정점을 고려 하지 않았네요

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

문제

문제

출처

ICPC

4%에서 틀립니다 ㅠㅠ 반례가 뭘까요 ...

rottoy 4년 전 0

wpqldmlrna 4년 전 1

rottoy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말