HDU 2853 (KM 최대 일치)

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=2853

제목 대의: 이분 도 일치 비용 흐름.① 최대 매 칭 ② 최소 원 배 변동
문제 풀이 방향:
두 번 째 요 구 를 빼 면 누 드 KM 다.
그러나 두 번 째 요 구 를 더 하면 새로운 건설 방식 이 필요 하 다.
건축 도
입력 행렬 에 대해 서 는 각 변 마다 cost 가 K 배 확대 ($K = n + 1 $)
원 배 에 대해 각 변 비용 은 K 배 확대 에 + 1
KM
cost 를 통계 할 때, 직접 cost 를 K 를 제거 한 후에 누적 합 니 다.
그리고 Hash 는 원 배 변 의 변동 상황 을 살 펴 보 겠 습 니 다.
K 배의 역할 을 확대 하 다
정확히 말 하면 K 배 는 + 1 을 위해 존재 한다.원래 의 배 치 를 우선적으로 고려 해 야 하기 때문에 비용 이 좀 많이 든다.
그러나 커 진 cost 는 마지막 으로 실제 cost 를 잘 집계 해 야 한다.그래서 K 배 를 늘 리 고 K 를 제거 하면 + 1 이 바로 버 려 집 니 다.
K = n + 1 은 n = 1 의 상황 이 걸 리 는 것 을 방지 하 는 자세 입 니 다.
코드

#include "iostream"

#include "cstdio"

#include "cstring"

#include "algorithm"

using namespace std;

#define maxn 55

int n,m,Hash[maxn],tmp,old,K;

int link[maxn],LX[maxn],RX[maxn],W[maxn][maxn],slack[maxn],e[maxn][maxn];

bool S[maxn],T[maxn];

const int inf=0x3f3f3f3f;

bool dfs(int u)

{

    S[u]=true;

    for(int v=1;v<=m;v++)

    {

        if(T[v]) continue;

        int t=LX[u]+RX[v]-W[u][v];

        if(!t)

        {

            T[v]=true;

            if(!link[v]||dfs(link[v]))

            {

                link[v]=u;

                return true;

            }

        }

        else if(t<slack[v]) slack[v]=t;

    }

    return false;

}

void update()

{

    int a=inf;

    for(int i=1;i<=m;i++) //ny

       if(!T[i]&&slack[i]<a) a=slack[i];

    for(int i=1;i<=n;i++)  //nx

        if(S[i]) LX[i]-=a;

    for(int i=1;i<=m;i++) //ny

    {

        if(T[i]) RX[i]+=a;

        else slack[i]-=a;

    }

}

void KM()

{

    memset(link,0,sizeof(link));

    memset(RX,0,sizeof(RX));

    for(int i=1;i<=n;i++) //nx

        for(int j=1;j<=m;j++) //ny

            LX[i]=max(LX[i],W[i][j]);

    for(int i=1;i<=n;i++) //nx

    {

        for(int j=1;j<=m;j++) //ny

            slack[j]=inf;

        while(1)

        {

            memset(S,0,sizeof(S));

            memset(T,0,sizeof(T));

            if(dfs(i)) break;

            else update();

        }

    }

    int res=0,change=0;

    for(int i=1;i<=m;i++) //ny

    {

       if(link[i])

       {

           res+=(W[link[i]][i]/K);

           if(Hash[i]!=link[i]) change++;

       }

    }

    printf("%d %d
",change,res-old);

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d%d",&n,&m)!=EOF)

    {

       memset(W,0,sizeof(W));

       memset(Hash,0,sizeof(Hash));

       old=0;K=n+1;

       for(int i=1;i<=n;i++)

          for(int j=1;j<=m;j++)

        {

            scanf("%d",&W[i][j]);

            W[i][j]*=K;

        }

       for(int i=1;i<=n;i++)

       {

           scanf("%d",&tmp);

           old+=(W[i][tmp]/K);

           Hash[tmp]=i;

           W[i][tmp]++;

       }

       KM();

       memset(slack,0,sizeof(slack));

       memset(LX,0,sizeof(LX));

    }

    return 0;

}