글 읽기 - 네트워크 플로우 도와주세요...

alsidnf 4년 전 0

네트워크 플로우 1일차 애기입니다. 힌트좀 받고 다른질문들 보면서 열심히 풀었는데 왜 안되는지 모르겠습니다 ㅠㅠ

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 300
using namespace std;
int K, N, M, S, E;
struct Edge {
	int to, c, f;
	Edge* dual;
	Edge() : Edge(-1, 0) {}
	Edge(int _to, int _c) : to(_to), c(_c), f(0), dual(nullptr) {}
	int spare() { return c - f; }
	void add_flow(int _f)
	{
		f += _f;
		dual->f -= f;
	}
};
vector<vector<Edge*> > adj;
bool qu(int st,int ed)
{
	queue<int> Q;
	int chk[MAX];
	fill(chk, chk + MAX, -1);
	Q.push(st);
	while (!Q.empty() && chk[ed] == -1)
	{
		int curr = Q.front(); Q.pop();
		for (Edge *e : adj[curr])
		{
			int next = e->to;
			if (e->c!=0 && e->spare() > 0 && chk[next] == -1)
			{
				chk[next] = curr;
				Q.push(next);
				if (next == ed) break;
			}
		}
	}
	if (chk[ed]==-1) return true;
	return false;
}
int main()
{
	scanf("%d", &K);
	while (K--)
	{
		scanf("%d%d", &N, &M);
		adj.clear();
		adj.resize(N);
		E = N - 1;
		//입력
		for (int i = 0; i < M; i++)
		{
			int f, t, b;
			scanf("%d%d%d", &f, &t, &b); f--; t--;
			Edge *e1 = new Edge(t, b), *e2 = new Edge(f, 0);
			e1->dual = e2;  e2->dual = e1;
			adj[f].push_back(e1);
			adj[t].push_back(e2);
		}
		//최종 그래프 만들기
		while (1)
		{
			int prev[MAX];
			Edge *path[MAX] = { 0, };
			fill(prev, prev + N, -1);
			queue<int> Q;
			Q.push(S);
			while (!Q.empty() && prev[E] == -1)
			{
				int curr = Q.front(); Q.pop();
				for (Edge* e : adj[curr])
				{
					int next = e->to;
					if (e->spare() > 0 && prev[next] == -1)
					{
						Q.push(next);
						prev[next] = curr;
						path[next] = e;
						if (next == E) break;
					}
				}
			}
			if (prev[E] == -1) break;
			int flow = 0x7FFFFFFF;
			for (int i = E; i != S; i = prev[i])
				flow = min(flow, path[i]->spare());
			for (int i = E; i != S; i = prev[i])
				path[i]->add_flow(flow);
		}
		//중요한 간선 찾기
		int ans = 0;
		for (int i = 0; i < N; i++)
		{
			for (Edge *e : adj[i])
			{
				ans += qu(i, e->to);
			}
		}
		printf("%d\n", ans);
	}
}

alsidnf 4년 전 0

if (e->spare() != 0) continue;

if (e->c == 0) continue;

이렇게 넣고 하니까 됩니다 ㅠㅠ

밑에 다른 질문이랑 비슷한 실수네요 ㅠㅠ

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

문제

문제

출처

ICPC

네트워크 플로우 도와주세요...

alsidnf 4년 전 0

alsidnf 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말