글 읽기 - 고수분들 도와줘요... 이분매칭과 포함배제 썼습니다. ㅠㅠ

curnurx 5년 전 0

행이 숫자, 열이 수열에서의 위치 로 해서

adj 행렬 만들었고,

이분매칭은 홉크로프트,

adj 행렬 계산은 2차원 포함배제써서 했습니다.

대부분의 경우 맞는 거 같은데 빼먹은 테스트 케이스가 뭘까요....

코드가 길지만 부탁드립니다 ㅠㅠ

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <functional>
#include <map>
#include <string>
#include <set>
#include <list>
#include <random>
#define aa first
#define bb second
using namespace std;
typedef long long lint;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int MOD = 1e9;
const int INF = 1e9;
const int WOW = 40000; // for reserve
const int NIL = 0; // this is for hopcroft
const int dy[8] = {-1, 0, 1, 0, 1 , 1, -1, -1};
const int dx[8] = {0, 1, 0, -1, 1, -1,1,-1};

int N, M;

bool adj[201][201];
int lazy[202][202];
int am[201], bm[201], dist[201];


bool bfs(){
    fill(dist, dist + N + 1, INF);
    queue<int> q;
    for (int i = 1; i<=N;++i)if (!am[i]){
        dist[i] = 0;
        q.push(i);
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        if (dist[u] >= dist[NIL]) continue;
        for (int v = 1; v<= N; ++v){
            if (!adj[u][v]) continue;
            int vm = bm[v];
            if (dist[vm] != INF) continue;
            dist[vm] = dist[u] + 1;
            q.push(vm);
        }
    }
    return dist[NIL] != INF;
}

bool dfs(int u){
    if (u== NIL) return 1;
    for (int v =1; v<=N; ++v){
        if (!adj[u][v]) continue;
        int& vm = bm[v];
        if (dist[vm] == dist[u] + 1 && dfs(vm)){
            vm = u;
            am[u]=v;
            return 1;
        }
    }
    dist[u] =INF;
    return 0;
}

bool hopcroft(){
    int ret = 0;
    while(bfs()) for (int i=1;i<=N;++i) if (!am[i]) ret += dfs(i);
    return ret == N;
}

int main(){
    scanf("%d%d",&N,&M);
    memset(adj, 1, sizeof(adj));
    while(M--){
        int q, x,y,v;
        scanf("%d%d%d%d",&q,&x,&y,&v);
        if (y < x) swap(x,y);
        
        if (q == 1){
            lazy[N][y] += 1;
            lazy[v][y] -=1;
            lazy[N][x -1] -=1;
            lazy[v][x - 1] +=1;
        }
        if (q==2){
            lazy[v - 1][y] += 1;
            lazy[v-1][x -1] -=1;
            lazy[0][y] -=1;
            lazy[0][x - 1] += 1;
        }
        for (int i = 1; i <= N; ++i) if (i < x || y < i) adj[v][i] = 0;
    }
    
    for (int y = N; y >= 1; --y){
        for (int x = N; x>=1; --x){
            lazy[y][x] += -lazy[y + 1][x + 1] + lazy[y + 1][x] + lazy[y][x+1];
            if (lazy[y][x]) adj[y][x] = 0; 
        }
    }
    
    if (!hopcroft()) puts("-1");
    else{
        for (int i = 1; i <= N; ++i) printf("%d ", bm[i]);
        puts("");
    }
    
    
}

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

문제

문제

출처

ICPC

고수분들 도와줘요... 이분매칭과 포함배제 썼습니다. ㅠㅠ

curnurx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말