\(\color{black}\texttt{A. 反转Dag图}\)

题目描述

给定一个有向图，每次操作可以花费 \(w_i\) 的代价来反转边 \(i\)，最终总代价为每次操作代价的最大值。求最少需要多少代价才能使这张图变为一个 DAG。

思路

首先看这个问题的简化版：把反转操作变为删除操作。

可以用二分解决：二分出最终答案 \(x\)，把所有代价 \(\le x\) 的边删掉，再拓扑排序判断即可。

这时可以发现，两个问题竟然是等价的：假设有 \(u\rightarrow v\) 这条边，如果 \(u\) 的拓扑序小于 \(v\)，则这条边不用删除或翻转；否则这条边必须删除或翻转。即要删除一定会翻转，反之亦然。

代码

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MAXN = 100001, MAXM = 100005;

struct Edge {
  int v, w;
};

int n, m, in[MAXN];
vector<Edge> e[MAXN];

void FileIO(const string &s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

bool check(int x) {
  queue<int> que;
  fill(in + 1, in + n + 1, 0);
  for(int i = 1; i <= n; ++i) {
    for(auto [v, w] : e[i]) {
      in[v] += (w > x);
    }
  }
  for(int i = 1; i <= n; ++i) {
    if(!in[i]) {
      que.push(i);
    }
  }
  for(; !que.empty(); ) {
    int u = que.front();
    que.pop();
    for(auto [v, w] : e[u]) {
      if(w > x && !(--in[v])) {
        que.push(v);
      }
    }
  }
  for(int i = 1; i <= n; ++i) {
    if(in[i]) {
      return 0;
    }
  }
  return 1;
}

int Binary_Search() {
  int l = 0, r = 1000000001;
  for(; l < r; ) {
    int mid = (l + r) >> 1;
    (check(mid) ? r = mid : l = mid + 1);
  }
  return l;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  FileIO("antidag");
  cin >> n >> m;
  for(int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    e[u].push_back({v, w});
  }
  cout << Binary_Search();
  return 0;
}