CF1100E Andrew and Taxi

套路题又来咯，最大值最小先直接上个二分答案\(lim\)

对于图中的边，若它的权值\(>lim\)的话这条边的方向就确定了，那么直接把这些边连出来跑个拓扑排序看看有没有环即可

如果有环则当前答案一定不合法，否则我们总存在如下的构造方法：

先把权值\(>lim\)的边得到的图的拓扑序搞出来，对于所有权值\(\le lim\)的边，如果它的起点的拓扑序大于终点，则这条边需要被反向

然后这题就做完了，总复杂度\(O(n\log c_i)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int n,m,x[N],y[N],c[N],deg[N],ord[N]; vector <int> v[N];
inline bool check(CI lim)
{
	RI i,idx=0; for (i=1;i<=n;++i) v[i].clear(),deg[i]=0;
	for (i=1;i<=m;++i) if (c[i]>lim) v[x[i]].push_back(y[i]),++deg[y[i]];
	queue <int> q; for (i=1;i<=n;++i) if (!deg[i]) q.push(i);
	while (!q.empty())
	{
		int now=q.front(); ord[now]=++idx; q.pop();
		for (auto to:v[now]) if (!--deg[to]) q.push(to);
	}
	return idx==n;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d%d",&x[i],&y[i],&c[i]);
	int l=0,r=1e9,mid,ret; while (l<=r)
	if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
	vector <int> ans; for (check(ret),i=1;i<=m;++i)
	if (c[i]<=ret&&ord[x[i]]>ord[y[i]]) ans.push_back(i);
	printf("%d %d\n",ret,ans.size());
	for (auto x:ans) printf("%d ",x);
	return 0;
}