HDU2282 Chocolate KM算法

第一次做这样的题，其中有几个细节是反复思考反复调试，最后一A的，ORZ，又加深了对KM算法的理解。能不参考网上的题解
，而是平静下来思考，参透，最后敢于尝试.....
真的很重要，以后遇到才会有更深的印象和灵感！

（或与还可以用贪心的方式或者数学姿势来解决，想了一下，头疼，QwQ）

主要是注意几个细节：

1：拆点方式。大于一个ccl（巧克力）的要一个一个的拆点，而不是拆成一坨，毕竟要没到不同的盒子里。

2：循环对象。毕竟是cnt1！=cnt2 ，即男女不是1：1，有的人匹配不到，所以最后有空盒子。匹配的时候以多的ccl为对象，而累加的时候以盒子为对象。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<memory.h>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=;

const int inf=0x7ffffff;

int map[maxn][maxn];

int vis1[maxn],vis2[maxn];

int ex1[maxn],ex2[maxn];

int lack[maxn];

int link[maxn];

int ans,n;

int x[maxn],p[maxn],y[maxn],cnt1,cnt2;

int Abs(int v){

    if(v<) v=-v;

    return v;

}

bool _bfs(int v)

{

    vis1[v]=true;

    for(int i=;i<=cnt2;i++){

        if(!vis2[i]){

            int tmp=ex1[v]+ex2[i]-map[v][i];

            if(tmp==){

              vis2[i]=true;

              if(!link[i]||_bfs(link[i])){

                 link[i]=v;

                 return true;

              }

            }

            else if(tmp<lack[i]) lack[i]=tmp;

        }

    }

    return false;

}

void _KM()

{

    int t,i,j;

    memset(link,,sizeof(link));

    memset(ex2,,sizeof(ex2));

    for(i=;i<=cnt1;i++){

        ex1[i]=map[i][];

        for(j=;j<=cnt2;j++)

         if(ex1[i]<map[i][j]) ex1[i]=map[i][j];

    }

    for(t=;t<=cnt1;t++){

        for(i=;i<=cnt2;i++) lack[i]=inf;

        while(true){

            memset(vis1,,sizeof(vis1));

            memset(vis2,,sizeof(vis2));

            if(_bfs(t))  break;

            int gap=inf;

            for(i=;i<=cnt2;i++)

             if(!vis2[i]&&lack[i]<gap) gap=lack[i];

            for(i=;i<=cnt1;i++) if(vis1[i]) ex1[i]-=gap;

            for(i=;i<=cnt2;i++) if(vis2[i]) ex2[i]+=gap;

            for(i=;i<=cnt2;i++) if(!vis2[i])lack[i]-=gap;

        }

    }

    ans=;

    for(i=;i<=cnt2;i++)//而不是cnt1，因为前cnt1个不一定就对应1-cnt1，有可能其对象在cnt+1——cnt2中

         ans-=map[link[i]][i];

    printf("%d\n",ans);

}

int main()

{

    int i,j,m;

    char c;

    while(~scanf("%d",&n)){

        memset(map,,sizeof(map));

        cnt1=cnt2=;

        for(i=;i<=n;i++) scanf("%d",&p[i]);

        for(i=;i<=n;i++){

           while(p[i]>) {//拆点

             x[++cnt1]=i;

             p[i]--;

           }

           if(p[i]==) y[++cnt2]=i;

        }

        for(i=;i<=cnt1;i++)

         for(j=;j<=cnt2;j++)

          map[i][j]=-min(Abs(x[i]-y[j]),n-Abs(x[i]-y[j]));//最近

        _KM();

    }

    return ;

}