题目意思
给你一个 $n$ 个点，$m$ 条边的有向图，每一个边有一个权值。现在你可以修改任意条边的方向，使得原图变为有向无环图。求修改的边的最大值最小时的方案。
思路
看到最大值最小便很容易想到二分答案（即修改的边中的最大值），我们将这个二分的数设为 $mid$。那么很明显，图中的边会被分为两大类：
- 权值大于 $mid$ 的边。
- 权值小于等于 $mid$ 的边。
需要解决的问题：
prob1:对于第一类边我们显然是无法修改方向的，如果存在一个环且换上全是一类边。则这个 $mid$ 显然无法让原图变成有向无环图。
prob2:对于第二类边我们可以改变其方向，直接统计有哪些需要改变方向的边即可。
于是我们十分欣喜的发现，这两个问题都可以用拓扑排序来解决。对于prob1，我们可以将原图的二类边去掉，然后跑拓扑排序判环。对于prob2，我们在prob1的拓扑排序中顺便记录拓扑序，如果出现一个二类边是由拓扑序在后面的点指向拓扑序在前面的点，就说明这条边构成了环，将这条边记录下来即可。
AT LAST 上代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>g[maxn];//邻接表
vector<int>ans;//记录方案
int n,m,rd[maxn],f[maxn],u[maxn],v[maxn],dist[maxn];
//u表示一条边的起点，v表示一条边的终点,dist表示一条边的权值
//rd表示一个点的入度，f表示一个点在新图中的拓扑序
bool check(int x){
for(int i=1;i<=n;i++){rd[i]=0;g[i].clear();}
for(int i=1;i<=m;i++){//建图(即只保留一类边)
if(dist[i]<=x)continue;//把边权大于二分答案的边建图
g[u[i]].push_back(v[i]);
rd[v[i]]++;
}
queue<int>q;int cnt=0;
for(int i=1;i<=n;i++){if(rd[i]==0)q.push(i);}
while(!q.empty()){//拓扑排序
int p=q.front();f[p]=++cnt;q.pop();
for(int i=0;i<g[p].size();i++){
int y=g[p][i];
if(--rd[y]==0)q.push(y);
}
}
if(cnt!=n)return 0;//判断是有环
ans.clear();//记录方案（即需要换方向的二类边）
for(int i=1;i<=m;i++){
if(dist[i]<=x&&f[u[i]]>f[v[i]])ans.push_back(i);
}// 如果从topo序大的点
// 指向topo序小的点则会产生环
// 需要颠倒过来
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u[i],&v[i],&dist[i]);//将边的信息用三元组存下来
}
int l=0,k,r=1e9+10,mid=(l+r)>>1;
while(l<=r){ //二分颠倒过来的路径的最大值
mid=(l+r)>>1;
if(check(mid)){ //合法，记录答案
k=mid;//即最小的最大值
r=mid-1;//这里不break是因为要找到跟小的k
}else l=mid+1;
}
printf("%d %d\n",k,ans.size());
for(int i=0;i<ans.size();i++){
printf("%d ",ans[i]);
}
printf("\n");
return 0;
}