最小费用最大流 HDU1533

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1533

#include<bits/stdc++.h>

#define fi first

#define se second

#define INF 0x3f3f3f3f

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define pqueue priority_queue

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

const double pi=4.0*atan(1.0);

const double e=exp(1.0);

const int maxn=1e6+;

typedef long long LL;

typedef unsigned long long ULL;

const LL mod=1e9+;

const ULL base=1e7+;

using namespace std;

struct edge{

    int to,nxt,flow,cost;

}g[maxn];

int head[],pre[],dis[],cnt,s,t,tot;

int a[][];

bool vis[];

char ss[];

void add(int x,int y,int cost,int flow){

    g[cnt].to=y;

    g[cnt].nxt=head[x];

    g[cnt].cost=cost;

    g[cnt].flow=flow;

    head[x]=cnt++;

}

bool spfa(){

    memset(pre,-,sizeof(pre));

    memset(dis,INF,sizeof(dis));

    memset(vis,,sizeof(vis));

    queue<int> que;

    while(!que.empty()){que.pop();}

    que.push(s);

    dis[s]=;

    vis[s]=;

    while(!que.empty()){

        int k=que.front();

        que.pop();

        vis[k]=;

        int tt=head[k];

        while(tt!=-){

            if(dis[g[tt].to]>dis[k]+g[tt].cost&&g[tt].flow>){

                pre[g[tt].to]=tt;

                dis[g[tt].to]=dis[k]+g[tt].cost;

                if(vis[g[tt].to]==){

                    que.push(g[tt].to);

                    vis[g[tt].to]=;

                }

            }

            tt=g[tt].nxt;

        }

    }

    return pre[t]!=-;

}

int maxflow(){

    int ans=;

    while(spfa()){

        int f=INF;

        for(int i=pre[t];i!=-;i=pre[g[i^].to]){

            if(g[i].flow<f)

                f=g[i].flow;

        }

        for(int i=pre[t];i!=-;i=pre[g[i^].to]){

            g[i].flow-=f;

            g[i^].flow+=f;

            ans+=g[i].cost*f;

        }

    }

    return ans;

}

int main(){

    int n,m;

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

        memset(head,-,sizeof(head));

        cnt=tot=;

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

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

                a[i][j]=tot++;

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

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

                if(j!=m){

                    add(a[i][j],a[i][j+],,INF);

                    add(a[i][j+],a[i][j],-,);

                    add(a[i][j+],a[i][j],,INF);

                    add(a[i][j],a[i][j+],-,);

                }

                if(i!=n){

                    add(a[i][j],a[i+][j],,INF);

                    add(a[i+][j],a[i][j],-,);

                    add(a[i+][j],a[i][j],,INF);

                    add(a[i][j],a[i+][j],-,);

                }

            }

        }

        s=tot++;

        t=tot++;

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

            scanf("%s",ss);

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

                if(ss[j]=='H'){

                    add(a[i][j+],t,,);

                    add(t,a[i][j+],,);

                }

                if(ss[j]=='m'){

                    add(s,a[i][j+],,);

                    add(a[i][j+],s,,);

                }

            }

        }

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

    }

}