SPOJ #300 题解

admin 2021-05-24 PM 125℃ 0条

题目链接

分析

首先,看到“最少删掉”就容易想到最小割。

但是这里是删掉点,所以考虑如何转成删掉边。拆点。

把点 $x$ 拆成入点 $x'$ 和出点 $x$。$x'$ 向 $x$ 连一条容量为 1 的边。删掉点 $x$ 等价于割掉这条边。

对于原图中一条 $(u,v)$ 的边,由于是无向图,从 $u$ 向 $v'$,从 $v$ 向 $u'$ 各连一条容量为 $\inf$ 的边,表示不能被割掉。

考虑源点和汇点。枚举源点 $s=1,2,\ldots n$,汇点 $t=1',2',\ldots n'$,取最大流的最小值即可。注意 $s'$ 和 $t$ 不能相等。

时间复杂度 $O(TN^4M)$,显然跑不满,实际上跑的飞快。

提一嘴,双倍经验,只需要改输入即可。

解决

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 105, M = 10005;
int n, m, T, head[N], ver[M], nxt[M], edge[M], tot, que[N], l, r, s, t, level[N], ans;

void init()
{
    tot = 1;
    memset(head, 0, sizeof(head));
}

bool bfs()
{
    memset(level, 0, sizeof(level));
    l = r = 1, que[l] = s, level[s] = 1;
    while (l <= r)
    {
        int cur = que[l++];
        for (int i = head[cur]; i; i = nxt[i])
            if (edge[i] && !level[ver[i]])
            {
                level[ver[i]] = level[cur] + 1, que[++r] = ver[i];
                if (ver[i] == t)
                    return true;
            }
    }
    return false;
}

int dinic(int cur, int increase)
{
    if (cur == t)
        return increase;
    int rest = increase;
    for (int i = head[cur]; i; i = nxt[i])
        if (edge[i] && level[ver[i]] == level[cur] + 1)
        {
            int inc = dinic(ver[i], min(rest, edge[i]));
            if (inc == 0)
            {
                level[ver[i]] = 0;
                continue;
            }
            rest -= inc, edge[i] -= inc, edge[i ^ 1] += inc;
        }
    return increase - rest;
}

int Dinic()
{
    int maxflow = 0, tmp;
    while (bfs())
        do
        {
            tmp = dinic(s, 0x3f3f3f3f);
            maxflow += tmp;
            if (maxflow >= ans)
                return n;
        } while (tmp);
    return maxflow;
}

void restore()
{
    for (int i = 1; i <= n + n; i++)
        for (int j = head[i]; j; j = nxt[j])
            if (!(j & 1))
                edge[j] += edge[j ^ 1], edge[j ^ 1] = 0;
}

void addedge(int u, int v, int w)
{
    ver[++tot] = v, nxt[tot] = head[u], head[u] = tot, edge[tot] = w;
    ver[++tot] = u, nxt[tot] = head[v], head[v] = tot, edge[tot] = 0;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        init();
        while (m--)
        {
            int x, y;
            scanf(" (%d,%d)", &x, &y);
            x++, y++;
            addedge(x, y + n, 0x3f3f3f3f), addedge(y, x + n, 0x3f3f3f3f);
        }
        for (int i = 1; i <= n; i++)
            addedge(i + n, i, 1);
        ans = n;
        for (s = 1; s <= n; s++)
            for (t = n + 1; t < n + s; t++)
            {
                restore();
                ans = min(ans, Dinic());
            }
        cout << ans << endl;
    }
    return 0;
}
标签: 图论, 网络最大流

非特殊说明,本博所有文章均为博主原创。

评论啦~