本文共 893 字，大约阅读时间需要 2 分钟。

题意

在一个无向图中求一个三元环与外界最小连接边的数量

思路

数据正好，我们考虑枚举一条边，那么这条边的两端就确定了，再枚举一个点，那么判断该点是否和边的两个端点相连，如果是的情况下，我们统计每个点的入度，每次取最小值。

因为是三元环，每个点的内度，也就是每个点必须和其他两个点相连，是2*3=6，最后用总度数减6就是最后答案。

code

#include
   
    #define endl '\n'using namespace std;const int maxn=5e3+5;int vis[maxn][maxn];int n,m;int in[maxn];int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>m;    for(int i=0;i
    
     >u>>v;        in[u]++,in[v]++;        vis[u][v]=vis[v][u]=1;    }    int ans=0x3f3f3f3f;    int flag=0;    for(int i=1;i<=n;i++){
           for(int j=i+1;j<=n;j++){
               if(vis[i][j]){
                   for(int k=j+1;k<=n;k++){
                       if(vis[i][k]&&vis[k][j]){
                           ans=min(ans,in[i]+in[j]+in[k]);                        flag=1;                    }                }            }        }    }    if(flag)        cout<
     
      <
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/104142063 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！