CF1100E Andrew and Taxi 题解

题意

?个有向图，改变?些边的?向，使得图中没有环，求使得所选边边权最大值最?的?案。

分析

如果边权最大值小的可行，那最大值更大的也一定可行。因此可以二分边权最大值，每次把边权比最大值大的加入图中，如果没有环，那把所有没加的边的方向都改成拓扑序的方向就一定可以满足，如果有环说明不可行。二分出来最小的最大值后，重新建图，把所有与拓扑序相反的边反转方向即可。

代码

#include 
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
    register T1 x=0;register bool f=false;char ch=getchar();
    while(ch<'0') f|=(ch=='-'),ch=getchar();
    while(ch>='0') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x=(f?-x:x);a=x;qread(b...);
}
templateinline T1 qmax(const T1 &x,const T2 &y){return x>y?x:y;}
templateinline T1 qmin(const T1 &x,const T2 &y){return xedge;
void add_edge(int u,int v,int w,int id){edge.push_back(Edge(v,w,head[u],id));head[u]=edge.size()-1;}
int in[MAXN],ans=2139062143;
vectortopo;
int topo_sort()
{
    topo.clear();int i;queueq;
    for(i=1;i<=n;i++) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();topo.push_back(u);
        for(i=head[u];i!=-1;i=edge[i].nxt) if(!(--in[edge[i].to])) q.push(edge[i].to);
    }
    return topo.size();
}
int x[MAXN],y[MAXN],z[MAXN];
void make(int mid) // 建图
{
    edge.clear();mem(head,-1);mem(in,0);
    for(int i=0;imid) add_edge(x[i],y[i],z[i],i+1),in[y[i]]++;
}
bool check(int mid)
{
    make(mid);
    return topo_sort()==n; // 如果topo数组中包含所有点，说明没有环
}
int mp[MAXN];setans1;
int main()
{
    qread(n,m);int i,j;
    int l=0,r=0;
    for(i=0;i>1;
        if(check(mid)) r=mid-1,ans=qmin(ans,mid);
        else l=mid+1;
    }
    check(ans);
    for(int i=0;imp[edge[j].to]) ans1.insert(edge[j].id); // 该边方向与拓扑序相反
    printf("%d %d\n",ans,ans1.size());
    for(auto i:ans1) printf("%d ",i);
    return 0;
}