CF1100E Andrew and Taxi

2020.11.3

Link

题目描述

给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。现在求一个改变边方向的方案，使得所选边边权的最大值最小。

解法

容易发现对于一条边，把其删去和把其反向其实是等价的。若不翻转之前，这条边仅处于一个简单环里，那么反过来之后一定不会组成新环。若反过来之后组成了一个新的环，那么不看这条边原图里一定构成了另一个环（画图）。所以对于反向操作直接不走它即可。

若选定了一条边其权值为 (v_i)，那么权值小于等于 (v_i) 的边都可删可不删，就没有约束条件。若选最大的边，那么所有边都可删可不删，一定可以满足要求。而若选择最小的边，只有最小的边能删，约束条件很强。容易发现这是由单调性的，而边权限制在 (10^9) 内，可以直接进行二分了。而对于每次二分，不走权值小于等于 (mid) 的边，判断是否有环即可，可用 (tarjan) 或拓扑排序。

对于第二问，需要求一种具体方案，只能用拓扑。先 (check) 一下 (ans)，把最后的图建出来，此时一定是没有环的，那么这一定是一个 (DAG)。对它进行一遍拓扑，求出拓扑序。枚举原图中每条有向边 (u o v)，若 (u) 的拓扑序比 (v) 的大，说明 (v) 要比 (u) 先被更新，所以这条边一定要反过来。

#include<stdio.h>
#include<string.h>
#define N 200007
#define M 300007

inline int read(){
    int x=0; bool flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

struct E{
    int next,to;
}e[M];
int head[N],cnt=0;

inline void add(int id,int to){
    e[++cnt]=(E){head[id],to};
    head[id]=cnt;
}

int X[M],Y[M],D[M];
int n,m,dep[N],in[N],sta[N],top=0;
bool check(int lim){
    memset(in,0,sizeof(in));
    memset(head,0,sizeof(head));
    cnt=0,top=0;
    int timer=0;
    for(int i=1;i<=m;i++)
        if(D[i]>lim) add(X[i],Y[i]),in[Y[i]]++;
    for(int i=1;i<=n;i++)
        if(!in[i]) sta[++top]=i,dep[i]=++timer;
    while(top){
        int u=sta[top--];
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(--in[v]) continue;
            sta[++top]=v,dep[v]=++timer;
        }
    }
    for(int i=1;i<=n;i++)
        if(in[i]) return 0;
    return 1;
}

int main(){
//    freopen("pestc.in","r",stdin);
//    freopen("pestc.out","w",stdout);
    n=read(),m=read();
    int l=0,r=0,ans;
    for(int i=1;i<=m;i++){
        X[i]=read(),Y[i]=read(),D[i]=read();
        if(D[i]>r) r=D[i];
    }
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
    check(ans);
    int ret=0;
    for(int i=1;i<=m;i++)
        if(D[i]<=ans&&dep[X[i]]>dep[Y[i]]) ret++;
    printf(" %d
",ret);
    for(int i=1;i<=m;i++)
        if(D[i]<=ans&&dep[X[i]]>dep[Y[i]])
            printf("%d ",i);
}