CF -1100 E Andrew and Taxi（二分+拓扑）

题目大意：一张n个点m条边的有向图，可以反转其中一些边的方向，使得图中不存在环。要求反转的边中权值最大的权值尽可能地小。

这可能是我第一次在比赛题中遇到拓扑排序相关的题了，，一直以为这玩意没用来着。。

解题思路：二分要反转的边权最大的边权。然后拓扑判环，输出要用到拓扑排序，因为并不是所有小于这个二分出来的值的路都需要反转，这样可能会形成新环，需要判断方向是否是由先拓扑的到后拓扑的，如果不是的的话，反转。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int u,v,c,next;
}edge[100100];

int cnt,head[100100],in[100010],top[100010];
int n,m;

void add(int u,int v,int w)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].c=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int check(int mid)
{
    int sum=0;
    vector<int>e[100010];
    memset(in,0,sizeof(in));
    for(int i=0;i<m;i++)//入度统计+建图
    {
        if(edge[i].c>mid)
        {
            e[edge[i].u].push_back(edge[i].v);
            in[edge[i].v]++;
        }
    }

    queue<int>q;
    for(int i=1;i<=n;i++)//入度为零的点入队
    {
        if(!in[i])
        {
            q.push(i);
            top[i]=++sum;
        }
    }

    while(!q.empty())//删边入队（拓扑排序）
    {
        int u=q.front();
        q.pop();
        for(auto v:e[u])
        {
            --in[v];
            if(!in[v])
            {
                q.push(v);
                top[v]=++sum;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(in[i])
            return 0;
    }

    return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cnt=0;
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    int u,v,w;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
    }
    int l=0,r=1e9;
    int mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    check(ans);
    vector<int>path;
    for(int i=0;i<m;i++)
    {
        if(edge[i].c<=ans&&top[edge[i].u]>top[edge[i].v])
           path.push_back(i+1);
    }
    cout<<ans<<" "<<path.size()<<endl;
    for(auto i:path)
    {
        cout<<i<<" ";
    }
    return 0;
}