글 읽기 - 이분매칭에서 소스에서 나가는 간선 용량이 1이 아니라 2일때 어찌하나요?

sgc109 7년 전 0

이분매칭에서 왼쪽에 source 에서 나가는 간선 용량이 2로 늘어나는경우에 코드를 어떤식으로 변형해야하나요?

@appa

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<queue>

#define REP(i,a,b) for(int i=a;i<b;++i)
#define FOR(i,n) REP(i,0,n)
#define LONG long long
#define INF 0x3a3a3a3a

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int adj[MAX_N][MAX_M];
vector<bool> visited;
vector<int> aMatch, bMatch;
int N,M;

bool dfs(int a){
    if(visited[a]) return false;
    visited[a] = true;
    
    FOR(b,M) {
        if(adj[a][b]) {
            if(bMatch[b] == -1 || dfs(bMatch[b])) {
                aMatch[a] = b;
                bMatch[b] = a;
                return true;
            }
        }
    }
    
    return false;
}

int bipartiteMatch() {
    aMatch = vector<int>(N,-1);
    bMatch = vector<int>(M,-1);
    int size = 0;
    FOR(i,N) {
        visited = vector<bool>(N,false);
        if(dfs(i))
            ++size;
    }
    return size;
}
    
int main() {
    scanf("%d%d",&N,&M);
    FOR(i,N){
        int m;
        scanf("%d",&m);
        FOR(j,m){
            int tmp;
            scanf("%d",&tmp);
            --tmp;
            adj[i][tmp] = 1;
        }
    }
    
    printf("%d",bipartiteMatch());
    
    return 0;
}

baekjoon 7년 전 1

호출을 두 번 하세요

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

문제

문제

출처

ICPC

이분매칭에서 소스에서 나가는 간선 용량이 1이 아니라 2일때 어찌하나요?

sgc109 7년 전 0

baekjoon 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말