글 읽기 - 이게 왜 TLE가 아니죠?

whquddn55 6년 전 0

O(V^2E)인 디닉을 썼습니다.

한 사람에게 배분해주고 난 뒤 남은 돼지를 다른 우리에 넣어서 다음 사람에게 배분해줄 수 있다고 해서 각 사람마다 우리의 개수(m)개 만큼 우리를 만들어주고 배분 해주어서

총 vertex개수는 m * n(총 우리의 개수) + n(사람의 개수) + 2(source , sink)개, 최대 10만개 이고,

각 vertex당 적어도 하나의 edge가 달려 있으므로 e은 최대의 경우 최소 10만개.... 당연히 tle가 떠야하는거 아닌가요?

네트워크 문제는 최악의 경우를 만드는게 불가능에 가깝기때문에 O(VE)로 봐도 무방(하지는 않지만)하다고 하던걸로 기억하는데 O(VE)로 봐도 당연히 TLE아닌가...요?

당연히 터질줄 알고 다른 방법 계속 생각하다가 구현해보고 안 되면 답 보자는 생각으로 제출했는데.. 띠용?

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define INF (INT_MAX / 2)
#define endl '\n'

#define MAX_V 100003

struct Edge { // Edge 설정 (Edge 도착점, Edge의 용량, 맞Edge의 번호)
	int to, capacity, flow, reverse;
	Edge(int to, int capacity, int reverse)
		:to(to), capacity(capacity), flow(0), reverse(reverse) {}
};

vector<Edge> graph[MAX_V]; // vertex의 각 Edge를 보관하는 vector
int level[MAX_V]; // vertex의 level 보관
int iter[MAX_V]; // 각 vertex의 Edge 방문개수 보관

int n, m;

void bfs(int s) {
	fill(level, level + MAX_V, -1);
	queue<int> q;
	q.push(s);
	level[s] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (Edge& e : graph[v]) {
			if (e.capacity - e.flow > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}
}

int dfs(int v, int t, int f) {
	if (v == t)
		return f;
	for (int& i = iter[v]; i < graph[v].size(); i++) {
		Edge& e = graph[v][i];
		if (e.capacity - e.flow > 0 && level[v] < level[e.to]) {
			int d = dfs(e.to, t, min(f, e.capacity - e.flow));
			if (d > 0) {
				e.flow += d;
				graph[e.to][e.reverse].flow -= d;
				return d;
			}
		}
	}

	return 0;
}

int maxFlow(int s, int t) {
	int flow = 0;
	while (true) {
		bfs(s);
		if (level[t] < 0)
			return flow;
		fill(iter, iter + MAX_V, 0);
		int f;
		while ((f = dfs(s, t, INF)) > 0)
			flow += f;
	}
	return flow;
}

void addEdge(int from, int to, int capacity) {
	graph[from].emplace_back(to, capacity, graph[to].size());
	graph[to].emplace_back(from, 0, graph[from].size() - 1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> m >> n;
	int source = 0;
	int sink = (m + 1) * n + 1;

	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		addEdge(source, 1 + i, a);
	}
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;

		vector<int> arr(t);
		for (int j = 0; j < t; i++){
			int tmp;
			cin >> tmp;
			arr[t] = tmp;
		}

		for (int j = 0; j < t; j++) {
			addEdge((m + 1) * i + arr[j], (m + 1) * (i + 1), INF);
			for (int k = 0; k < t; k++)
				if (j != k)
					addEdge((m + 1) * i + arr[j], (m + 1) * (i + 1) + arr[k], INF);
		}
		if (i != n - 1)
			for (int j = 0; j < m; j++)
				addEdge((m + 1) * i + (j + 1), (m + 1) * (i + 1) + (j + 1), INF);

		int tmp;
		cin >> tmp;
		addEdge((m + 1) * (i + 1), sink, tmp);
	}

	cout << maxFlow(source, sink) << endl;

	return 0;
}

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

문제

문제

출처

ICPC

이게 왜 TLE가 아니죠?

whquddn55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말