글 읽기 - 범죄파티 질문 드려요

tols91 7년 전 0

파라메트릭 서치로 이분매칭하면서 검사해주게 했는데 답이안나오네요..

코드 보고 고칠부분 알려주세요..ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, a, ka, b, kb;
vector<vector<pair<int, int> > > graph;
bool visited[300001];
int matched[300001];

bool dfs(int here, int m)
{
    if(visited[here]) return false;
    visited[here] = true;

    for(int i=0;i<graph[here].size();i++){
        int there = graph[here][i].first;
        int cost = graph[here][i].second;

        if( ((matched[there] == -1) && (cost <= m)) || dfs(matched[there], m)){ // 매칭이 안되어있고 cost가 m이하 인곳으로 매칭
            matched[there] = here;

            return true;
        }
    }
    return false;
}

int decision(int m)
{
    int ans = 0;
    memset(matched, -1, sizeof matched);
    for(int i=1;i<=n;i++){
        memset(visited, 0, sizeof visited);
        if(dfs(i, m))
            ans++;
    }
    return ans;
}

int optimize() 
{
    int lo = 0;
    int hi = 10000000;
    int mid;

    for(int i=0;i<100;i++){ // parametric search
        mid = (hi+lo) / 2;

        if(decision(mid) == n){ // n개가 매칭이 되면 파티 비용 낮춰줌
            hi = mid;
        }else{
            lo = mid;
        }
    }

    return hi;
}

int main()
{
    scanf("%d", &n);
    graph.resize(3*n+1);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d %d", &a, &ka, &b, &kb);
        graph[i].push_back(make_pair(a+n,ka));
        graph[i].push_back(make_pair(b+n,kb));
    }

    printf("%d\n", optimize());

    return 0;
}