【CodeForces 574B】Bear and Three Musketeers

【题解】

枚举每一条边(x,y)
然后再枚举y的出度z
看看g[x][z]是否等于1(表示联通)
如果等于1就说明找到了一个三元环,则尝试用它们的出度和-6更新答案就好。
时间复杂度O(M*N)

【代码】

#include <bits/stdc++.h>

#define rep1(i,a,b) for (int i = a;i <= b;i++)

using namespace std;

const int N = 4e3;

int n,m;

vector<int> g[N+10];

bool G[N+10][N+10];

vector<pair<int,int> > v;

int main()

{

    #ifdef LOCAL_DEFINE

        freopen("rush.txt","r",stdin);

    #endif // LOCAL_DEFINE

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >> n >> m;

    rep1(i,1,m){

        int x,y;

        cin >> x >> y;

        v.push_back({x,y});

        G[x][y] = G[y][x] = 1;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    int ans = -1;

    for (int i = 0;i < m;i++){

        int x = v[i].first,y = v[i].second;

        for (int j = 0;j < (int) g[y].size();j++){

            int z = g[y][j];

            if (G[x][z]){

                int temp = g[x].size();

                temp+=g[y].size();

                temp+=g[z].size();

                temp-=6;

                if (ans==-1){

                    ans = temp;

                }else{

                    ans = min(ans,temp);

                }

            }

        }

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

【CodeForces 574B】Bear and Three Musketeers

最新文章

热门文章