最小环-Dijkstra-Floyd

2021 CCPC 桂林 E - Buy and Delete

题目描述

Alice 和 Bob 在有向图 $G$ 上玩游戏。最初图中没有边，Alice 可以先购买一些边加入图中，购买总价不能超过 $c$。之后 Bob 每轮可以删除一个边集 $S$，要求只保留 $S$ 中的边时图是无环的。Bob 不断删除直到图中没有边。

Alice 希望最大化删除轮数，Bob 希望最小化删除轮数。要求预测最终删除轮数。

输入

输入包含一个测试用例。

第一行包含三个整数 $n,m,c$，分别表示点数、可购买边数和 Alice 的预算，满足：

$$2 \le n \le 2000, \quad 1 \le m \le 5000, \quad 1 \le c \le 10^9$$

接下来 $m$ 行，每行三个整数 $u_i,v_i,p_i$，表示一条从 $u_i$ 到 $v_i$、价格为 $p_i$ 的有向边。

输出

输出一个整数，表示删除轮数。

分析

如果一条边都买不起，答案为 $0$。

如果可以买至少一条边，但买不到任何有向环，那么图是 DAG，一轮就能删完，答案为 $1$。

如果预算内可以买出至少一个有向环，那么答案为 $2$。因此问题可以转化为：判断预算 $c$ 内是否存在有向环。

做法是枚举每个点作为起点，跑最短路寻找回到起点的最小环。如果某个最小环权值不超过 $c$，答案就是 $2$；否则根据是否能买任意一条边判断答案为 $1$ 或 $0$。

时间复杂度约为：

$$O(nm\log n)$$

代码

vector<int> e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
    minn=1e18;
    for(int i=1;i,greater >q;
    dist[u]=0;
    q.push({dist[u],u});
    while(q.size()){
        auto [dis,ver]=q.top();
        q.pop();
        if(st[ver])continue;
        st[ver]=1;
        for(auto [v,w]:e[ver]){
            if(v==u)minn=min(minn,dis+w);
            if(st[v])continue;
            if(dist[v]>dis+w){
                dist[v]=dis+w;
                q.push({dist[v],v});
            }
        }
    }
}
void solve(){
    cin>>n>>m>>c;
    int ans=0;
    for(int i=1;i>u>>v>>z;
        e[u].pb({v,z});
        if(z<=c)ans=1;
    }
    for(int i=1;i<=n;i++){
        Dijkstra(i);
        if(minn<=c){ans=2;break;}
    }
}