UVA1660 题解

yyrwlj · 2024-02-15 19:53:22 · 题解

思路

将每个点拆成入点和出点，入点向出点连一条边权为 1 的边，删除这条边就相当于删除这个点。

其它边就让这个点的出点连向其它点的入点即可，容量为 +\infty。

然后枚举源汇点，答案就是所有情况的最小割流量的最小值。

源点需要是出点，汇点需要是入点，不然直接切断入点连向出点的边就行了，最小割的流量肯定是 1。

Code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 105, M = 5205, inf = 1e8;
struct Edge{
    int e, to, nxt;
}g[M];
int h[N], idx;
int dep[N], now[N], q[N];
int n, m, S, T;
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
    g[++idx] = {0, a, h[b]}, h[b] = idx;
}
bool bfs()
{
    memset(dep, 0, sizeof dep);
    dep[S] = 1;
    int hh = 0, tt = 0;
    q[0] = S;
    now[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; i; i = g[i].nxt)
        {
            int j = g[i].to;
            if (dep[j] || !g[i].e)
                continue;
            dep[j] = dep[t] + 1;
            now[j] = h[j];
            if (j == T)
                return true;
            q[++ tt] = j;
        }
    }
    return false;
}
int find(int u,int lim)
{
    if (u == T)
        return lim;
    int flow = 0;
    for (int i = now[u]; i && flow < lim; i = g[i].nxt)
    {
        now[u] = i;
        int j = g[i].to;
        if (dep[j] != dep[u] + 1 || !g[i].e)
            continue;
        int v = find(j, min(g[i].e, lim - flow));
        if (!v)
            dep[j] = 0;
        else
        {
            g[i].e -= v;
            g[i ^ 1].e += v;
            flow += v;
        }
    }
    return flow;
}
int dinic()
{
    int res = 0, flow;
    while (bfs())
        while (flow = find(S, inf))
            res += flow;
    return res;
}
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i=0;i<n;i++)
            h[i] = h[i + n] = 0;
        idx = 1;
        for (int i=0;i<n;i++)
            add(i, i + n, 1);
        while (m--)
        {
            int a, b;
            scanf(" (%d,%d)", &a, &b);
            add(a + n, b, inf);
            add(b + n, a, inf);
        }
        int ans = n;
        for (int i=1;i<n;i++)
            for (int j=0;j<i;j++)
            {
                S = n + i, T = j;
                for (int k=2;k<=idx;k+=2)
                {
                    g[k].e += g[k ^ 1].e;
                    g[k ^ 1].e = 0;
                }
                ans = min(ans, dinic());
            }
        printf("%d\n", ans);
    }
    return 0;
}