权值最小有向环

发表于2021-11-15更新于2022-04-08阅读次数

我的标题都去哪了？

简单图

Buy and Delete Gym - 103409E

思路：用n次dijkstra求出所有(u,v)之间的最短路径。然后最小环就为min(dis[ u ] [ v ]+dis[ v ] [ u ]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e3+11;
const ll maxm=5e3+11;
struct Edge{
    ll to,w,nx;
}e[maxm];
ll head[maxn],vis[maxn],dis[maxn][maxn];
ll n,m,tmp,flag,c,start;
priority_queue<P,vector<P>,greater<P>> q;
void add(ll u,ll v,ll w){
    e[tmp]={v,w,head[u]};head[u]=tmp++;
}
void dijkstra(){
    q.push({0,start});dis[start][start]=0;
    while(!q.empty()){
        ll u=q.top().second;q.pop();
        if(vis[u])  continue;
        vis[u]=1;
        for(ll i=head[u];i;i=e[i].nx){
            ll v=e[i].to;
            if(dis[start][u]+e[i].w<dis[start][v]){
                dis[start][v]=dis[start][u]+e[i].w;
                q.push({dis[start][v],v});
            }
        }
    }
}
void solve(){
    if(flag==0){
        cout<<"0"<<endl;return ;
    }
    memset(dis,0x1f,sizeof(dis));
    for(ll i=1;i<=n;i++){
        start=i;
        memset(vis,0,sizeof(vis));
        dijkstra();
    }
    ll minn=INF;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(i==j)  continue;
            minn=min(minn,dis[i][j]+dis[j][i]);
        }
    }
    if(c<minn){
        cout<<"1"<<endl;return ;
    }
    cout<<"2"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>c;
    flag=0;tmp=1;
    for(ll i=1;i<=m;i++){
        ll u,v,w;cin>>u>>v>>w;add(u,v,w);
        if(w<=c)  flag=1;
    }   
    solve();
    return 0;
}

仙人掌图

P2661 [NOIP2015 提高组] 信息传递

题意：求最小环，无权值。

法一：拓扑排序

把非环边都删去，剩下的就都是环了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
struct Edge{
    ll to,nx;
}e[maxn];
ll head[maxn],vis[maxn],dr[maxn];
ll n,tmp=1;
void add(ll u,ll v){
    e[tmp]={v,head[u]};head[u]=tmp++;
}
ll dfs(ll u){
    vis[u]=1;
    for(ll i=head[u];i;i=e[i].nx){
        ll v=e[i].to;
        if(vis[v])  return 1;
        else  return dfs(v)+1;
    }
}
void solve(){
    queue<ll> q;
    for(ll i=1;i<=n;i++)  if(dr[i]==0)  q.push(i),vis[i]=1;
    while(!q.empty()){
        ll u=q.front();q.pop();
        for(ll i=head[u];i;i=e[i].nx){
            ll v=e[i].to;
            dr[v]--;
            if(dr[v]==0)  q.push(v),vis[v]=1;
        }
    }
    ll ans=INF;
    for(ll i=1;i<=n;i++){
        if(!vis[i]){
            ans=min(ans,dfs(i));
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(ll u=1;u<=n;u++){
        ll v;cin>>v;add(u,v);dr[v]++;
    }   
    solve();
    return 0;
}

dfs树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
struct Edge{
    ll to,nx;
}e[maxn];
ll head[maxn],vis[maxn],d[maxn],tree[maxn];
ll n,tmp=1,ans=INF;
void add(ll u,ll v){
    e[tmp]={v,head[u]};head[u]=tmp++;
}
void dfs(ll u){
    vis[u]=1;tree[u]=1;
    for(ll i=head[u];i;i=e[i].nx){
        ll v=e[i].to;
        if(tree[v]){
            ans=min(ans,d[u]-d[v]+1);
            tree[u]=0;
            return ;
        }
        d[v]=d[u]+1;
        if(!vis[v])  dfs(v);
    }
    tree[u]=0;
}
void solve(){
    for(ll i=1;i<=n;i++){
        if(!vis[i]){
            d[i]=1,dfs(i);
        }
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(ll u=1;u<=n;u++){
        ll v;cin>>v;add(u,v);
    }       
    solve();
    return 0;
}

带权并查集

踩坑：带权并查集，d[ x ]+=d[ fa[ x ] ]，即使是路径压缩之后，
每次查询x的父节点，还是会执行这条语句，所以得让d[ fa[ x ] ]为0，不然d[ x ]会越来越大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ll fa[maxn],d[maxn];
ll found(ll x){
    if(fa[x]==x)  return x;
    ll fx=found(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=fx;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(ll i=1;i<maxn;i++)  fa[i]=i;
    ll n;cin>>n;
    ll ans=INF;
    for(ll u=1;u<=n;u++){
        ll v;cin>>v;
        ll fu=found(u),fv=found(v);
        if(fu==fv){
            ans=min(ans,d[v]-d[u]+1);
            continue;
        }
        fa[u]=v;
        d[u]=1;
    }   
    cout<<ans<<endl;
    return 0;
}