글 읽기 - '책 나눠주기' 시간초과 질문입니다.

wiz 8년 전 0

이분매칭으로 풀었는데 시간초과가 납니다.

각 정점마다 a부터 b번까지의 간선을 모두 추가해야 하는데, 연결된 간선이 너무 많아서 그런 것이 아닌가 추측됩니다.

혹시나 다른 방법을 알고 계시면 답변 부탁드립니다.

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

using namespace std;
const int MAX_N = 1001;
const int MAX_M = 1001;
int N, M;
vector<vector<int> > G;
vector<int> bMatch;
vector<bool> visit;

void add_edge(int u, int v) {
	G[u].push_back(v);
}

bool dfs(int a) {

	if (visit[a]) return false;
	visit[a] = true;
	for (int b = 0; b < G[a].size(); ++b) {
		int there = G[a][b];
		if (bMatch[there] == -1 || dfs(bMatch[there])) {
			bMatch[there] = a;
			return true;
		}
	}
	return false;
}

int bipartiteMatch() {

	bMatch = vector<int>(N, -1); // M
	int size = 0;
	for (int start = 0; start < N; ++start) {
		visit = vector<bool>(N, false);
		if (dfs(start))
			++size;
	}
	return size;
}

int main() {

	int c;
	cin >> c;
	while (c--) {

		scanf("%d%d", &N, &M);
		int a, b;
		G = vector<vector<int> >(N);
		for (int i = 0; i < M; ++i) {
			scanf("%d%d", &a, &b);
			for (int j = a - 1; j <= (b - 1); ++j)
				add_edge(j, i);
		}
		cout << bipartiteMatch() << endl;
	}
	return 0;

}

yukariko 8년 전 1

저는 정렬후에 O(N)으로 총 O(NlgN)으로 풀었습니다.

hakgb11 8년 전 1

이렇게 수정하니 답이 나왔습니다.

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
 
using namespace std;
const int MAX_N = 1001;
const int MAX_M = 1001;
int N, M;
vector<vector<int> > G;
vector<int> bMatch;
vector<bool> visit;
 
void add_edge(int u, int v) {
    G[u].push_back(v);
}
 
bool dfs(int a) {
 

    for (int b = 0; b < G[a].size(); ++b) {
        
        int there = G[a][b];
        if(visit[there]) continue;
        visit[there] = true;
    
        if (bMatch[there] == -1 || dfs(bMatch[there])) {
            bMatch[there] = a;
            return true;
        }
    }
    return false;
}
 
int bipartiteMatch() {
 
    bMatch = vector<int>(M, -1); // M
    int size = 0;
    for (int start = 0; start < N; ++start) {
        visit = vector<bool>(M, false);
        if (dfs(start))
            ++size;
    }
    return size;
}
 
int main() {
 
    int c;
    cin >> c;
    while (c--) {
 
        scanf("%d%d", &N, &M);
        int a, b;
        G = vector<vector<int> >(N);
        for (int i = 0; i < M; ++i) {
            scanf("%d%d", &a, &b);
            for (int j = a - 1; j <= (b - 1); ++j)
                add_edge(j, i);
        }
        cout << bipartiteMatch() << endl;
    }
    return 0;
 
}

wiz 8년 전 0

답변들 정말 감사합니다.

좀 더 배워갑니다.~

luke0201 8년 전 0

참고로 말씀드리자면 네트워크 플로우 알고리즘은 시간 복잡도가 꽤 큽니다. 그래서 보통 N이 200 정도로 주어지니까 이 이상인 경우에는 다른 방법을 생각해보심이 ㅎ.

myth 6년 전 0

wiz 님 어떻게 풀이를 변경하셨는지요?

DFS 함수 내만 변경된 것 같은데.... 맞는지요?

medic_programmer 6년 전 0

@yukariko 님 그리디로 어떻게 하는지 도움을 주실 수 있을까요?

yukariko 6년 전 0

1년전 풀이라 제 코드를 봐도 무슨생각으로 이렇게 했는지 모르겠네요..

무엇보다 O(N)도 아니었고, 제 풀이가 정답인지도 모르겠습니다.

일단 코드 첨부하겠습니다.

#include <bits/stdc++.h>

using namespace std;

bool cmp(const pair<int,int>& p, const pair<int,int>& q)
{
	if(p.second != q.second)
		return p.second < q.second;
	return p.first < q.first;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int N, M;
		scanf("%d%d",&N,&M);

		vector< pair<int, int> > a(M);
		for(int i=0; i < M; i++)
			scanf("%d%d",&a[i].first, &a[i].second);

		sort(a.begin(), a.end(), cmp);

		int ans = 0;
		bool b[1001] = {};
		for(int i=0; i < M; i++)
			for(int j=a[i].first; j <= a[i].second; j++)
				if(b[j] == false)
				{
					ans++;
					b[j] = true;
					break;
				}
		printf("%d\n",ans);
	}
	return 0;
}

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

문제

문제

출처

ICPC

'책 나눠주기' 시간초과 질문입니다.

wiz 8년 전 0

yukariko 8년 전 1

hakgb11 8년 전 1

wiz 8년 전 0

luke0201 8년 전 0

myth 6년 전 0

medic_programmer 6년 전 0

yukariko 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말