Submission #67348931

---

Source Code Expand

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int read(){int f=0,x=0;char a=getchar();while(!isdigit(a)){if(a=='-')f=1;a=getchar();}while(isdigit(a)){x=x*10+a-'0';a=getchar();}if(f)return -x;return x;}
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    vector<vector<bool> >f(n+1,vector<bool>(n+1,0));
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        f[u][v]=1;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    int ans=INT_MAX;
    do
    {
        vector<vector<bool> >g(n+1,vector<bool>(n+1,0));
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            int u=a[i],v=(i==n)?a[1]:a[i+1];
            if(u>v)swap(u,v);
            g[u][v]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cnt+=f[i][j]^g[i][j];
            }
        }
        ans=min(ans,cnt);
        for(int d=3;d<=n-3;d++)
        {
            vector<vector<bool> >h(n+1,vector<bool>(n+1,0));
            int cn=0;
            for(int i=1;i<=d;i++)
            {
                int u=a[i],v=(i==d)?a[1]:a[i+1];
                if(u>v)swap(u,v);
                h[u][v]=1;
            }
            for(int i=d+1;i<=n;i++)
            {
                int u=a[i],v=(i==n)?a[d+1]:a[i+1];
                if(u>v)swap(u,v);
                h[u][v]=1;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    cn+=f[i][j]^h[i][j];
                }
            }
            ans=min(ans,cn);
        }
    }while(next_permutation(a.begin()+1,a.end()));
    cout<<ans<<'\n';
}
int main()
{
    //freopen(in.in,r,stdin);
    //freopen(out.out,w,stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

Submission Info

Judge Result