글 읽기 - 뭐가 잘못된건지 모르겠습니다!

ojh031 4년 전 0

가능한 경로를 dfs로 찾아서 찾았으면 dfs를 통해 또 경로를 확인하는 방식으로 작성했는데 틀린 부분을 잘모르겠습니다.

#include <iostream>

using namespace std;

#define INF 101;
int n, m;
int arr[301][301];
bool visit[301];
int cnt = 0;
int maxx;
bool dfs(int s,int X) {
	visit[s] = true;
	if (X < maxx)
		maxx = X;
	if (s == n) {
	//	cout << maxx << endl;
		cnt+=maxx;
		return true;
	}
	bool check=false;
	for (int i = 1; i <= n; i++) {
		if (arr[s][i] > 0 && !visit[i])  { //방문가능한 점이면 방문
			check=dfs(i,arr[s][i]);
			if (check) {
				arr[s][i] -= maxx;
				return true;
			}
		}
	}
	return check;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++)
			arr[i][j] = 0;
	}
	for (int i = 0; i < m; i++) {
		int from, to,cost;
		cin >> from >> to >> cost;
		if (arr[from][to] == 0 || arr[from][to]< cost) {
			arr[from][to] = cost;
			arr[to][from] = cost;
		}
	}// input
	do {
		for (int i = 1; i <= n; i++) {
			visit[i] = false;
			maxx = INF;
		}
	}while (dfs(1,101)); //길을 못찾을때까지 dfs

	cout << cnt << endl;
	return 0;
}

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

문제

문제

출처

ICPC

뭐가 잘못된건지 모르겠습니다!

ojh031 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말