글 읽기 - 도와주세요

pos10022 5년 전 0

열혈강호에서 소스에서 사람 사이의 정방향의 최대 유량을 2로 바꾸었는데 8% 정도에서 틀렸다고 나와요ㅠㅠ

열혈 강호에서는 맞게 나왔어요.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 0x7fffffff

using namespace std;

vector<pair<pair<int, int>, int> > info[2017];
queue<int> q;
pair<int, int> path[2017];

int n, m, mini, ans;
bool chk[2017];

bool bfs()
{
	while (!q.empty()) q.pop();
	memset(chk, 0, sizeof(chk));
	q.push(n + m + 1);
	chk[n + m + 1] = true;
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (int i = 0;i < info[f].size();i++) {
			int next_f = info[f][i].first.first;
			if (info[f][i].first.second == 0) continue;
			if (!chk[next_f]) {
				q.push(next_f);
				path[next_f].first = f;
				path[next_f].second = i;
				chk[next_f] = true;
			}
			if (next_f == n + m + 2) return true;
		}
	}
	return false;
}

int main()
{
	int i, j, a, b;

	scanf("%d %d", &n, &m);
	for (i = 1;i <= n;i++) {
		info[n + m + 1].push_back(make_pair(make_pair(i, 2), info[i].size()));
		info[i].push_back(make_pair(make_pair(n + m + 1, 0), info[n + m + 1].size() - 1));
	}
	// n+m+1 : s
	for (i = 1;i <= m;i++) {
		info[n + m + 2].push_back(make_pair(make_pair(n + i, 0), info[n + i].size()));
		info[n + i].push_back(make_pair(make_pair(n + m + 2, 1), info[n + m + 1].size() - 1));
	}
	// n+m+2 : x
	for (i = 1;i <= n;i++) {
		scanf("%d", &a);
		for (j = 1;j <= a;j++) {
			scanf("%d", &b);
			info[i].push_back(make_pair(make_pair(n + b, 1), info[n + b].size()));
			// i : 사람 , n+b : 일
			info[n + b].push_back(make_pair(make_pair(i, 0), info[i].size() - 1));
		}
	}
	while (1) {
		if (!bfs()) break;
		vector<int> d;
		d.push_back(n + m + 2);
		mini = MAX;
		while (1) {
			int e = path[d.back()].first; // 그 노드 바로 앞의 노드
			int j = path[d.back()].second; // 그 노드 바로 앞의 노드가 몇 번째 간선인지
			if (mini > info[e][j].first.second) mini = info[e][j].first.second;
			d.push_back(e);
			if (e == n + m + 1) break;
		}
		for (i = d.size() - 2;i >= 0;i--) {
			int e = path[d[i]].first;
			int j = path[d[i]].second;
			int k = info[e][j].first.first; // e랑 연결되어 있는 또 다른 노드
			int s = info[e][j].second;
			info[e][j].first.second -= mini;
			info[k][s].first.second += mini;
		}
		ans += mini;
	}
	printf("%d\n", ans);
}

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

문제

문제

출처

ICPC

도와주세요

pos10022 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말