题意

假设我们有 $k$ 个交通控制器。它们可以翻转所有权重小于等于 $k$ 的边。然后，我们从图中移除这些边，对剩余图进行拓扑排序，并按照拓扑排序的顺序定向其他边。如果在移除边之后图中仍然存在环，那么即使有 $k$ 个交通控制器，我们也无法消除这些环。否则，通过添加边，我们不会引入新的环。

思路

参数 $k$ 可以通过二分查找来迭代。在二分查找中，我们不必遍历所有可能的 $k$ 值，而只需遍历那些出现在边上的权重值。

算法步骤

1. 对边的权重进行排序，得到候选的 $k$ 值集合（即所有边的权重）。
2. 在候选值上进行二分查找：
   • 对于当前 $k$，移除所有权重小于等于 $k$ 的边。
   • 对剩余图进行拓扑排序。
   • 如果剩余图中存在环，则当前 $k$ 不可行，需要增大 $k$。
   • 否则，当前 $k$ 可行，尝试减小 $k$。
3. 返回最小的可行 $k$。

复杂度分析

时间复杂度为 $O((n+m)\log C)$ 或 $O((n+m)\log m)$，其中 $n$ 为节点数，$m$ 为边数，$C$ 为权重范围。

代码说明

• 使用二分查找框架，每次检查当前 $k$ 是否可行。
• 检查过程：构建剩余图，进行拓扑排序（如 Kahn 算法），检测是否存在环。
• 二分查找的搜索空间为所有边的权重值，而非连续整数。

#include <bits/stdc++.h>
using namespace std;
const int Maxn=100005;
int n,m,head[Maxn],cnt,maxi,ct[Maxn],dfn[Maxn],ans[Maxn],tot,vis[Maxn];
struct edg
{
	int nxt,to,w;
}edge[Maxn];
void add(int x,int y,int w)
{
	edge[++cnt]=(edg){head[x],y,w};
	head[x]=cnt;
}
int lim; 
bool dfs(int u,int id)
{
	vis[u]=-1;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(edge[i].w<=lim) continue;
		if(vis[to]!=-1&&vis[to]) continue;
		if(vis[to]==-1||dfs(to,id)) return true;
	}
	vis[u]=id;
	return false;
}
bool in[Maxn];
void work(int x)
{
	queue <int> Qu;
	int c=0;
	for(int i=1;i<=m;i++)
		if(edge[i].w>lim)
			ct[edge[i].to]++;
	for(int i=1;i<=n;i++)
		if(!ct[i]) Qu.push(i),in[i]=true;
	while(!Qu.empty())
	{
		int u=Qu.front();
		Qu.pop();
		dfn[u]=++c;
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(edge[i].w>lim)
			{
				ct[to]--;
				if(!ct[to]&&!dfn[to]&&!in[to]) in[to]=true,Qu.push(to);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		maxi=max(maxi,w);
	}
	int lt=0,rt=maxi;
	while(lt+1<=rt)
	{
		int mid=(lt+rt)/2;
		lim=mid;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dfs(i,i))
			{
				lt=mid+1;
				goto A;
			}
		rt=mid;
		A:;
	}
	lim=lt;
	work(lt);
	for(int u=1;u<=n;u++)
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(edge[i].w<=lt)
				if(dfn[to]<dfn[u]) ans[++tot]=i;
		}
	printf("%d %d\n",lt,tot);
	for(int i=1;i<=tot;i++) printf("%d ",ans[i]); 
	return 0;
}