Hướng dẫn giải của Rừng tre lạc lối
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Dễ thấy phải chặt nhị phân sức mạnh.
Để kiếm tra sức mạnh ~k~ có thể tạo nên đồ thị không có chu trình được không thì cần loại bỏ các cạnh có ~c_i \le k~ trước. Nếu những cạnh còn lại vẫn tạo ra chu trình thì không thỏa mãn.
Từ đây ta luôn có cách đảo cạnh sao cho thỏa mãn. Do không còn chu trình nên ta có thể xác định thứ tự topo của các đỉnh trong đồ thị. Xét những cạnh đã bị bỏ, nếu ~u_i~ phải đứng sau ~v_i~ thì ta đảo cạnh, do vậy nên thứ tự topo vẫn được thỏa mãn và không tạo ra chu trình.
Code
#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"
const int maxn = 1e5 + 5;
vector<pi> edge[maxn];
int n, m;
int vis[maxn];
int pos[maxn];
vector<int> topo;
struct e{
int u, v, w;
};
vector<e> v;
bool dfs(int root, int k){
vis[root] = 1;
for(pi &v : edge[root]){
if(v.second <= k) continue;
if(vis[v.first] == 1) return true;
if(vis[v.first]) continue;
if(dfs(v.first, k)) return true;
}
vis[root] = 2;
topo.push_back(root);
return false;
}
bool check(int k){
topo.clear();
set0(vis);
for(int i = 1; i <= n; i++)
if(!vis[i]){
if(dfs(i, k)) return false;
}
return true;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
edge[u].push_back({v, w});
::v.push_back({u, v, w});
}
int l = 0, r = 1e9, ans = -1;
while(l <= r){
int m = (l + r) >> 1;
if(check(m)) ans = m, r = m - 1;
else l = m + 1;
}
check(ans);
for(int i = 0; i < n; i++) pos[topo[i]] = i;
vector<int> rev;
for(int i = 0; i < m; i++){
if(pos[v[i].u] < pos[v[i].v]) rev.push_back(i + 1);
}
cout << ans << ' ' << rev.size() << '\n';
for(int &d : rev) cout << d << ' ';
}