다 이 닝 (네트워크 스 트림 포인트 + Dinic)

젖소 N 마리 와 F 종, D 종 음 료 를 주 고, 소 한 마리 한 마리 가 좋아 하 는 음료 와 음식 을 가 지 며, 소 한 마리 가 좋아 하 는 음료 와 음식 을 하나씩 얻 으 면 기뻐 하 는 소 는 한 가지 음료 나 한 가지 음식 을 소 한 마리 만 얻 을 수 있 으 며, 최대 몇 마리 의 소 를 기 쁘 게 할 수 있 는 지 물 었 다.
이 문 제 는 좀 풀 면 말 하지 않 겠 습 니 다. 저도 생각 이 안 나 지만 Dinic 알고리즘 은 여름 방학 때 보다 훨씬 뚜렷 해 졌 습 니 다.
Dinic 은 먼저 원래 의 네트워크 에 대해 원점 에서 외환 점 BFS 까지 층 을 나 누 었 다. 외환 점 의 층 을 나 눌 수 있다 면 반드시 유량 이 원점 에서 외환 점 으로 흘러 갈 수 있다 는 것 을 의미한다. 그 다음 에 원점 에서 DFS 를 하고 한 개 (또는 여러 개) 를 찾 아 외환 점 에서 가장 작은 유량 (대략 이런 뜻) 을 증가 시 키 고 최대 흐름 에 이 답 을 더 했다.이번에 DFS 가 추 가 된 번복 은 다음 BFS 이후 에 사용 하기 위 한 것 이다.매번 BFS 가 DFS 에 대해 한 번 에 증 광 로 를 찾 고 BFS 가 외환 점 이 있 는 층 수 를 구분 하지 못 한 다 는 것 을 알 면 증 광 로 가 존재 하지 않 는 다 는 것 을 알 수 있 고 알고리즘 이 끝 났 습 니 다.시간 복잡 도 O (V ^ 2, E).

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
int N, F, D, k, dep[maxn], head[maxn];
int food[maxn], drink[maxn];
int S, T;
struct Edge
{
    int before;
    int flow;
    int to;
} e[maxn << 1];
inline void add(int u, int v, int c)
{
    e[k].to = v;
    e[k].flow = c;
    e[k].before = head[u];
    head[u] = k++;
}
int BFS(int S, int T)
{
    queue q;
    memset(dep, -1, sizeof(dep));
    dep[S] = 0;
    q.push(S);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (u == T)
            return true;
        for (int i = head[u]; i != -1; i = e[i].before)
        {
            int v = e[i].to;
            if (e[i].flow && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    if (dep[T] == -1)
        return false; //         
    return true;
}
int DFS(int u, int flow)
{
    if (u == T)
        return flow; //          
    int sum = 0;
    for (int i = head[u]; i != -1; i = e[i].before)
    {
        int v = e[i].to;
        if (e[i].flow && dep[v] == dep[u] + 1)
        {
            int f = DFS(v, min(flow - sum, e[i].flow)); //                     
            e[i].flow -= f;                             // flow-sum              
            e[i ^ 1].flow += f;
            sum += f;
            if (sum == flow) //       
                return sum;
        }
    }
    return sum;
}
int Dinic(int S, int T)
{
    int max_flow = 0;
    while (BFS(S, T))
    {
        max_flow += DFS(S, inf);
    }
    return max_flow;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
#endif
    memset(head, -1, sizeof head);
    scanf("%d %d %d", &N, &F, &D);
    int f, d;
    S = 0;                 //     
    T = 2 * N + F + D + 1; //     
                           //	                2n+1~2n+F
                           //	          1 ~ n
                           //	          n+1 ~ 2n
                           //	    		      2n+F+1 ~ 2n+F+D
    for (int i = 1; i <= F; i++)
    {
        add(S, 2 * N + i, 1); //        
        add(2 * N + i, S, 0); //    
    }
    for (int i = 1; i <= D; i++)
    {
        add(2 * N + F + i, T, 1); //        
        add(T, 2 * N + F + i, 0); //    
    }
    for (int i = 1; i <= N; i++)
    {
        add(i, i + N, 1); //          
        add(i + N, i, 0); //    
    }
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d", &f, &d);
        for (int j = 1; j <= f; j++)
        {
            scanf("%d", &food[j]);
            add(2 * N + food[j], i, 1);
            add(i, 2 * N + food[j], 0);
        }
        for (int j = 1; j <= d; j++)
        {
            scanf("%d", &drink[j]);
            add(N + i, 2 * N + F + drink[j], 1);
            add(2 * N + F + drink[j], N + i, 0);
        }
    }
    printf("%d", Dinic(S, T));
    return 0;
}