글 읽기 - 63퍼정도에서 틀리네요

didwlvv 7년 전 0

질문보고 수치가 같다면 체크를 해서 나머지 한마리는 못먹게했는데도 틀렸어요.. 도와주세요ㅜㅜ

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;
struct Data{
    int a,b,c;
};
vector<int>v[1005];
Data shk[1005];
int n;
int match[1005];    bool chk[1005]; bool t[1005];
void init();    void solve();
int dfs(int now);
int main(){
    
    init();
    solve();
    
    return 0;
}

void init(){
    scanf("%d", &n);
    
    for(int i=1; i<n+1; i++){//상어를 받는다.
        scanf("%d %d %d", &shk[i].a, &shk[i].b, &shk[i].c);
    }
    for(int i=1; i<n+1; i++){//서로서로 잡아먹을수 있기때문에 간선을 만든다.
        for(int j=1; j<n+1; j++){
            if(i==j)continue;
            v[i].push_back(j);
        }
    }
    memset(match,-1,sizeof match);
    
}

void solve(){
    int res =0;
    for(int t=0; t<2; t++){
        for(int i=1; i<n+1; i++){//이분매칭으로 dfs를 탑니다.
            memset(chk,false,sizeof chk);
            if(dfs(i))res++;
        }
    }
    cout << n-res <<endl;
}
int dfs(int now){
    if(chk[now])return false;
    
    chk[now]=true;
    
    for(int i=0; i<v[now].size(); i++){
        int next = v[now][i];
        if(shk[now].a ==shk[next].a && shk[now].b == shk[next].b// 이부분이 수치가 같으면 잡아주는건데
           && shk[now].c == shk[next].c){    //내가 먹는놈을 체크합니다. 나는 안합니다.
            t[next]=true;
            
            if(t[now] && t[next])return false; //여기서 만약에 둘다 체크가 되있으면 저번에 먹힌놈이 다른놈을 먹으려
        }                                      //먹는것이기 때문에 그냥 넘어갑니다
        if(shk[now].a >=shk[next].a && shk[now].b >= shk[next].b
           && shk[now].c >= shk[next].c){
            if(match[next] == -1 || dfs(match[next])){
                match[next]=now;
                return true;
            }
            
        }
    }
    
    
    return false;
    
    
}

ehddml3 7년 전 0

dfs 안에서 체크하는 부분 빼고 입력을 이렇게 받으니까 맞았습니다 뜨네용

for(int i=1; i<n+1; i++){//서로서로 잡아먹을수 있기때문에 간선을 만든다.
        for(int j=i+1; j<n+1; j++){
            v[i].push_back(j);
            if(shk[i].a ==shk[j].a && shk[i].b == shk[j].b
                && shk[i].c == shk[j].c) continue;
            v[j].push_back(i);
        }
    }

didwlvv 7년 전 0

감사합니다 ^^

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

문제

문제

출처

ICPC

63퍼정도에서 틀리네요

didwlvv 7년 전 0

ehddml3 7년 전 0

didwlvv 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말