最小环-Dijkstra-Flyod

2021CCPC桂林 E Buy and Delete

题目：

爱丽丝和鲍勃正在有向图 $G$上玩游戏。在 $G$ 中有 $n$ 个顶点，标记为 $1,2,\dots,n$ 。最初， $G$ 中没有边。爱丽丝会先从商店直接购买一些边，然后将它们添加到 $G$ 中。之后，鲍勃需要删除边，直到 $G$ 中没有边为止。在一轮删除中，鲍勃可以从 $G$ 中删除一个边子集 $S$ ，这样当只保留 $S$ 中的边时，图就是非循环的。请注意，爱丽丝可以什么也不买，在这种情况下，删除回合数为 $0$ 。

商店中有 $m$ 条边。爱丽丝有 $c$美元，因此她要购买的边的总价不应超过 $c$ 。爱丽丝希望最大化删除回合数，而鲍勃希望最小化删除回合数。爱丽丝和鲍勃都将以最优方式下棋。请编写一个程序来预测删除回合数。

输入

输入只包含一个案例。

输入的第一行包含三个整数 $n,m$ 和 $c$ ( $2 \leq n\leq 2000$ , $1\leq m \leq 5000$ , $1\leq c\leq 10^9$ )，分别表示 $G$ 中的顶点数、商店中的边数以及爱丽丝有多少美元。

在接下来的 $m$ 行中， $i$ 行 $(1 \le i \le m)$ 包含三个整数$u_i,v_i$ 和 $p_i$ ( $1\leq u_i,v_i\leq n$ , $1\leq p_i\le 100000$)，表示商店中的一条有向边。爱丽丝可以支付 $p_i$ 美元购买，并在 $G$ 中添加一条从顶点 $u_i$ 到顶点 $v_i$ 的边。

输出

打印一行，其中包含一个整数，表示删除轮数。

分析：

无论几个环都会被删两轮，只有边没有环删一轮，还有一个边也买不起的情况为零轮。

$Dijkstra$求最小环即可时间复杂度为$O(nmlogn)$

代码：

vector<PII>e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
    minn=1e18;
    for(int i=1;i<=n;i++)dist[i]=1e18,st[i]=0;
    priority_queue<PII,vector<PII>,greater<PII> >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<=m;i++){
        int u,v,z;cin>>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;}
    }
}