Codeforces Round 532 (Div. 2) E.Andrew and Taxi 解题日志

2019-01-23

字数统计: 425字 | 阅读时长: 2分

简单题意：

n个点m条边，每条边都有边权。
反转边向需要花费边权，整张图可以共用花费。
问至少花费多少使得图为DAG，并输出反转方案。

思路：

二分花费x。
对于所有权值大于x的边，我们无法反转，所以必须建图。
对于建出的图拓扑排序，得到入队顺序。
如果是DAG，遍历所有边，对于入点和出点的拓扑序作比较，如果拓扑序相反，则反转这条边。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int u[maxn],v[maxn],w[maxn];
int n,m;
int deg[maxn],dfn[maxn];
vector<int> g[maxn];
vector<int> ans;
bool check(int x){
    for(int i=1;i<=n;i++){
        g[i].clear();
        deg[i]=dfn[i]=0;
    }
    for(int i=1;i<=m;i++){
        if(w[i]>x){
            g[u[i]].push_back(v[i]);
            deg[v[i]]++;
        }
    }
    int df=0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!deg[i]){
            q.push(i);dfn[i]=++df;
        }
    }
    while(!q.empty()){
        int now = q.front();q.pop();
        for(auto to:g[now]){
            if(dfn[to])return 0;
            deg[to]--;
            if(!deg[to]){
                dfn[to]=++df;
                q.push(to);
            }
        }
    }
    if(df!=n)return 0;
    ans.clear();
    for(int i=1;i<=m;i++){
        if(dfn[u[i]]>dfn[v[i]]){
            if(w[i]>x)return 0;
            ans.push_back(i);
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",u+i,v+i,w+i);
    }
    int l=-1,r=1e9+7;
    while(r-l>1){
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
    check(r);
    cout<<r<<" "<<ans.size()<<endl;
    for(auto v:ans)cout<<v<<" ";
    return 0;
}