【 확장 km 】 hdu 4744

앞서 hdu 4744 의 정 해 는 비용 흐름 이 아니 라 순 폭력 적 이 고 그림 에 대한 성격 이 없 는 비용 흐름 이 아니 라...
우 리 는 km 가 가장 좋 은 매 칭 을 할 때 매번 같은 서브 맵 에서 가장 큰 매 칭 을 하 는 것 을 알 고 있 습 니 다. 만약 에 같은 서브 맵 을 찾 지 못 하면 정상 표 지 를 수정 하여 같은 서브 맵 을 확대 하 는 것 을 알 수 있 습 니 다. 그러면 이 문 제 는 사실은 여러 번 확대 되 는 km 임 을 알 수 있 습 니 다. 즉, 같은 서브 맵 을 찾 을 때마다 유량 을 한 번 확대 하 는 동시에 한 변 으로 여러 번 선택 할 수 있 기 때 문 입 니 다.그러면 똑 같은 서브 맵 도 여러 개 있 기 때문에 알고리즘 을 수정 하고 나 왔 습 니 다. 똑 같은 서브 맵 을 찾 을 때마다 하 나 를 찾 으 면 넓 어 지고 넓 어 질 수 있 는 똑 같은 서브 맵 을 찾 지 못 할 때 정상 표 지 를 수정 합 니 다.
93ms 를 뛰 었 으 니 지금 이 가장 빠 를 것 입 니 다. G + + 로 교차 하 는 것 이 느 릴 것 입 니 다. 그래서 사실은 유 대사 보다 느 립 니 다.

#include <cstdio>
#include <cstdlib>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
const int oo=1073741819;
using namespace std;
int n;
int vx[200],vy[200],lx[200],ly[200],slack[200],f[200],g[200];
int x[200],y[200],z[200],a[200],b[200],c[200][200],w[200][200];
double dist(int i,int j)
{
    return sqrt((double)(sqr(x[i]-x[j])+sqr(y[i]-y[j])+sqr(z[i]-z[j])));
}
bool km(int x)
{
    if (vx[x]) return 0;
    vx[x]=1;
    for (int i=1;i<=n;i++) {
        if (vy[i]) continue;
        int tmp=lx[x]+ly[i]-w[x][i];
        if (!tmp) {
            vy[i]=1;
            if (b[i]) {
                f[x]=i,g[x]=0;
                return 1;
            }
            for (int j=1;j<=n;j++)
                if (c[j][i] && km(j)) {
                    f[x]=i,g[x]=j;
                    return 1;
                }
        }
        else slack[i]=min(slack[i],tmp);
    }
    return 0;
}
int push(int x)
{
    int d=a[x];
    for (int i=x;i;i=g[i]) {
        if (g[i]) d=min(d,c[g[i]][f[i]]);
        else d=min(d,b[f[i]]);
    }
    int sum=0;
    a[x]-=d;
    for (int i=x;i;i=g[i]) {
        if (g[i]) sum-=d*w[g[i]][f[i]],c[g[i]][f[i]]-=d;
        else b[f[i]]-=d;
        sum+=d*w[i][f[i]],c[i][f[i]]+=d;
    }
    return sum;
}
int main()
{
    freopen("hdu4744.in","r",stdin);
    freopen("hdu4744.out","w",stdout);
    for (;;) {
        scanf("%d",&n);
        if (!n) break;
        for (int i=1;i<=n;i++) {
            scanf("%d%d%d%d",&x[i],&y[i],&z[i],&a[i]);
            b[i]=a[i];
            lx[i]=0,ly[i]=0;
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++) {
                if (i!=j) w[i][j]=-floor(dist(i,j));
                else w[i][j]=-oo;
                c[i][j]=0;
                lx[i]=max(lx[i],w[i][j]);
            }
        int ans=0;
        for (int i=1;i<=n;i++) { 
            for (;a[i];) {
                for (int j=1;j<=n;j++) slack[j]=oo;
                for (;a[i];) {
                    for (int j=1;j<=n;j++) vx[j]=vy[j]=0;
                    if (km(i)) 
                        ans+=push(i);
                    else break;
                }
                if (!a[i]) break;
                int d=oo;
                for (int i=1;i<=n;i++)
                    if (!vy[i]) d=min(d,slack[i]);
                for (int i=1;i<=n;i++) {
                    if (vx[i]) lx[i]-=d;
                    if (vy[i]) ly[i]+=d;
                }
            }
        }
        for (int i=1;i<=n;i++)
            if (c[i][i]) ans=1;
        printf("%d
",-ans);
    }
    return 0;
}