C++(g++ 7.5.0) 解法, 执行用时: 40ms, 内存消耗: 620K, 提交时间: 2022-11-15 11:43:51

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ff double
#define pb push_back
#define int long long
#define all(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof a)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const int N = 55 << 1;
const int M = N * N << 3;
const int INF = 1e18;
int n, m, s, t;
int g[N][N];
int h[N], e[M], ne[M], f[M], idx;
int dep[N], cur[N];

void add(int a, int b, int c) {
    e[idx] = b; f[idx] = c; ne[idx] = h[a]; h[a] = idx ++;
    e[idx] = a; f[idx] = 0; ne[idx] = h[b]; h[b] = idx ++;
}

bool bfs() {
    queue<int> q; q.push(s);
    mem(dep, -1); dep[s] = 0;
    cur[s] = h[s];
    while(q.size()) {
        int pos = q.front(); q.pop();
        for(int i = h[pos]; ~i; i = ne[i]) {
            int j = e[i];
            if(dep[j] == -1 && f[i]) {
                dep[j] = dep[pos] + 1;
                cur[j] = h[j];
                if(j == t) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}
int find(int pos, int limit) {
    if(pos == t) return limit;
    int flow = 0;
    for(int i = cur[pos]; ~i && flow < limit; i = ne[i]) {
        int j = e[i];
        cur[pos] = i;
        if(dep[j] == dep[pos] + 1 && f[i]) {
            int tmp = find(j, min(f[i], limit - flow));
            if(!tmp) dep[j] = -1;
            f[i] -= tmp; f[i ^ 1] += tmp; flow += tmp;
        }
    }
    return flow;
}
int dinic() {
    int ans = 0, flow;
    while(bfs())
        while(flow = find(s, INF))
            ans += flow;
    return ans;
}
void solve() {
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i ++) {
        cin >> u >> v;
        u ++; v ++;
        g[u][v] = g[v][u] = 1;
    }
    int ans = n;
    for(int i = 1; i <= n; i ++) {
        for(int j = i + 1; j <= n; j ++) {
            if(g[i][j]) continue;
            s = i + n, t = j;
            for(int k = 1; k <= n * 2; k ++) h[k] = -1; idx = 0;
            for(int k = 1; k <= n; k ++)
                for(int l = 1; l <= n; l ++) 
                    if(k == l) add(k, k + n, 1);
                    else if(g[k][l]) add(k + n, l, INF);
            ans = min(ans, dinic());
        }
    }
    cout << ans << endl;
}
signed main() {
    IOS; int t = 1;
    while(t --) solve();
}

C++ 解法, 执行用时: 24ms, 内存消耗: 1116K, 提交时间: 2022-07-13 20:54:27

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int mp[300][300],pre[300],flow[300][300],p[300],a[300];
int EK(int s,int t)
{
    int sum=0;
    int m=2*s+2;
    queue<int>q;
    memset(flow,0,sizeof(flow));
    for(;;)
    {
        memset(a,0,sizeof(a));
        a[s]=inf;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=0;i<m;i++)if(!a[i]&&mp[u][i]>flow[u][i])p[i]=u,q.push(i),a[i]=a[u]<mp[u][i]-flow[u][i]?a[u]:mp[u][i]-flow[u][i];
        }
        if(!a[t])break;
        for(int i=t; i!=s; i=p[i])flow[p[i]][i]+=a[t],flow[i][p[i]]-=a[t];
        sum+=a[t];
    }
    return sum;
}
int main(){
    int a,b;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(mp,0,sizeof(mp));
        memset(p,0,sizeof(p));
        for(int i=0;i<n;i++)mp[i][i+n]=1;
        while(m--){
            scanf("%d%d",&a,&b);
            mp[a+n][b]=inf;
            mp[b+n][a]=inf;
        }
        int ans=inf;
        for(int i=1;i<n;i++)ans=min(ans,EK(n,i));
        if(ans==inf)ans=n;
        printf("%d\n",ans);
    }
    return 0;
}