City Tour

Description

艾丽丝想要从城市A出发到城池B,由于Alice近期相比较穷(不像集中磨炼队陈兴先生是个rich
second),所以只好选拔做列车从A到B。可是Alice很讨厌坐高铁,轻轨上人可比多,相比拥挤,所以艾丽丝有很严谨的须要:高铁的邻座两站间的最大距离尽恐怕的短,这样阿丽丝就足以在停站的时候下车休息一下。当然阿丽丝希望任何旅途相比较短。


Input

有多组测试数据。

每组测试数据的率先行有七个整数N,M,A,B(N<=两千, M<=陆仟0, N
>=2, A,B<=N),个中N是都市的个数,M是城市间通火车的个数。

A,B是Iris初阶的城池与目标地城市,城市的标注从1发端。

接下去的M行每行多个整数u,v,w表示从u到v和从v到u有一条铁路,距离为w,
u,v<=N, w<=10000。

title: 网络流
date: 2018-07-31 22:01:22
tags:

Output

对此每组测试数据输出满意Iris必要的从A到B的最短距离。

  • acm
  • 算法
  • 网络流

Sample Input

3 3 1 2

1 2 80

1 3 40

2 3 50

3 3 1 2

1 2 90

1 3 10

2 3 20

4 5 1 4

1 2 8

1 4 9

1 3 10

2 4 7

3 4 8

葡京手机登陆网址 1葡京手机登陆网址 2

#include<stdio.h>
#include<string.h>
#define maxn 2020
#define maxm 50500
#define inf 100000000

struct edge
{
    int u,v;
    int val,next;
} e[2*maxm],seq[maxm];

int last[maxn];
int que[maxm],dis[maxn];
bool vis[maxn];
int t,n,m,A,B;

void add(int u,int v,int val)//离散化存储
{
    e[t].v = v;
    e[t].val = val;
    e[t].next = last[u];
    last[u] = t++;
    return ;
}
void build(int val)//建树
{
    memset(last,-1,sizeof(last));
    t = 0;
    for (int i=1; i<=m; i++)
        if (seq[i].val <= val)
        {
            add(seq[i].u,seq[i].v,seq[i].val);
            add(seq[i].v,seq[i].u,seq[i].val);
        }
    return ;
}

int spfa()
{//采用负权存储
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; i++) dis[i] = inf;
    int head = 0, tail = 0;
    que[++tail] = A;
    vis[A] = 1;
    dis[A] = 0;
    while (head < tail)
    {
        int u = que[++head];
        for (int j=last[u]; j!=-1; j=e[j].next)//遍历与j相连的边
        {
            int v = e[j].v;
            int val = e[j].val;
            if (dis[u] + val < dis[v]) //松弛条件判断
            {
                dis[v] = dis[u] + val;
                if (vis[v]==0)
                {
                    vis[v] = 1;
                    que[++tail] = v;
                }
            }
        }
        vis[u] = 0;
    }
    if (dis[B] < inf) return dis[B];
    return -1;
}
int solve()
{
    int res = -1;
    int l = 1, r = 10000;
    while (l <= r)//二分最大边
    {
        int mid = (l + r)/2;
        build(mid);
        int tmp = spfa();
        if (tmp == -1) l = mid + 1;
        else
        {//当mid(即每段中的最大值)减少时,res进行更新
            res = tmp;
            r = mid - 1;
        }
    }
    return res;
}
int main()
{
    while (scanf("%d%d%d%d",&n,&m,&A,&B)==4)
    {
        for (int i=1; i<=m; i++) scanf("%d%d%d",&seq[i].u,&seq[i].v,&seq[i].val);
        int ans = solve();
        printf("%d\n",ans);
    }
    return 0;
}

图论(二分+SPFA)

 

概述

那篇博客主借使有关互联网流的一部分着力的知识点以及相应的模版,,

算了,,,依然先贴大佬的博客,,,暑假在补一下。。。。QAQ

Sample Output

90 30 15

网络流

tan90,,,,,,,

习题

Problem A: 养猪

Time Limit: 1 Sec Memory Limit: 128 MB

Description

埃弗里Boy喜欢玩LOL,不过她技术太菜,总是被外人喷“这么菜玩什么游戏,回家养猪去吧”。终于有一天,他被喷的不堪了,于是回家养猪。但是他家的养猪场在雨天的时候总是被淹,所以他用读书学来的学识设计了一套排水系统。他还设计了一套装置,能够决定排管的流水流量。以后有n个排管,m个排水节点,问您从1到m的最大排水流量。

Input

有多组测试数据,对于每组测试数据,第③行是八个整数n,m(0 <= n
<= 200,2 <= m <=
200),分别代表排管数和排水节点数。之后n行每行包罗一个整数,u,v,w(1<=u,v<=m,0<=w<=1e7,u!=v),表示从u到v的排管的水流流量是w。

Output

对此每一种景况输出三个整数,表示从1到m的最大排水流量。
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output
50

模板题,,,直接套就行

#include <iostream>#include <bits/stdc++.h>#define ms memset(a , b , sizeofusing namespace std;//前向星typedef long long ll;const int maxn = 1e4;const int inf = 0x3f3f3f3f;int n , m;struct Edge{    int to;    int next;    int w;}edge[maxn << 1];int head[maxn];bool vis[maxn];int cnt;void init(){    ms(head , -1);    cnt = 0;}void add(int u , int v , int w){    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt++;    edge[cnt].to = u;                       //添加反向边,,流量为零    edge[cnt].w = 0;    edge[cnt].next = head[v];    head[v] = cnt++;}int step[maxn];bool bfs(int s , int t){    ms(step , -1);    step[s] = 0;    queue<int> q;    q.push;    while (!q.empty    {        int u = q.front;        for (int i = head[u]; i != -1; i = edge[i].next)        {            if (step[edge[i].to] == -1 && edge[i].w > 0)            {                step[edge[i].to] = step[u] + 1;                q.push(edge[i].to);                if (edge[i].to == t) return true;            }        }    }    return step[t] != -1;}int dfs(int s , int t , int f){    if (s == t || !f)   return f;    int flow = 0;    for (int i = head[s]; i != -1; i = edge[i].next)    {        if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)        {            int d = dfs(edge[i].to , t , min(edge[i].w , f));            if             {                edge[i].w -= d;                edge[i ^ 1].w += d;                flow += d;                  //累加当前节点的某条路径的合适流量                f -= d;                     //当前节点的容量减去某条路径的合适流量                if  break;          //如果当前节点的容量用完,说明无法再通过任何流量            }        }    }    if (flow == 0)  step[s] = inf;      //如果当前节点无任何流量通过,取消标记    return flow;}int Dinic(int s , int t){    int flow = 0;    while (bfs    {        flow += dfs(s , t , inf);    }    return flow;}int main(){    //ios_base::sync_with_stdio;    while (~scanf("%d%d", &n , &m))    {        int u , v , w;        init();        for (int i = 1; i <= n; i++)        {            //cin >> u >> v >> w;            scanf("%d%d%d" , &u , &v , &w);            add(u , v , w);        }        printf("%d\n" , Dinic;        //cout << "Case " << k++ << ": " << ans << endl;    }    return 0;}

学长用的分界表存的,,,

学长的代码:

// hdu 1532#include <bits/stdc++.h>using namespace std;typedef long long ll;#define PB push_backconst int INF = 0x3f3f3f3f;const int maxn = 205;int n,m;struct Edge{    int to,cap,idx;    Edge(){}    Edge(int to,int cap,int idx):to,cap,idx{}};vector<Edge> V[maxn];bool vis[maxn];void add_edge(int u,int v,int w){    V[u].PB(Edge(v,w,V[v].size;    V[v].PB(Edge(u,0,V[u].size;}int dfs(int s,int t,int f){    if return f;    vis[s]=true;    for(int i=0;i<V[s].size    {        Edge &cur = V[s][i];        if(!vis[cur.to] && cur.cap>0)        {            int tmp = dfs(cur.to,t,min(f,cur.cap));            if            {                cur.cap -= tmp;                V[cur.to][cur.idx].cap += tmp;                return tmp;            }        }    }    return 0;}int Ford_Fulkerson(int s,int t){    int res = 0;    while    {        memset(vis,false,sizeof;        int flow = dfs;        if return res;        res += flow;    }}int main(){    while(~scanf("%d%d",&n,&m))    {        for(int i=1;i<=m;i++) V[i].clear();        int u,v,w;        for(int i=1;i<=n;i++)        {            scanf("%d%d%d",&u,&v,&w);            add_edge;        }        printf("%d\n",Ford_Fulkerson;    }    return 0;}

Problem B: 最大流

Time Limit: 1 Sec Memory Limit: 128 MB

Description

如题,给您2个体量互连网,请您找出最大流。

Input

首先行输入包罗三个整数T,表示测试用例的数目。

对于每一个测试用例,第①行包含八个整数N和M,表示图中顶点和边的多寡。(2
<= N <= 15,0 <= M <= 1000)

接下去的M行,每行李包裹括四个整数X,Y和C,表示从X到Y有贰个边,它的容积是C.(1
<= X,Y <= N,1 <= C <= 一千)

Output

对于各类测试用例,您应该出口从起点1到汇点N的最大流量。

Sample Input
2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Sample Output
Case 1: 1
Case 2: 2

无差距于是模板题,,,但是刚开端自我套fk的模版平素tle就换了dinic算法

#include <iostream>#include <bits/stdc++.h>#define ms memset(a , b , sizeofusing namespace std;//前向星const int maxn = 1e4;const int inf = 0x3f3f3f3f;int n , m;struct Edge{    int to;    int next;    int w;}edge[maxn << 1];int head[maxn];bool vis[maxn];int cnt;void init(){    ms(head , -1);    cnt = 0;}void add(int u , int v , int w){    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt++;    edge[cnt].to = u;                       //添加反向边,,流量为零    edge[cnt].w = 0;    edge[cnt].next = head[v];    head[v] = cnt++;}int step[maxn];bool bfs(int s , int t){    ms(step , -1);    step[s] = 0;    queue<int> q;    q.push;    while (!q.empty    {        int u = q.front;        for (int i = head[u]; i != -1; i = edge[i].next)        {            if (step[edge[i].to] == -1 && edge[i].w > 0)            {                step[edge[i].to] = step[u] + 1;                q.push(edge[i].to);                if (edge[i].to == t) return true;            }        }    }    return step[t] != -1;}int dfs(int s , int t , int f){    if (s == t || !f)   return f;    int flow = 0;    for (int i = head[s]; i != -1; i = edge[i].next)    {        if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)        {            int d = dfs(edge[i].to , t , min(edge[i].w , f));            if             {                edge[i].w -= d;                edge[i ^ 1].w += d;                flow += d;                  //累加当前节点的某条路径的合适流量                f -= d;                     //当前节点的容量减去某条路径的合适流量                if  break;          //如果当前节点的容量用完,说明无法再通过任何流量            }        }    }    if (flow == 0)  step[s] = inf;      //如果当前节点无任何流量通过,取消标记    return flow;}int Dinic(int s , int t){    int flow = 0;    while (bfs    {        flow += dfs(s , t , inf);    }    return flow;}int main(){    //ios_base::sync_with_stdio;    int t;scanf("%d" , &t);    //cin >> t;    int k = 1;    while     {        //cin >> n >> m;        scanf("%d%d", &n , &m);        int u , v , w;        init();        for (int i = 1; i <= m; i++)        {            //cin >> u >> v >> w;            scanf("%d%d%d" , &u , &v , &w);            add(u , v , w);        }        printf("Case %d: %d\n" , k++ , Dinic;        //cout << "Case " << k++ << ": " << ans << endl;    }    return 0;}

学长的代码:

// hdu 3549#include <bits/stdc++.h>using namespace std;typedef long long ll;#define PB push_backconst int INF = 0x3f3f3f3f;const int maxn = 20;int c[maxn][maxn],f[maxn][maxn],p[maxn],a[maxn];int m,n;int bfs(){    queue<int> q;    memset(p,-1,sizeof;    memset(a,0,sizeof;    a[1] = INF;    q.push;    while(!q.empty    {        int u = q.front;        for(int i=1;i<=n;i++)        {            if(!a[i] && c[u][i]>f[u][i])            {                p[i] = u;                q.push;                a[i] = min(a[u],c[u][i]-f[u][i]);            }        }        if break;    }    if return 0;    for(int u=n;u!=1;u=p[u])    {        f[p[u]][u] += a[n];        f[u][p[u]] -= a[n];    }    return a[n];}int Edmonds_Karp(){    int res = 0;    while    {        int tmp = bfs();        if return res;        res += tmp;    }}int main(){    int t;    scanf("%d",&t);    for(int ca=1;ca<=t;ca++)    {        scanf("%d%d",&n,&m);        memset(c,0,sizeof;        memset(f,0,sizeof;        int u,v,w;        for(int i=1;i<=m;i++)        {            scanf("%d%d%d",&u,&v,&w);            c[u][v] += w;        }        int max_flow=Edmonds_Karp();        printf("Case %d: %d\n",ca,max_flow);    }    return 0;}

Problem C: 房子和车

葡京手机登陆网址,Time Limit: 1 Sec Memory Limit: 128 MB

Description

华中农林科技(science and technology)高校累计有n个老师,f种房子和d种车(1 <= n,f,d <=
200)。每种导师都有温馨喜爱的一部分房屋和车的项目,现在要你把这几个房子和车分配给那n个老师,种种导师只分红一套房子和一辆车。问您最多能使某个个教授满意对应的分红。

Input

有多组测试数据,每组测试数据第贰行是二个正整数,n,f,d,表示老师个数,房子种数,车子种数。

其次行李包裹罗f个整数,个中第i个数表示第i种房子的个数。

其三行李包裹蕴d个整数,当中第i个数表示第i种车子的个数。

此后n行,每行李包裹涵长度为f的字符串,个中第i行第j个字符表示第i个老师是不是喜欢第j种房子,‘Y’表示欣赏,‘N’表示不希罕。

然后n行,每行李包裹罗长度为d的字符串,个中第i行第j个字符表示第i个名师是或不是喜欢第j种车子,‘Y’表示喜欢,‘N’表示不欣赏。

Output

对此每组测试数据,输出二个平头,表示最大的教员满足的个数。

Sample Input
4 3 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY
Sample Output
3

那道题首要是将标题所给的新闻用图描述出来,,,老师的处理是一分成二即可,,,

自家的代码:

#include <iostream>#include <bits/stdc++.h>#define ms memset(a , b , sizeofusing namespace std;//前向星typedef long long ll;const int maxn = 1e5;const int maxm = 1e3 + 10;const int inf = 0x3f3f3f3f;int n , f , d;int home[maxm];int car[maxm];struct Edge{    int to;    int next;    int w;}edge[maxn << 1];int head[maxn];bool vis[maxn];int cnt;void init(){    ms(head , -1);    cnt = 0;}void add(int u , int v , int w){    edge[cnt].to = v;    edge[cnt].w = w;    edge[cnt].next = head[u];    head[u] = cnt++;    edge[cnt].to = u;                       //添加反向边,,流量为零    edge[cnt].w = 0;    edge[cnt].next = head[v];    head[v] = cnt++;}int step[maxn];bool bfs(int s , int t){    ms(step , -1);    step[s] = 0;    queue<int> q;    q.push;    while (!q.empty    {        int u = q.front;        for (int i = head[u]; i != -1; i = edge[i].next)        {            if (step[edge[i].to] == -1 && edge[i].w > 0)            {                step[edge[i].to] = step[u] + 1;                q.push(edge[i].to);                if (edge[i].to == t) return true;            }        }    }    return step[t] != -1;}int dfs(int s , int t , int f){    if (s == t || !f)   return f;    int flow = 0;    for (int i = head[s]; i != -1; i = edge[i].next)    {        if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)        {            int d = dfs(edge[i].to , t , min(edge[i].w , f));            if             {                edge[i].w -= d;                edge[i ^ 1].w += d;                flow += d;                  //累加当前节点的某条路径的合适流量                f -= d;                     //当前节点的容量减去某条路径的合适流量                if  break;          //如果当前节点的容量用完,说明无法再通过任何流量            }        }    }    if (flow == 0)  step[s] = inf;      //如果当前节点无任何流量通过,取消标记    return flow;}int Dinic(int s , int t){    int flow = 0;    while (bfs    {        flow += dfs(s , t , inf);    }    return flow;}int main(){    //ios_base::sync_with_stdio;    while (~scanf("%d%d%d", &n , &f , &d))    {        init();        for (int i = 1; i <= f; i++)            scanf("%d" , &home[i]);        for (int i = 1; i <= d; i++)            scanf("%d" , &car[i]);        int s = 0;                                  //超级原点        int t = f + n + n + d + 1;                  //汇点        for (int i = 1; i <= f; i++)            add(0 , i , home[i]);                   //原点到每个房子的点建边        char str[maxm];        for (int i = 1; i <= n; i++)        {            scanf("%s" , str);            for (int j = 1; j <= f; j++)            {                if (str[j - 1] == 'Y')                    add(j , i + f, 1);              //老师满意的和对应的房子连接,,,流量为1            }            add(i + f , f + n + i , 1);             //分离出两个老师的点,,,同一个老师之间流量为1        }        for (int i = 1; i <= n; i++)        {            scanf("%s" , str);            for (int j = 1; j <= d; j++)                if (str[j - 1] == 'Y')                add(f + n + i , f + n + n + j , 1);//第二个老师的点和车子建边,,,流量为1        }        for (int i = 1; i <= d; i++)            add(f + n + n + i , t , car[i]);        //汇点和车子之间建边,        printf("%d\n" , Dinic;    }    return 0;}         add(f + n + n + i , t , 1);//----------//这个在处理点之间的关系和我的不同,,,一个是老师分开另一个是分开的老师相邻就是下面这个        int s = 0;        int t = f + n + n + d + 1;        for (int i = 1; i <= f; i++)            add(0 , i , home[i]);         char str[maxm];        for (int i = 1; i <= n; i++)        {            scanf("%s" , str);            for (int j = 1; j <= f; j++)            {                if (str[j - 1] == 'Y')                    add(j , f + 2 * i - 1 , 1);            }            add(f + 2 * i - 1 , f + 2 * i , 1);        }        for (int i = 1; i <= n; i++)        {            scanf("%s" , str);             for (int j = 1; j <= d; j++)                if (str[j - 1] == 'Y')                add(f + 2 * i , f + n + n + j , 1);        }         for (int i = 1; i <= d; i++)            add(f + n + n + i , t , car[i]);         printf("%d\n" , Dinic;

学长的代码:

// hdu 4292#include<stdio.h>#include<string.h>#include<algorithm>#include<queue>#define INF 0x3f3f3f3f#define mem memset(a,b,sizeofusing namespace std;const int N=1000+50;const int M=1e6+50;struct node{    node() {};    node(int tv,int tw,int tnext)    {        v=tv,w=tw,next=tnext;    };    int v,w,next;} e[M];int first[N],vis[N],dis[N],tot;void add_edge(int u,int v,int w){    e[tot]=node(v,w,first[u]);    first[u]=tot++;    e[tot]=node(u,0,first[v]);    first[v]=tot++;}int bfs(int s,int t){    mem;    mem;    queue<int>q;    q.push;    vis[s]=1;    while(!q.empty    {        int u=q.front();        q.pop();        for(int i=first[u]; ~i; i=e[i].next)        {            if(!vis[e[i].v]&&e[i].w>0)            {                vis[e[i].v]=1;                dis[e[i].v]=dis[u]+1;                q.push;            }        }    }    return dis[t];}int dfs(int u,int t,int flow){    ifreturn flow;    for(int i=first[u]; ~i; i=e[i].next)    {        if(dis[e[i].v]==dis[u]+1&&e[i].w>0)        {            int dd=dfs(e[i].v,t,min(e[i].w,flow));            if            {                e[i].w-=dd;                e[i^1].w+=dd;                return dd;            }        }    }    dis[u]=0;    return 0;}int Dinic(int s,int t){    int ans=0,flow;    while    {        while(flow=dfs            ans+=flow;    }    return ans;}void init(){    mem;    tot=0;}int a[N],b[N];char s[N];int main(){    int n,f,d;    while(~scanf("%d%d%d",&n,&f,&d))    {        init();        for(int i=1; i<=f; i++) scanf("%d",&a[i]);        for(int i=1; i<=d; i++) scanf("%d",&b[i]);        for(int i=1; i<=n; i++)        {            add_edge(f+2*i-1,f+2*i,1);            scanf("%s",s+1);            for(int j=1; j<=f; j++)                if(s[j]=='Y')                    add_edge(j,f+2*i-1,1);        }        for(int i=1; i<=n; i++)        {            scanf("%s",s+1);            for(int j=1; j<=d; j++)                if(s[j]=='Y')                    add_edge(f+2*i,f+2*n+j,1);        }        for(int i=1; i<=f; i++) add_edge;        for(int i=1; i<=d; i++) add_edge(2*n+f+i,2*n+f+d+1,b[i]);        printf("%d\n",Dinic(0,2*n+f+d+1));    }    return 0;}

Problem D: 回家

Time Limit: 5 Sec Memory Limit: 128 MB

Description

在网格地图上有n个人和n个房子。在种种单位时间内,每一种人都得以水平或垂直运动到相邻点。对于种种人,你要求为他移动的每一步支付1法郎的旅行费,直到她进来房屋。每种房子只可以容纳1人。今后问你全体人都回来房子所要求的最少花费是稍稍?输入是三个网格图,‘.’表示空地,‘H’表示房子,‘m’表示人。

Input

有多组测试数据,对于每组测试数据第1行是七个正整数n,m表示地图的行和列(2<=n,m<=100)。地图上有相同数量的房屋和人,房子最多不超越100。输入以n=0,m=0甘休。

Output

对此每组测试数据输出1个平头,表示全部人都回来房子所需的微小成本。

Sample Input
2 2
.m

H.
5 5
HH..m
…..
…..
…..
mm..H
7 8
…H….
…H….
…H….
mmmHmmmm
…H….
…H….
…H….
0 0

Sample Output
2
10
28

那道题自个儿做的时候被网上的沙盘坑了一手,,,一向tle,,,换模板就行了,,,
关键思路是,先将人房找到,,,计算出每1人和具有房屋平素的离开,,这几个距离也叫曼哈顿距离,,,然后人房直接建边,,再弄贰个一流原点和汇点求原点和平谈判会议顶啊直接的蝇头耗费的最大流就能够了,,,,

#include <iostream>#include <bits/stdc++.h>#define ms memset(a , b , sizeofusing namespace std;//前向星typedef long long ll;const int maxn = 1e3 + 5;const int maxm = 1e3 + 5;const int inf = 0x3f3f3f3f;int n , m;char mp[maxm][maxm];struct Man{    int x , y;}man[maxn];int cnt_man;struct Home{    int x , y;}home[maxn];int cnt_home;struct Edge{    int v;    int u;    int next;    int cap;    int cost;    Edge(){}    Edge(int u , int v, int cap , int cost , int next):u , cap , cost , next{}}edge[maxn << 7];int head[maxn];int cnt;void init(){    ms(head , -1);    cnt = 0;    cnt_home = 1;    cnt_man = 1;}void add(int from , int to , int cap , int cost){    edge[cnt] = Edge(from , to , cap , cost , head[from]);    head[from] = cnt++;    edge[cnt] = Edge(to , from , 0 , -cost , head[to]);    head[to] = cnt++;}int dis[maxn << 1];int pe[maxn << 1];bool vis[maxn << 1];bool spfa(int s , int t){    ms(dis , inf);    ms(vis , false);    ms;    dis[0] = 0;    vis[s] = true;    queue<int> q;    q.push;    while(!q.empty    {        int u = q.front;        vis[u] = false;        for (int i = head[u]; i != -1; i = edge[i].next)        {            int v = edge[i].v;            int cost = edge[i].cost;            if (edge[i].cap > 0 && dis[v] > dis[u] + cost)            {                dis[v] = dis[u] + cost;                pe[v] = i;                if                 {                    vis[v] = true;                    q.push;                }            }        }    }    if (dis[t] == inf)  return false;    return true;}int min_cost_flow(int s , int t , int f){    int res = 0;    while (spfa    {        int flow = inf;        for (int i = pe[t]; i != -1; i = pe[edge[i].u])        {            flow = min(flow , edge[i].cap);        }        f -= flow;        if   break;        for (int i = pe[t]; i != -1; i = pe[edge[i].u])        {            edge[i].cap -= flow;            edge[i ^ 1].cap += flow;        }        res += flow * dis[t];    }    return res;}int main(){    //ios_base::sync_with_stdio;    while (~scanf("%d%d", &n , &m) && n && m)    {        init();        char str[maxm];        for (int i = 1; i <= n; i++)        //存图        {            scanf("%s" , str);            for (int j = 1; j <= m; j++)                mp[i][j] = str[j - 1];        }        for (int i = 1; i <= n; i++)        //人房分离,,记录坐标        {            for (int j = 1; j <= m; j++)            {                if (mp[i][j] == 'H')                {                    home[cnt_home].x = i;                    home[cnt_home++].y = j;                }                else if (mp[i][j] == 'm')                {                    man[cnt_man].x = i;                    man[cnt_man++].y = j;                }            }        }        for (int i = 1; i <= cnt_man - 1; i++)        {            for (int j = 1; j <= cnt_home - 1; j++)            {                               //算出每一个人对于所有房子的距离,,,,,                int w = fabs(man[i].x - home[j].x) + fabs(man[i].y - home[j].y);                add(i , j + cnt_man - 1 , 1 , w);       //人房之间连边,,,流量为刚刚的值            }        }        int t = cnt_home;                   //汇点        t *= 2;        t--;        for (int i = 1; i <= cnt_man - 1; i++)  //超级原点和每个人建边,,流量为0            add(0 , i , 1 , 0);        for (int i = cnt_man; i <= t - 1; i++)  //房子和汇点建边            add(i , t , 1 , 0);        printf("%d\n" , min_cost_flow(0 , t , t + 1));    }    return 0;}

学长的代码:

// hdu 1533#include <cstdio>#include <queue>#include <cstring>#include <cstdlib>using namespace std;typedef long long ll;#define PB push_backconst int INF = 0x3f3f3f3f;const int maxn = 1005;typedef pair<int,int> P;char mp[105][105];int dist[maxn<<1],pe[maxn<<1],head[maxn<<1];bool vis[maxn<<1];int n,m,tot;struct Edge{    int u,v,cap,cost,next;    Edge(){}    Edge(int u,int v,int cap,int cost,int next):u,cap,cost,next{}}edge[maxn<<7];void add_edge(int from,int to,int cap,int cost){    edge[tot] = Edge(from,to,cap,cost,head[from]);    head[from] = tot++;    edge[tot] = Edge(to,from,0,-cost,head[to]);    head[to] = tot++;}bool SPFA(int s,int t){    memset(dist,INF,sizeof;    memset(vis,false,sizeof;    memset(pe,-1,sizeof;    dist[s]=0;    vis[s]=true;    queue<int> q;    q.push;    while(!q.empty    {        int u = q.front;        vis[u] = false;        for(int i=head[u];i!=-1;i=edge[i].next)        {            int v = edge[i].v;            int cost = edge[i].cost;            if(edge[i].cap>0 && dist[v]>dist[u]+cost)            {                dist[v] = dist[u]+cost;                pe[v] = i;                if                {                    vis[v]=true;                    q.push;                }            }        }    }    if(dist[t]==INF) return false;    else return true;}int min_cost_flow(int s,int t,int f){    int res = 0;    while)    {        int flow = INF;        for(int i=pe[t];i!=-1;i=pe[edge[i].u])        {            flow = min(flow,edge[i].cap);        }        f -= flow;        if break;        for(int i=pe[t];i!=-1;i=pe[edge[i].u])        {            edge[i].cap -= flow;            edge[i^1].cap += flow;        }        res += flow*dist[t];    }    return res;}int dis{    return abs(a.first-b.first)+abs(a.second-b.second);}int main(){    while(~scanf("%d%d",&n,&m) && (n!=0 && m!=0))    {        int num1=0,num2=0;        P man[maxn],hos[maxn];        for(int i=1;i<=n;i++)        {            scanf("%s",mp[i]);            for(int j=0;j<m;j++)            {                if(mp[i][j]=='m')                    man[++num1] = P;                if(mp[i][j]=='H')                    hos[++num2] = P;            }        }        int s=0,t=num1+num2+1;        memset(head,-1,sizeof;        tot=0;        for(int i=1;i<=num1;i++)            add_edge;        for(int i=1;i<=num2;i++)            add_edge(num1+i,t,1,0);        for(int i=1;i<=num1;i++)        {            for(int j=1;j<=num2;j++)            {                add_edge(i,num1+j,1,dis(man[i],hos[j]));            }        }        printf("%d\n",min_cost_flow);    }    return 0;}

~~~~~~