CF1100E

i207M给的题

省选前-小题解合集

给定一张有向图，每条边有边权。你可以花费边权的代价反转一条边，使得原图中没有环。最小化反转的边权的最大值。

首先二分，然后考虑判定。

转化为有些边可以翻转，有些边不可以翻转，使得图中没有环

我们把不能反向的边拿出来，然后跑拓扑排序判环，如果有环则无解，不然一定有一种方案，加入那些可以改变方向的边而不产生环。

新加的边方向：拓扑序小的连向拓扑序大的

有环一定是大的拓扑序连向小的拓扑序有一条边

而这样是一定没有环的！

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

int n,m;

struct edge{

    int x,y,z;

}b[N];

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

int dfn[N],df;

int q[N],l,r;

int du[N];

int mem[N],tot;

bool topo(){

    memset(dfn,,sizeof dfn);

    l=,r=;

    df=;

    for(reg i=;i<=n;++i){

        if(du[i]==){

            q[++r]=i;

            dfn[i]=++df;

        }

    }

    while(l<=r){

        int x=q[l++];

        for(reg i=hd[x];i;i=e[i].nxt){

            int y=e[i].to;

            du[y]--;

            if(!du[y]){

                dfn[y]=++df;

                q[++r]=y;

            }

        }

    }

    for(reg i=;i<=n;++i){

        if(!dfn[i]) return false;

    }

    return true;

}

bool che(int mid){

    memset(du,,sizeof du);

    memset(hd,,sizeof hd);

    cnt=;

    for(reg i=;i<=m;++i){

        if(b[i].z>mid){

            add(b[i].x,b[i].y);

            ++du[b[i].y];

        }

    }

    return topo();

}

int main(){

    rd(n);rd(m);

    int x,y,z;

    int L=,R=;

    for(reg i=;i<=m;++i){

        rd(x);rd(y);rd(z);R=max(R,z);

        b[i].x=x;b[i].y=y;b[i].z=z;

    }

    int ans=;

    while(L<=R){

        int mid=(L+R)>>;

        if(che(mid)){

            ans=mid;R=mid-;

        }else L=mid+;

    }

    printf("%d ",ans);

    bool haha=che(ans);

    for(reg i=;i<=m;++i){

        if(dfn[b[i].x]>dfn[b[i].y]){

            mem[++tot]=i;

        }

    }

    sort(mem+,mem+tot+);

    printf("%d\n",tot);

    for(reg i=;i<=tot;++i){

        printf("%d ",mem[i]);

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/1/16 11:46:04

*/

巴特西

CF1100E

最新文章

热门文章