Minimum Cost POJ - 2516 （模板题 spfa最小费用最大流）

题意：

人回家，一步一块钱，有x个人，y个房子，求能回家的最大人数且使之费用最小

解析：

就是。。。。套模板，，，，

建图(⊙﹏⊙)。。。要仔细观察呐

对于人拆不拆都可以  都能过，，，，这里贴上拆开的代码。。。。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

typedef long long LL;

int head[maxn], d[maxn], cur[maxn], vis[maxn], p[maxn], f[maxn];

int n, m, s, t;

int cnt, flow, value;

struct edge{

    int x, y;

};

struct node{

    int u, v, c, w, next;

}Node[maxn*];

void add_(int u, int v, int c, int w)

{

    Node[cnt].u = u;

    Node[cnt].v = v;

    Node[cnt].c = c;

    Node[cnt].w = w;

    Node[cnt].next = head[u];

    head[u] = cnt++;

}

void add(int u, int v, int c, int w)

{

    add_(u, v, c, w);

    add_(v, u, , -w);

}

int spfa()

{

    queue<int> Q;

    for(int i=; i<maxn; i++) d[i] = INF;

    d[s] = ;

    mem(vis, );

    mem(p, -);

    Q.push(s);

    vis[s] = ;

    p[s] = ; f[s] = INF;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        vis[u] = ;

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] > d[e.u] + e.w && e.c > )

            {

                d[e.v] = d[e.u] + e.w;

                p[e.v] = i;

                f[e.v] = min(f[u], e.c);

                if(!vis[e.v])

                {

                    Q.push(e.v);

                    vis[e.v] = ;

                }

            }

        }

    }

    if(p[t] == -) return ;

    flow += f[t], value += d[t];

    for(int i=t; i!=s; i=Node[p[i]].u)

    {

        Node[p[i]].c -= f[t];

        Node[p[i]^].c += f[t];

    }

    return ;

}

void max_flow()

{

    while(spfa());

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

}

int main()

{

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

    {

        s = ; t = *n*m+;

        edge hou[maxn], men[maxn];

        flow = ; value = ;

        cnt = ;

        mem(head, -);

        char str[][];

        int cnt1 = , cnt2 = ;

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

        {

            scanf("%s",str[i]);

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

            {

                if(str[i][j] == 'H')

                {

                    hou[cnt1].x = i;

                    hou[cnt1].y = j;

                    add(cnt1, t, , );

                    cnt1++;

                }

                if(str[i][j] == 'm')

                {

                    men[cnt2].x = i;

                    men[cnt2].y = j;

                    add(n*m+cnt2, *n*m + cnt2, , );

                    add(s, n*m+cnt2, , );

                    cnt2++;

                }

            }

        }

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

            for(int j=; j<cnt1; j++)

            {

                add(*n*m+i, j, , abs(men[i].x - hou[j].x) + abs(men[i].y - hou[j].y));

            }

            max_flow();

    }

    return ;

}