Codeforces Round#532(Div.2)E.Andrew and Taxi(二分+トポロジーソート)

タイトルリンク:http://codeforces.com/contest/1100/problem/E
n個の点を与えて、m条の辺の有向図.各エッジにはエッジ権があり、いくつかのエッジの方向を反転する必要があります.この図をDAGにして、反転されたエッジの最大の重み値を最小化するには、エッジをどのように反転するかを尋ねます.
タイトル構想:試合中に半日見てもこのテーマが最初に何を出力するのか分からなかったので、直接F問題をぶつけました(最後にF問題もぶつけていません.本当の料理QQ)
この問題は最大値の最小化が要求されるため,反転したエッジの最大重み値を二分することを考慮する.有向図にループがあるかどうかを判断するには,トポロジーでソートすることを自然に考えた.二分過程では,辺権がcheck値より大きい辺のみを図に加え(辺権がcheck値以下の後は反転するので,しばらくは気にしない),次にトポロジーソートを行いリングが存在するか否かを判断すればよい.最後にトポロジーソート後の順序関係に基づいて,どの辺が反転するのかを判断し,シナリオ数を出力すればよい.(二分が終わったらもう一度トポロジーソートを走るのを忘れないでください.二分が終わる前に最後に走るトポロジーソートは必ずしも正しいトポロジーソートの順序ではないからです).
具体的な実装はコードを見る:

#include 
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define lowbit(x) x&-x
#define clr(a) memset(a,0,sizeof(a))
#define _INF(a) memset(a,0x3f,sizeof(a))
#define FIN freopen("in.txt","r",stdin)
#define IOS ios::sync_with_stdio(false)
#define fuck(x) cout<G[MX], ans;
int in[MX], pos[MX];
struct edge {
	int u, v, w;
} E[MX];

bool check(int cost) {
	for (int i = 1; i <= n; i++) G[i].clear(), in[i] = 0;
	for (int i = 1; i <= m; i++) {
		if (E[i].w <= cost) continue;
		G[E[i].u].pb(E[i].v);
		in[E[i].v]++;
	}
	queueq;
	for (int i = 1; i <= n; i++) if (in[i] == 0) q.push(i);
	int sz = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		pos[u] = ++sz;
		for (auto v : G[u]) {
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
	return sz == n;
}

int main() {
#ifdef ONLINE_JUDGE
#else
	freopen("in.txt", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
	int l = 0, r = 1e9;
	int res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			res = mid;
			r = mid - 1;
		} else
			l = mid + 1;
	}
	check(res);
	for (int i = 1; i <= m; i++)
		if (E[i].w <= res && pos[E[i].u] > pos[E[i].v]) ans.pb(i);
	printf("%d %d
", res, (int)ans.size());
	for (auto x : ans) printf("%d ", x);
	printf("
");
	return 0;
}