글 읽기 - 왜틀렸을까요~

movie_jo 5년 전 0

각자 친구관계 연결 하고
소스 -> 여자 (홀수) 연결하고
남자 (짝수) -> 싱크 연결하고
플로우 돌렸습니다

최종 플로우 수 : 짝의 수니깐 2 곱하고, 짝 다 맞췄는데 N명보다 적으면 한명 가운데 끼울 수 있으니 + 1 한걸 답으로 했습니다.

플로우 구현은 평소에 다른 문제 풀 때 했던거랑 비교해도 다른점이 없는데 뭐가 문제일까요...

#include <stdio.h>
#include <vector>
#include <queue>

#define SRC 0
#define SNK 201

using namespace std;

vector<int> vec[202];
int capa[202][202];
int flow[202][202];
int visit[202];
int parent[202];

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

		capa[u][v] = capa[v][u] = 1;
		vec[u].push_back (v);
		vec[v].push_back (u);
	}
	
	for (int i = 1; i <= N; i += 2) {
		
		capa[SRC][i] = 1;
		vec[SRC].push_back (i);
		vec[i].push_back (SRC);
	}

	for (int i = 2; i <= N; i += 2) {
		
		capa[i][SNK] = 1;
		vec[i].push_back (SNK);
		vec[SNK].push_back (i);
	}
	
	int totalFlow = 0;
	
	for (int t = 1; ; t++) {
		
		queue<int> q;
		q.push (SRC);
		visit[SRC] = t;
		
		while (!q.empty () && visit[SNK] != t) {
			
			int u = q.front (); q.pop ();
			
			for (int i = 0; i < vec[u].size (); i++) {
				
				int v = vec[u][i];
				
				if (visit[v] == t) continue;
				
				if (capa[u][v] - flow[u][v] > 0) {
					
					q.push (v);
					visit[v] = t;
					parent[v] = u;
				}
			}
		}
		
		if (visit[SNK] != t) break;
		
		int maxFlow = 999;
		
		for (int i = SNK; i != SRC; i = parent[i]) {
			
			if (maxFlow > capa[parent[i]][i] - flow[parent[i]][i])
				maxFlow = capa[parent[i]][i] - flow[parent[i]][i];
		}

		for (int i = SNK; i != SRC; i = parent[i]) {
			
			flow[parent[i]][i] += maxFlow;
			flow[i][parent[i]] -= maxFlow;
		}
		
		totalFlow += maxFlow;
	}
	
	totalFlow *= 2;
	
	printf ("%d\n", totalFlow < N ? totalFlow + 1 : totalFlow);
	
	return 0;
}

adh0463 5년 전 2

주어지는 M개의 데이터는 친한 친구라는 것을 나타낼 뿐이지, 이성이라는 보장은 없어요

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

문제

문제

출처

ICPC

왜틀렸을까요~

movie_jo 5년 전 0

adh0463 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말