60分WA蒟蒻求助
查看原帖
60分WA蒟蒻求助
384233
shadow_ltq楼主2022/9/20 21:16
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define db double

const int N = 1e4 + 10, M = 1e5 + 10;
int n, m1, m2, s, t, kk, dis[N], now[N];
int idx = 1, h[N], w[M], to[M], ne[M];
ll ans;
bool has[N];

void add (int x, int y, int c)
{
	to[++idx] = y;
	ne[idx] = h[x];
	w[idx] = c;
	h[x] = idx;
	to[++idx] = x;
	ne[idx] = h[y];
	w[idx] = 0;
	h[y] = idx;
}

bool bfs ()
{
	memset (dis, 0, sizeof (dis));
	queue <int> q;
	q.push (s);
	dis[s] = 1;
	now[s] = h[s];
	while (q.size ())
	{
		int x = q.front ();
		q.pop ();
		for (int i = h[x]; i; i = ne[i])
		{
			if (w[i] && !dis[to[i]])
			{
				int y = to[i];
				q.push (y);
				now[y] = h[y];
				dis[y] = dis[x] + 1;
				if (y == t)
				{
					return true;
				}
			}
		}
	}
	return false;
}

int dinic (int x, int flow)
{
	if (x == t)
	{
		return flow;
	}
	int rest = flow, k;
	for (int i = now[x]; i && rest; i = ne[i])
	{
		now[x] = i;
		if (w[i] && dis[to[i]] == dis[x] + 1)
		{
			k = dinic (to[i], min (rest, w[i]));
			if (!k)
			{
				dis[to[i]] = 0;
			}
			w[i] -= k;
			w[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}

int main()
{
	scanf ("%d%d%d", &n, &m1, &m2);
	s = 1;
    t = 2 + n + m1 * 2 + m2 * 2;
    for (int i = 1; i <= m1; i++)
    {
        add (1 + i, 1 + m1 + i, 1);
        add (s, 1 + i, 1);
    }
    for (int i = 1; i <= m2; i++)
    {
        add (1 + m1 * 2 + n + i, 1 + m1 * 2 + n + m2 + i, 1);
        add (1 + m1 * 2 + n + m2 + i, t, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m1; j++)
        {
            int x;
            scanf ("%d", &x);
            add (1 + m1 + j, 1 + m1 * 2 + i, x);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m2; j++)
        {
            int x;
            scanf ("%d", &x);
            add (1 + m1 * 2 + i, 1 + m1 * 2 + n + j, x);
        }
    }
	int flow = 0;
	while (bfs ())
	{
		while (flow = dinic (s, INT_MAX))
		{
			ans += flow;
		}
	}
    printf ("%lld", ans);
	return 0;
}
2022/9/20 21:16
加载中...