글 읽기 - 간선 연결을 어떻게 하는게 좋을까요 ??

hazxz 7년 전 0

조를 2개를 만들어야하니깐 처음에는 source를 in_node, out_node로 용량 2를 주고 out_node에서 각각의 node로 용량 1을 주는 형식으로 했습니다. 그리고 각각의 노드들은 조가 될 수 있는 ( 좋아하는 ) 노드끼리 연결을 해주고 sink도 in_node, out_node 나누어 용량 2로 연결했습니다. source랑 sink만 두가지로 나눈게 좀 이상해보이기도 하고 fail이 뜨더라구요...

아니면 이분매칭 개념으로 n명의 사람에 대해 2*n 개의 node를 만들어 싫어하는 사람들끼리 연결하여 최대한 간선을 많이 선택하는 쪽으로도 생각해봤는데 이렇게 하면 조가 2개가 되는 개념이 아닐꺼 같아서 햇갈립니다..좋아하는 사람들끼리 연결하여야 하는건지 햇갈리기도 하고요 ㅜㅜ

int in_node(int x) {
	return 2 * x;
}
int out_node(int x) {
	return in_node(x) + 1;
}
int source, sink;

struct Dinic {

	struct edge {
		int to, cap, rev;
		edge() {}
		edge(int a, int b, int c) :to(a), cap(b), rev(c) {}
	};
	vector<vector<edge>> G;
	vector<int> level;
	vector<int> iter;

	Dinic(int n) {
		G.resize(n);
		level.resize(n);
		iter.resize(n);
	}


	void add_edge(int from, int to, int cap)
	{
		edge e(to, cap, G[to].size());
		edge re(from, 0, G[from].size());
		G[from].push_back(e);
		G[to].push_back(re);
	}
	void bfs(int s) {
		std::fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front();
			que.pop();
			for (int i = 0; i < G[v].size(); i++) {
				edge & e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t) return f;
		for (int &i = iter[v]; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, std::min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			bfs(s);
			if (level[t] < 0) return flow;
			std::fill(iter.begin(), iter.end(), 0);
			int f;
			while ((f = dfs(s, t, INF)) > 0) {
				flow += f;
			}
		}
	}
};

int grade[55];
char str[55];
bool chk[55][55];

int main() {
	int n, m, k;

	scanf("%d", &n);

	Dinic D((n + 3) * 2);
	source = 0, sink = n+1;

	for (int i = 1; i <= n; i++) {
		scanf("%1d", &grade[i]);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (grade[i] == grade[j]) {
				D.add_edge(i, n + j, 1);
				D.add_edge(j, n + i, 1);
				chk[i][j] = true;
				chk[j][i] = true;
			}
		}
		D.add_edge(0, i, 1);
		D.add_edge(i, 2 * n + 1, 1);
	}

	for (int i = 1; i <= n; i++) {
		scanf("%s", str);
		for (int j = 1; j <= n; j++) {
			if (str[j-1] == 'Y' && chk[i][j] == false) {
				D.add_edge(i, n + j, 1);
				D.add_edge(j, n + i, 1);
				chk[i][j] = true;
				chk[j][i] = true;
			}
		}
	}
	D.add_edge(2 * n + 2, 0, 2);
	D.add_edge(2 * n + 1, 2 * n + 3, 2);
	printf("%d\n", D.max_flow(2 * n + 2, 2 * n + 3));
	return 0;
}

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

문제

문제

출처

ICPC

간선 연결을 어떻게 하는게 좋을까요 ??

hazxz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말