uva 10746 Crime Wave – The Sequel

최소 비용 최대 흐름
제목: n 개의 장소, m 개의 배 (m > = n) 가 있 으 며, 각 배가 각 장소 에 도착 하 는 시간 을 드 립 니 다.그리고 배 를 장소 로 보 내야 합 니 다.배 는 한 번 만 쓸 수 있 고 한 곳 만 갈 수 있 으 며, 한 곳 마다 배 한 척 만 필요 하 다.최소 평균 시간 을 산출 하 다.평균 시간 을 계산 하려 면 사실 총 시간 을 가장 적 게 계산 한 다음 에 n 으로 나 누 면 된다.그럼 총 시간 을 어떻게 최소 화하 지?
사실은 딱 봐 도 유형 에 맞 는 문제 이지 만 제 가 현재 배 운 일치 하 는 알고리즘 에 대해 이 문 제 를 풀 수 있 는 것 이 없습니다. 그 다음 에 백서 의 도 론 주제 에서 다른 유형의 문제 로 바 꿀 수 있 는 지 고려 해 보 겠 습 니 다.2 분 그림 의 최대 일치 문 제 를 최대 흐름 으로 바 꿀 수 있다 는 것 을 생각 하 자 곧 최소 비용 의 최대 흐름 으로 풀 생각 이 났 다.
배 는 1 부터 m 까지 표 시 됩 니 다. 장 소 는 m + 1 에서 m + n 까지 표 시 됩 니 다.방향 도 를 구축 하 는 것 은 모두 u 선 에서 v 장 소 를 가리 키 는 것 이 고 단위 비용 은 u 선 에서 v 장소 까지 의 시간 이 며 용량 은 1 이다. 그 다음 에 원점 0, 0 을 설립 하여 모든 배 를 가리 키 는데 모두 m 개의 변 이 고 용량 은 1 이다. 단위 비용 은 0 이다. 하나의 외환 점 m + n + 1 을 설립 하고 모든 지점 은 외환 점 을 가리 키 며 단위 비용 은 0 용량 이 1 이다. 구원 점 0 에서 외환 점 m + n + 1 의 최소 비용 은 최대 흐름 이다.알 수 있 듯 이 마지막 최대 유량 은 n 이 고 최소 비용 은 최소 의 총 시간 이 며 그 다음 에 n 으로 나 누 면 된다.
이렇게 설치 하면 모든 배 와 장소 가 한 번 만 사 용 될 수 있다.
그림 을 만 든 후, 직접 최소 비용 의 최대 스 트림 템 플 릿 을 올 리 면 된다.
방향 도 가 있 고 이 문 제 는 평행 변 이 없 기 때문에 행렬 을 인접 하면 되 고 인접 표를 사용 하지 않 아 도 된다.

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

using namespace std;

#define MAX 50

#define INF 1000000000.00000

#define eps 1e-8

int n,m,F;

double C;

double g[MAX][MAX],cost[MAX][MAX],d[MAX];

int cap[MAX][MAX],flow[MAX][MAX],p[MAX];



void init()

{

    memset(cap,0,sizeof(cap));

    memset(flow,0,sizeof(flow));

    memset(cost,0,sizeof(cost));



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

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

        {

            int u,v;

            u=j; v=m+i;

            cap[u][v]=1;

            scanf("%lf",&cost[u][v]);

            cost[v][u]=-cost[u][v];

        }

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

        cap[0][i]=1;

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

        cap[i][m+n+1]=1;

}



int relax(int u ,int v)

{

    if(d[v]>d[u]+cost[u][v]+eps)  //  

        return 1;

    else 

        return 0;

}

void spfa(int s ,int t)

{

    queue<int>q;

    int vis[MAX];

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

    { d[i]=INF; vis[i]=0; p[i]=-1; }

    d[s]=0; vis[s]=1;

    q.push(s);

    while(!q.empty())

    {

        int u;

        u=q.front(); vis[u]=0; q.pop();

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

            if(flow[u][v]<cap[u][v] && relax(u,v))  //     

            {

                d[v]=d[u]+cost[u][v];

                p[v]=u;

                if(!vis[v])

                {

                    vis[v]=1;

                    q.push(v);

                }

            }

    }

    return ;

}

void mincost_maxflow()

{

    int s=0,t=m+n+1;

    F=0; C=0;

    while(1)

    {

        spfa(s,t);

        if(d[t]==INF)

            break;

        int u,min=0x3f3f3f3f;

        for(u=t; u!=s; u=p[u])

            min=min < cap[p[u]][u]-flow[p[u]][u] ? min : cap[p[u]][u]-flow[p[u]][u];



        for(u=t; u!=s; u=p[u])  //  

        {

            flow[p[u]][u]+=min;

            flow[u][p[u]]-=min;

        }

        F+=min;

        C+=1.*min*d[t];

    }



    //printf("%.2lf
",C);

    //printf("%d
",F);

    printf("%.2f
",C/n+eps);  //   

    return ;

}



int main()

{

    while(scanf("%d%d",&n,&m))

    {

        if(!n && !m) break;

        init();

        mincost_maxflow();

    }

    return 0;

}