洛谷P1345-奶牛的电信(最小割+拆点)

题目链接:洛谷P1345-奶牛的电信

题意:

n个奶牛互相交流,若a能与b,c交流,那么b与c也能交流,问最少宰多少头奶牛能让奶牛s与奶牛t不能交流。

题解:

最小割模型。

注意是割点,不是割边,割边只会涉及到一条边,割点则会涉及到与这个点相连的所有边。

具体做法:把每个点拆分为两个点,一个为入点,一个为出点,并连边即可。若割掉点A,等价于割掉边(A,A')。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int MAXM = 2e4;
const int inf = 0x3f3f3f3f;
int n, m, st, ed, s, t;
int depth[MAXN], cur[MAXN];
struct EDGE
{
    int v, w, nxt;
} edge[MAXM * 2];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
int dfs(int u, int flow)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w != 0)
        {
            int di = dfs(v, min(flow, w));
            if (di > 0)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs()
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (depth[v] == 0 && w > 0)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    if (depth[ed] > 0)
        return 1;
    else
        return 0;
}
int dinic()
{
    int tot = 0;
    while (bfs())
    {
        for (int i = 1; i <= n * 2; i++)
            cur[i] = fir[i];
        while (int temp = dfs(st, inf * 2))
            tot += temp;
    }
    return tot;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(fir, -1, sizeof(fir));
    cnt = 0;
    t += n;
    st = 1;
    ed = t;
    for (int i = 1; i <= n; i++)
        addedge(i, i + n, 1), addedge(i + n, i, 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v + n, inf);
        addedge(v + n, u, 0);
        addedge(v, u + n, inf);
        addedge(u + n, v, 0);
    }
    int flow = dinic();
    printf("%d\n", flow);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。