CF 1100E Andrew and Taxi

题目描述

http://codeforces.com/problemset/problem/1100/E

简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，现在需要改变某些边的方向，使得原图变成有向无环图，求一个改变边的方案，使得被改变的边的边权最大值最小

$n,m\le 10^5$

Solution

首先我们考虑二分，然后就是判断在只改变 $[1,mid]$ 的边的方向时能否将原图变成一个有向无环图

注意到我们只需要保证 $[mid+1,r]$ 的边无环，即能够拓扑排序即可，因为 $[1,mid]$ 的方向只需要按照 $[mid+1,r]$ 的边拓扑排序得到的拓扑序由小向大连接即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 100010
using namespace std;

int n, m;

struct Edge {
    int fr, to, next, w, id;

    friend bool operator < (const Edge &u, const Edge &v) { return u.w < v.w; }
} e[maxn], E[maxn]; int c1, head[maxn], in[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; ++in[v];
    e[c1].next = head[u]; head[u] = c1++;
}

void init() {
    fill(head, head + maxn, -1); c1 = 0;
    for (int i = 1; i <= n; ++i) in[i] = 0;
}

int id[maxn];
bool topsort() {
    queue<int> Q;
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    int cnt = 0; 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); id[u] = ++cnt;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0) Q.push(v); 
        }
    }
    return cnt == n;
} 

bool check(int x) {
    init();
    for (int i = x + 1; i <= m; ++i) 
        add_edge(E[i].fr, E[i].to);
    return topsort();  
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> E[i].fr >> E[i].to >> E[i].w, E[i].id = i; 
    sort(E + 1, E + m + 1);
    int l = 0, r = m, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    } init(); check(ans); vector<int> Ans;
    for (int i = 1; i <= ans; ++i)
        if (id[E[i].fr] > id[E[i].to]) Ans.push_back(E[i].id);
    cout << E[ans].w << " " << Ans.size() << "\n";
    for (auto u : Ans) cout << u << " "; 
    return 0;
}