题目链接:https://codeforces.com/contest/1100/problem/E
题意是n个点,m条有向边,每条边都有一个权值,将某些边变向,使得图变成一个无环图,要使所有变向的边中权值最大的最小,输出这个最大的最小值和变向的边。
大致思路是二分答案,然后用拓扑排序去判断是否存在环。具体的操作是我们把每次枚举的mid作为建边的依据,把大于mid的边建起来,因为答案是变向的边的最大值,所以比mid大的边都是不用变向的边,所以将他们建好边以后判断一下图是否是无环图(入队个数等于n就是无环图),如果不是无环图的话,说明这些边有些还需要变向,那么就扩大mid的值。如果这个图是一个无环图的话,就更新ans数组,更新的过程是它的权值要小于等于mid,然后按它的拓扑顺序进行变向,并将mid缩小去找更小的答案。有一个讲的不错的文章,对于更新ans数组的过程有详细的解释,可以去看看:https://www.geeksforgeeks.org/
AC代码:
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
int x, y, w;
}Edge[maxn];
int pre[maxn], dep[maxn], pos[maxn];
vector<int> ans;
int n,m;
bool Check(int xx){
vector<int> v[maxn];
memset(dep, 0, sizeof(dep));
for(int i=1;i<=m;i++){
if(Edge[i].w > xx){
v[Edge[i].x].push_back(Edge[i].y);
dep[Edge[i].y] ++;
}
}
queue<int> q;
int cnt = 0, yy = 0;
for(int i=1;i<=n;i++) if(dep[i] == 0) q.push(i), pos[i] = ++cnt, yy++;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=0;i<v[u].size();i++){
int to = v[u][i];
if(--dep[to] == 0){
q.push(to);
pos[to] = ++ cnt;
yy ++;
}
}
}
if(yy != n) return false;
ans.clear();
for(int i=1;i<=m;i++){
if(Edge[i].w <= xx && pos[Edge[i].y] < pos[Edge[i].x]) ans.push_back(i);
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&Edge[i].x,&Edge[i].y,&Edge[i].w);
}
int l = 0, r = 1e9+2, mid, xx;
while(l <= r){
mid = (l + r) >> 1;
if(Check(mid)) r = mid - 1, xx = mid;
else l = mid + 1;
}
// Check(xx); 我觉得这里不需要再更新一次ans数组了 因为xx和ans是同步更新的
printf("%d %d\n",xx, ans.size());
for(int i=0;i<ans.size();i++){
printf("%d ", ans[i]);
}
return 0;
}