글 읽기 - 서로 잡아먹는 관계에서 간선을 뒤죽박죽으로 어떤 문제가 생기나요?

pjh9996 5년 전 0

62번 라인에서 주석 친 소스(무작위선택)로 실행하면 60%에서 WA를 봤고, 질문글을 본 후에 인덱스 순서로 정해주니 맞았습니다.

서로 잡아먹을 때 무작위로 선택되면 어떤 경우에 문제가 생기는지 알고싶습니다.

직접 케이스를 만들어서 검증해보는것이 많이 어렵네요...

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>

#define A first.first
#define B first.second
#define C second

using namespace std;
using pii=pair<int,int>;
using ll=long long;

int n;
vector<pair<pii,int>> shark;
vector<set<int>> adjlist;
vector<int> parent;
vector<bool> visited;

int answer=0;

void input()
{
    cin>>n;
    shark.resize(n);
    adjlist.resize(n*2);
    parent.resize(n,-1);
    visited.resize(n*2);
    for(int i=0; i<n; i++) cin>>shark[i].A>>shark[i].B>>shark[i].C;
}

void output()
{
    cout<<n-answer;
}

bool bmatch(int now)
{
    if(visited[now]) return false;
    visited[now]=true;
    for(auto it=adjlist[now].begin(); it!=adjlist[now].end(); it++){
        int next=*it;
        if(parent[next]==-1 || bmatch(parent[next])){
            parent[next]=now;
            return true;
        }
    }
    return false;
}

void process()
{
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(shark[i]==shark[j]){
                //뒤죽박죽 선택 소스(틀린 소스)
                /*
                if(shark[i]==shark[j]){
                    adjlist[min(i,j)].insert(max(i,j));
                    adjlist[min(n+i,j)].insert(max(n+i,j));
                }
                */
                //작은 인덱스 번호가 큰 인덱스 번호를 먹도록(맞은 소스)
                if(i<j){
                    adjlist[i].insert(j);
                    adjlist[n+i].insert(j);
                }
                else{
                    adjlist[j].insert(i);
                    adjlist[n+j].insert(i);
                }
            }
            else if(shark[i].A>=shark[j].A && shark[i].B>=shark[j].B && shark[i].C>=shark[j].C){
                adjlist[i].insert(j);
                adjlist[n+i].insert(j);
            }
            else if(shark[j].A>=shark[i].A && shark[j].B>=shark[i].B && shark[j].C>=shark[i].C){
                adjlist[j].insert(i);
                adjlist[n+j].insert(i);
            }
        }
    }

    for(int i=0; i<n*2; i++){
        fill(visited.begin(),visited.end(),false);
        if(bmatch(i)) answer+=1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
    input();
    process();
    output();
    return 0;
}

djm03178 5년 전 0

일단 이 상태에서 저 주석과 그 아래의 if else만을 뒤바꾸면 parent의 크기가 작아서도 문제가 됩니다.

33번째 줄에서 n*2로 크기를 변경하면 다음과 같은 입력이 반례가 됩니다.

상어가 서로를 동시에 먹을 수 없는데도 서로 먹어치우고 아무도 남지 않는 것으로 계산하게 됩니다.

2
1 1 1
1 1 1

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

문제

문제

출처

ICPC

서로 잡아먹는 관계에서 간선을 뒤죽박죽으로 어떤 문제가 생기나요?

pjh9996 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말