글 읽기 - 반례좀 찾아주세요...

tlsdbrjs 6년 전 0

거의 틀릴만한것 해봤는데 잘 모르겠네요...

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<bitset>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#include<map>
#define ll long long
#define MAX 987654321
using namespace std;
vector<int> v[20];
int visited[20];
int n, m,Min=MAX;
bool check()
{
	for (int i = 0; i < n; i++)
		if (!visited[i])
			return false;
	return true;
}
void sol(int s,int t)
{
	int ssize = v[s].size();
	for (int i = 0; i < ssize; i++)
	{
		visited[v[s][i]]=t;
	}
}
void func(int i,int num)
{
	if (i == m)
	{
		if (check())
		{
			Min = min(Min, num);
		}
		return;
	}
	func(i + 1, num);
	sol(i,1);
	func(i + 1, num + 1);
	sol(i, 0);
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int tsize,tmp;
		scanf("%d", &tsize);
		for (int j = 0; j < tsize; j++)
		{
			scanf("%d", &tmp);
			tmp--;
			v[i].push_back(tmp);
		}
	}
	func(0, 0);
	if (Min != MAX)
		printf("%d\n", Min);
	else
		printf("-1\n");
}

thexl 6년 전 1

Back tracking 시 sol(i, 0) 부분에서 기존에 1로 되어 있던 부분도 0으로 바꿔버립니다.

아래와 같이 수정하니 Accept 되네요.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<bitset>
#include<functional>
#include<list>
#include<cmath>
#include<stack>
#include<map>
#define ll long long
#define MAX 987654321
using namespace std;
vector<int> v[20];
int visited[20];
int n, m,Min=MAX;
bool check()
{
	for (int i = 0; i < n; i++)
		if (!visited[i])
			return false;
	return true;
}
void sol(int s,int t)
{
	int ssize = v[s].size();
	for (int i = 0; i < ssize; i++)
	{
		visited[v[s][i]] += t;
	}
}
void func(int i,int num)
{
	if (i == m)
	{
		if (check())
		{
			Min = min(Min, num);
		}
		return;
	}
	func(i + 1, num);
	sol(i, 1);
	func(i + 1, num + 1);
	sol(i, -1);
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int tsize,tmp;
		scanf("%d", &tsize);
		for (int j = 0; j < tsize; j++)
		{
			scanf("%d", &tmp);
			tmp--;
			v[i].push_back(tmp);
		}
	}
	func(0, 0);
	if (Min != MAX)
		printf("%d\n", Min);
	else
		printf("-1\n");
}

thexl 6년 전 0

추가로 반례는

5 5

2 1 2

3 3 4 5

2 2 3

2 3 4

2 2 5

일 때 (1, 2), (3, 4, 5)로 답이 2이지만 질문자분의 코드로 돌릴 시 3으로 뜹니다.

tlsdbrjs 6년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

반례좀 찾아주세요...

tlsdbrjs 6년 전 0

thexl 6년 전 1

thexl 6년 전 0

tlsdbrjs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말