kmjp's blog

競技プログラミング参加記です

NJPC 2017 : E - 限界集落

これもあまり迷わず解けた。
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_e

問題

N頂点(N-1)有向辺のグラフが与えられる。
各辺には距離が与えられている。
このグラフは辺を無向辺とみなすと木を成している。

以下の条件を満たすように辺の向きを変えたい。
最小何本の辺の向きを変える必要があるか。

  • ある頂点を1つゴールとして設定する。
    • 全辺は各頂点からこのゴールに向かうようにする。
    • 全頂点からゴールまでの距離の最大値はD以下である。

解法

各頂点について、最遠点までの距離と、辺のうちその頂点から外向きに向いている辺(=向きを逆にしなければならない辺)の数を数え上げよう。
それぞれDFSを2回行うテクで求められる。
最遠点を求めるのは直径を求める手法でもよい。(結局2回DFS行う点で大差ない)

int N,D;
int A[101010],B[101010];
int C[101010];
int rev[101010];
vector<int> dist[101010];
vector<pair<int,int>> E[101010];

int dfs(int cur,int pre) {
	
	dist[cur].push_back(0);
	FORR(r,E[cur]) {
		int tar=(r.second?A[r.first]:B[r.first]);
		if(tar!=pre) dist[cur].push_back(dfs(tar,cur)+C[r.first]);
	}
	sort(ALL(dist[cur]));
	reverse(ALL(dist[cur]));
	return dist[cur][0];
}

void dfs2(int cur,int pre,int par) {
	
	dist[cur].push_back(par);
	sort(ALL(dist[cur]));
	reverse(ALL(dist[cur]));
	
	FORR(r,E[cur]) {
		int tar=(r.second?A[r.first]:B[r.first]);
		if(tar!=pre) {
			int id=(dist[cur][0]==dist[tar][0]+C[r.first]);
			dfs2(tar,cur,dist[cur][id]+C[r.first]);
		}
	}
}

int dfs3(int cur,int pre) {
	
	FORR(r,E[cur]) {
		int tar=(r.second?A[r.first]:B[r.first]);
		if(tar!=pre) rev[cur]+=dfs3(tar,cur)+(1^r.second);
	}
	return rev[cur];
}

void dfs4(int cur,int pre,int par) {
	rev[cur]+=par;
	
	FORR(r,E[cur]) {
		int tar=(r.second?A[r.first]:B[r.first]);
		if(tar!=pre) {
			int left=rev[cur]-(rev[tar]+(1^r.second));
			dfs4(tar,cur,left+r.second);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	FOR(i,N-1) {
		cin>>A[i]>>B[i]>>C[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back({i,0});
		E[B[i]].push_back({i,1});
	}
	
	dfs(0,-1);
	dfs2(0,-1,0);
	dfs3(0,-1);
	dfs4(0,-1,0);
	
	int mi=1<<20;
	FOR(i,N) if(dist[i][0]<=D) mi=min(mi,rev[i]);
	if(mi==1<<20) mi=-1;
	cout<<mi<<endl;
	
}

まとめ

下校時は問題ないらしい。