BOJ 22368 辺が先か，頂点が先か

문제 링크입니다.

문제 요약

유향 그래프가 주어집니다. 선공이 먼저 각 간선의 가중치를 결정하고, 후공이 이를 확인한 뒤 각 정점의 가중치를 결정합니다. 간선의 가중치 합과 정점의 가중치 합은 각각 1입니다.

그 뒤 가중치에 따른 확률로 간선과 정점을 하나씩 무작위로 뽑습니다. 이때 뽑힌 정점이 뽑힌 간선의 시작점이면 -1점, 끝점이면 +1점, 둘 다 아니면 0점을 얻고 게임을 종료합니다.

선공은 점수를 최대화, 후공은 점수를 최소화하는 전략을 사용할 때 점수의 기댓값을 구해야 합니다.

관찰

일단 최종 점수는 절대 0을 초과할 수 없습니다. 후공이 모든 정점에 균등한 가중치를 주면 최종 점수의 기댓값이 무조건 0이기 때문입니다.

만약 그래프에 사이클이 존재한다면, 선공이 그 사이클에 포함되지 않는 간선에는 가중치를 0으로 주고, 사이클에 포함되는 간선에만 균등한 가중치를 주면 후공이 어떻게 가중치를 주어도 점수의 기댓값은 0이 됩니다. 따라서 주어진 그래프가 DAG인 경우만 고려해도 충분합니다.

후공의 최적 전략

선공이 간선에 가중치를 부여한 뒤에, 후공은 굳이 많은 정점에 가중치를 줄 이유가 딱히 없습니다. 많은 정점을 선택할 수록 가장 후공에게 유리한 정점이 선택될 확률이 낮아지기 때문입니다.

따라서 후공은 가장 점수의 기댓값이 낮은 정점 하나만을 선택하는 것이 최적 전략입니다.

(후공의 최적 전략을 알고 있는) 선공의 최적 전략

선공은 가장 점수의 기댓값이 낮은 정점의 기댓값을 최대화하는 전략을 사용해야 합니다.

진출 차수가 0인 정점들은 간선에 어떻게 가중치를 주어도 기댓값이 0 이상입니다. 후공이 절대 선택하지 않을 것이므로, 선공은 진출 차수가 1 이상인 정점들에만 집중합니다.

진출 차수가 1 이상인 모든 정점의 점수의 기댓값을 균등하게 만드는 방법을 생각해 봅시다. 어떤 정점의 점수의 기댓값을 X라고 하면, 그 정점에서 진출하는 간선의 가중치 합 - 그 정점에 도달하는 간선의 가중치 합 = X여야 합니다. 이를 진입 차수가 0인 정점부터 순서대로 생각하면 쉽게 간선의 가중치를 매길 수 있습니다.

각 정점마다 진출하는 간선을 굳이 많이 고를 필요는 없습니다. 외려 정점의 진출 차수를 1 이하로 만드는 것이 그 정점의 가중치를 최대화하는 데에는 유리합니다. 그렇기 때문에, 각 정점마다 진출 간선은 최장경로에 들어가는 간선 하나만 남기고 나머지는 가중치로 0을 줄 수 있습니다.

기댓값 구하기

모든 간선의 가중치 합은 1이 되어야 합니다. 진입 차수가 0인 정점에서 진출하는 간선들의 가중치를 1로 두고 계산했을 때의 총 가중치 합을 K라고 하면, 우리가 구해야 하는 값은 -1/K가 됩니다.

진입 가중치 합 + 1이 진출 가중치로 넘어가는 거니까, 각 간선마다 할당되는 1은 그 간선의 시작점부터 DAG의 맨 끝 점까지의 거리만큼 더해집니다. 따라서 이 거리를 다 구해서 더하면 K의 값을 구할 수 있고, 이는 위상 정렬을 DAG의 역방향으로 하면 쉽게 구할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<int> e[12345];
int deg[12345], dist[12345], n, m;
queue<int> q;

void solve(){
	memset(deg, 0, sizeof(deg));
	memset(dist, 0, sizeof(dist));
	for(int i = 1; i <= n; i++) e[i].clear();
	while(m--){
		int u, v; cin >> u >> v;
		e[v].push_back(u);
		deg[u]++;
	}
	for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
	while(q.size()){
		int now = q.front(); q.pop();
		for(int nxt : e[now]){
			deg[nxt]--;
			if(!deg[nxt]){
				dist[nxt] = dist[now]+1;
				q.push(nxt);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(deg[i]){
			cout << "0\n"; return;
		}
		ans += dist[i];
	}
	cout << fixed << setprecision(12) << (long double)(-1)/ans << '\n';
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	while(1){
		cin >> n >> m; if(!n) return 0;
		solve();
	}
}