POJ 2112 2 점 + dinic

제목: N, C, M, N 은 착유기 의 수량 이 고 C 는 젖소 의 수량 이 며 M 은 각 착유기 마다 최대 몇 마리 의 젖소 에 게 사용 하 는 지 알려 준다.
(N + C) * (N + C) 의 행렬 을 보 여 줍 니 다. 착유기 와 젖소 사이 의 거 리 를 대표 합 니 다. 0 은 도착 할 수 없습니다. 이 구 덩이 는 저 에 게 오랫동안 있 었 습 니 다.
― 최대 흐름 을 만족 시 키 는 상황 에서 어떤 젖소 가 가장 긴 거 리 를 가장 짧게 가 는 방법.
사고방식: 먼저 뛰 면서 플 로 이 드, dis [] = 0, 도착 할 수 없 기 때문에 특 판 이 필요 합 니 다. 여기 WA 는 56 번 입 니 다.
2 분 변 의 길 이 는 매번 그림 을 한 번 만 들 면 이 변 의 길이 보다 작은 것 을 만족 시 키 고 dinic 을 한 번 달 려 서 최대 흐름 이 젖소 의 수량 과 같 는 지 확인 합 니 다.
S - 착유기, 가중치 M, 역방향 0.
착유기 - 젖소, 가중치 1, 역방향 0.
젖소 - T, 가중치 1, 역방향 0.
구체 적 으로 코드 참조.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define Max 250
#define mem(a,b) memset(a,b,sizeof(a))
int N,M,C;
int Map[Max][Max] ;
#define inf 1 << 30
#include <cstring>
#include <string>

struct kdq
{
    int s , e , l ,next ;
} ed[Max * 100] ;
int head[Max] ,num ;
int S,T ;
void add(int s ,int e ,int l )
{
    ed[num].s = s ;
    ed[num].e = e ;
    ed[num].l = l ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;

    ed[num].s = e ;
    ed[num].e = s ;
    ed[num].l = 0 ;
    ed[num].next = head[e] ;
    head[e] = num ++ ;
}

void init()
{
    mem(head,-1) ;
    num = 0 ;
}

int deep[Max] ;
int qe[Max * 100] ;
int dinic_bfs()
{
    mem(deep,-1) ;
    deep[S] = 0 ;
    int h = 0 ,t = 0 ;
    qe[h ++ ] = S ;
    while(h > t)
    {
        int tt = qe[t ++ ] ;
        for (int i = head[tt] ; ~i ; i = ed[i].next )
        {
            int e = ed[i].e ;
            int l = ed[i].l ;
            if(deep[e] == -1 && l > 0 )
            {
                deep[e] = deep[tt] + 1 ;
                qe[h ++ ] = e ;
            }
        }
    }
    return deep[T] != -1 ;
}

int dinic_dfs(int now ,int f )
{
    if(now == T)return f ;
    int flow = 0 ;
    for (int i = head[now] ; ~i ; i = ed[i].next )
    {
        int e = ed[i].e ;
        int l = ed[i].l ;
        if(deep[e] == deep[now] + 1 && l > 0)
        {
            int mm = min(l,f - flow) ;
            int nn = dinic_dfs(e , mm) ;
            flow += nn ;
            ed[i].l -= nn ;
            ed[i ^ 1].l += nn ;
        }
    }
    if(!flow )deep[now] = -2 ;
    return flow ;
}
int dinic()
{
    int flow = 0 ;
    while(dinic_bfs())
    {
        flow += dinic_dfs(S,inf) ;
    }
    return flow ;
}

void floyd()
{
    for (int k = 1 ; k <= N + C ; k ++ )
    {
        for (int i = 1 ; i <= N + C ; i ++ )
        {
            if(Map[i][k] == inf)continue ;//    
            for (int j = 1 ; j <= N + C ; j ++)
            {
                if(Map[j][k] == inf) continue ;//    
                if(Map[i][k] + Map[k][j] < Map[i][j])Map[i][j] = Map[i][k] + Map[k][j] ;
            }
        }
    }
}
void build_Map(int mid)
{
    S = 0 ,T = N + C + 1 ;
    init() ;
    for (int i = 1 ; i <= N ; i ++)
    {
        for (int j = N + 1 ; j <= N + C ; j ++)
        {
            if(Map[i][j] <= mid)
            {
                add(i,j,1) ;
            }
        }
    }
    for (int i = N + 1 ; i <= N + C ; i ++)add(i,T,1) ;
    for (int i = 1 ; i <= N ; i ++ )add(S,i,M) ;
}
int main()
{
    while(scanf("%d%d%d",&N,&C,&M) != EOF)
    {
        for (int i = 1 ; i <= N + C ; i ++ )
            for (int j = 1 ; j <= N + C ; j ++ )
            {
                scanf("%d",&Map[i][j]) ;
                if(!Map[i][j])Map[i][j] = inf ;
            }
        floyd() ;
        int l = 0 ,r = 100000 ;
        int mid = l + r >> 1 ;
        while(r > l)
        {
            mid = (l + r ) / 2 ;
            build_Map(mid) ;
            int ans = dinic() ;
            if(ans < C) l = mid + 1 ;
            else r = mid ;
        }
        cout << r <<endl;
    }
    return 0;
}