codeforces 1100E-Andrew and Taxi

传送门：QAQQAQ

题意：给你一个图，每条边有边权，现在你可以对边进行反转，使图中不存在环，你需要使得反转的边的边权集合中的最大值最小，并输出任意一组解。

思路：二分+拓扑排序

使得最大值最小，自然而然想到二分（其实我先想到tarjan，发现环套环无法处理）

那么我们二分枚举答案，把小于mid的边全部拆了，判断剩下边是否成环（dfs，之前染色方法玄学错误），若没有环则当前mid成立

为什么呢？——如果我们把一条删掉的边连上，无论怎么摆都会形成一个环，那么原先的边一定有一条大环，所以原先这种情况就不可能成立（画个图可以模拟一下）

那么现在我们已经证明删掉的边按照一定顺序摆一定不会有环，我们只需要找出一种这样的顺序。

进行拓扑排序，如果一条边是由拓扑序大的连向拓扑序小的，我们就将它反转，这样就可以保证没有坏

证明：删掉比mid小的边后剩下的一定是若干个DAG，产生环的根本原因是儿子有返祖边，而父亲拓扑序一定比儿子小（因为是用queue维护的），所以若所有边都从拓扑序小的连向拓扑序大的，就一定不会产生返祖边

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

 

struct node{

    int from,to,cost,id;

}E[N];

vector<int> v;

 

int first[N],nxt[N],point[N],w[N],e=,dfn[N];

void add_edge(int x,int y,int z,int num)

{

    e++;

    E[num].id=e;

    point[e]=y; w[e]=z;

    nxt[e]=first[x];

    first[x]=e;

}

 

bool cmp(node x,node y)

{

    if(x.cost==y.cost) return x.id<y.id;

    return x.cost<y.cost;

}

 

int vis[N],bl[N],n,m,judge,best,in[N];

void dfs(int u)

{

    vis[u]=;

    for(int i=first[u];i!=-;i=nxt[i])

    {

        if(bl[i]) continue;

        int p=point[i];

        if(vis[p]==)

        {

            judge=;

            return;

        }

        if(!vis[p]) dfs(p);

    }

    vis[u]=;

    return;

}

 

bool check(int mid)

{

    judge=;

    memset(vis,,sizeof(vis));

    memset(bl,,sizeof(bl));

    for(int i=;i<=mid;i++) bl[E[i].id]=;

    for(int i=;i<=n;i++)

    {

        if(!vis[i])

        {

            dfs(i);

        }

    }

    return judge;

}

 

int main()

{

    memset(first,-,sizeof(first));

    memset(nxt,-,sizeof(nxt));

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&E[i].from,&E[i].to,&E[i].cost);

        add_edge(E[i].from,E[i].to,E[i].cost,i);

    }

    sort(E+,E+m+,cmp);

    int l=,r=m,mid;best=-;

    while(l<=r)

    {

        mid=(l+r)>>;

        if(check(mid)) r=mid-,best=mid;

        else l=mid+;

    }

    queue<int> q;int tot=;

    memset(in,,sizeof(in));

    for(int i=best+;i<=m;i++)

    {

        in[E[i].to]++;

    }

    for(int i=;i<=n;i++) if(!in[i]) q.push(i);

    memset(bl,,sizeof(bl));

    for(int i=;i<=best;i++) bl[E[i].id]=;

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        dfn[now]=++tot;

        for(int i=first[now];i!=-;i=nxt[i])

        {

            if(bl[i]) continue;

            int pos=point[i];

            in[pos]--;

            if(!in[pos]) q.push(pos);

        }

    }

    for(int i=;i<=best;i++)

    {

        int x=E[i].from;

        int y=E[i].to;

        if(dfn[x]>dfn[y]) v.push_back(E[i].id);

    }

    printf("%d %d\n",E[best].cost,(int)v.size());

    for(int i=;i<(int)v.size();i++) printf("%d ",v[i]);

    return ;

}

巴特西

codeforces 1100E-Andrew and Taxi

最新文章

热门文章