P6175

Aryper · 2021-11-16 23:09:00 · 个人记录

无向图的最小环问题

论 Floyd 的奇怪用法。

主要是处理环的路径不重复的问题。

有一些技巧。

时间复杂度 O(n^3)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e2,inf=0x1f1f1f1f1f1f1f1f;

ll n,m,ans,u,v,d;

ll f[N+5][N+5],edge[N+5][N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();

    memset(f,0x1f,sizeof(f));
    memset(edge,0x1f,sizeof(edge));
    for(ll i=1;i<=n;i++) edge[i][i]=f[i][i]=0;

    for(ll i=1;i<=m;i++) {
        u=read();v=read();d=read();
        f[u][v]=f[v][u]=min(f[u][v],d);
        edge[u][v]=edge[v][u]=min(edge[u][v],d);
    }

    ans=inf;
    for(ll k=1;k<=n;k++) {
        for(ll i=1;i<k;i++) {
            for(ll j=i+1;j<k;j++) {
                ans=min(ans,f[i][j]+edge[i][k]+edge[k][j]);
            }
        }
        for(ll i=1;i<=n;i++) {
            for(ll j=1;j<=n;j++) {
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }

    if(ans>=inf) printf("No solution.");
    else write(ans);

    return 0;
}