题目链接：http://codeforces.com/contest/1100/problem/E
题目大意：给你n和m，n代表有n个城市，m代表有m条边，然后m行输入三个数，起点，终点，花费。，每一条边的花费指的是将这条路方向反转的花费。然后问你使得整个图没有环的最小花费。（这里的最小花费指的是改变方向的边中，权值最大的那个）。
具体思路：二分答案，我们找出符合题目条件的最优解，check的时候，建立边权大于当前值的边，我们是通过形成的图判断有没有环来检验的，找到最优解之后，将剩余边权的大于最优解的边建立一个图，然后进行拓扑排序。再枚举每一条边，看这一条边的起点和终点的拓扑序，如果说起点的拓扑序大于终点的拓扑序，也就是说这条边应该是方向翻转，然后找出这满足情况的边就可以了。
反思：
1.这样为什么可以呢？昨晚打比赛的时候想到了一种情况，就是如果将当前的一条边翻转之后，原来的图中的环会不再存在，但是会形成新的图，这样的话也是不行的，但是对于这种情况，画画图就知道了，这种情况的话，外面肯定是有一个大环的，我们只需要对这个大环进行操作就可以了（操作的边数没有限制，只要这条边权比当前二分的值小就可以了）。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
using namespace std;
# define ll long long
# define pi acos(-1.0)
const int maxn = 1e5+;
int deg[maxn],head[maxn],ord[maxn],vis[maxn];
int num,n,m;
vector<int>qq;
struct node
{
int fr;
int to;
int nex;
int cost;
} q[maxn],edge[maxn*];
void init()
{
num=;
memset(head,-,sizeof(head));
memset(deg,,sizeof(deg));
}
void addedge(int fr,int to)
{
edge[num].to=to;
edge[num].nex=head[fr];
head[fr]=num++;
deg[to]++;
}
bool check(int t)
{
memset(vis,,sizeof(vis));
init();
for(int i=; i<=m; i++)
{
if(q[i].cost>t)
addedge(q[i].fr,q[i].to);
}
queue<int>wakaka;
for(int i=;i<=n;i++){
if(deg[i]==){
wakaka.push(i);
}
}
while(!wakaka.empty()){
int top=wakaka.front();
wakaka.pop();
vis[top]=;
for(int i=head[top];i!=-;i=edge[i].nex){
int u=edge[i].to;
if(--deg[u]==)wakaka.push(u);
}
}
for(int i=;i<=n;i++){
if(vis[i]==)return false;//(拓扑判环)
}
return true;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=; i<=m; i++)
{
scanf("%d %d %d",&q[i].fr,&q[i].to,&q[i].cost);
}
int l=,r=1e9;
while(l<r)
{
int mid=(l+r)/;
if(check(mid))
{
r=mid;
}
else
l=mid+;
}
init();
for(int i=; i<=m; i++)
{
if(q[i].cost>r)
{
addedge(q[i].fr,q[i].to);
}
}
queue<int>wakaka;
for(int i=; i<=n; i++)
{
if(!deg[i])
wakaka.push(i);
}
memset(ord,,sizeof(ord));
int ans=;
while(!wakaka.empty())
{
int top=wakaka.front();
wakaka.pop();
ord[top]=++ans;
for(int i=head[top]; i!=-; i=edge[i].nex)
{
int to=edge[i].to;
deg[to]--;
if(!deg[to])
{
wakaka.push(to);
}
}
}
for(int i=; i<=m; i++)
{
if(ord[q[i].fr]>ord[q[i].to])//（拓扑序）
{
qq.push_back(i);
}
}
printf("%d %d\n",r,qq.size());
int len=qq.size();
for(int i=; i<len; i++)
{
if(i==)
printf("%d",qq[i]);
else
printf(" %d",qq[i]);
}
printf("\n");
return ;
}