글 읽기 - 반례 질문

prarie 3년 전 1

1. DFS 로 먼저 SCC 를 구합니다.

2. S 가 속한 SCC 의 집합을 S', T 가 속한 SCC의 집합을 T' 라 합시다.

S' 부터 출발해서 각각의 SCC를 정점으로 하는 그래프를 만들어 갑니다.

3. DAG에서 S' -> T' 로 갈 때 최댓값을 dp를 통해 계산합니다.

반례 부탁드립니다..

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define fi first
#define se second
#define endl '\n'
#define all(v) (v).begin(), (v).end()

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e4 + 5;

int n, m, s, t;
vector<int> adj[N];
int dfsn[N], sccn[N], cntn;
stack<int> st;
vector<vector<int>> scc;

set<int> sadj[N];
int dp[N], ind[N];
bool visited[N];

int dfs(int cur) {
	int ret = dfsn[cur] = cntn++;
	st.emplace(cur);
	for (auto &next : adj[cur]) {
		if (dfsn[next] == -1) ret = min(ret, dfs(next));
		else if (sccn[next] == -1) ret = min(ret, dfsn[next]);
	}
	if (ret == dfsn[cur]) {
		int id = scc.size();
		vector<int> x;
		while (1) {
			int p = st.top(); st.pop();
			sccn[p] = id;
			x.emplace_back(p);
			if (p == cur) break;
		}
		scc.emplace_back(x);
	}

	return ret;
}

int main() {
	fastio;
	cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].emplace_back(v);
	}
	memset(dfsn, -1, sizeof dfsn);
	memset(sccn, -1, sizeof sccn);
	for (int i = 1; i <= n; i++) if (dfsn[i] == -1) dfs(i);

	queue<int> q;
	q.push(sccn[s]);
	visited[sccn[s]] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto &u : scc[cur]) for (auto &v : adj[u]) {
			int &next = sccn[v];
			if (visited[next]) continue;
			q.emplace(next);
			visited[next] = true;
			sadj[cur].emplace(next);
			ind[next]++;
		}
	}
	q.push(sccn[s]);
	dp[sccn[s]] = scc[sccn[s]].size();
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto &next : sadj[cur]) {
			ind[next]--;
			dp[next] = max(dp[next], dp[cur] + (int)scc[next].size());
			if (ind[next] == 0) {
				q.emplace(next);
			}
		}
	}
	cout << dp[sccn[t]] << endl;
}

prarie 3년 전 0

SCC를 정점으로 한 그래프에서 위상정렬 하면서 dp값 구하는 거 구현한 걸 좀 다르게 바꿔서 AC 맞았습니다.

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define fi first
#define se second
#define endl '\n'
#define all(v) (v).begin(), (v).end()

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e4 + 5;

int n, m, s, t;
vector<int> adj[N];
int dfsn[N], sccn[N], cntn;
stack<int> st;
vector<vector<int>> scc;

vector<int> sadj[N];
int dp[N], ind[N];
bool can[N];

int dfs(int cur) {
	int ret = dfsn[cur] = cntn++;
	st.emplace(cur);
	for (auto &next : adj[cur]) {
		if (dfsn[next] == -1) ret = min(ret, dfs(next));
		else if (sccn[next] == -1) ret = min(ret, dfsn[next]);
	}
	if (ret == dfsn[cur]) {
		int id = scc.size();
		vector<int> x;
		while (1) {
			int p = st.top(); st.pop();
			sccn[p] = id;
			x.emplace_back(p);
			if (p == cur) break;
		}
		scc.emplace_back(x);
	}

	return ret;
}

int main() {
	fastio;
	cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].emplace_back(v);
	}
	memset(dfsn, -1, sizeof dfsn);
	memset(sccn, -1, sizeof sccn);
	for (int i = 1; i <= n; i++) if (dfsn[i] == -1) dfs(i);
	for (int i = 1; i <= n; i++) for (auto &j : adj[i]) {
		if (sccn[i] == sccn[j]) continue;
		sadj[sccn[i]].emplace_back(sccn[j]);
		ind[sccn[j]]++;
	}
	queue<int> q;
	for (int i = 0; i < scc.size(); i++) {
		if (!ind[i]) q.emplace(i);
	}
	can[sccn[s]] = true;
	dp[sccn[s]] = scc[sccn[s]].size();
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (auto &next : sadj[cur]) {
			if (can[cur]) {
				dp[next] = max(dp[next], dp[cur] + (int)scc[next].size());
				can[next] = true;
			}
			ind[next]--;
			if (!ind[next]) {
				q.emplace(next);
			}
		}
	}
	cout << dp[sccn[t]];
}

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

문제

문제

출처

ICPC

반례 질문

prarie 3년 전 1

prarie 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말