網路流

来源:https://www.cnblogs.com/31415926535x/archive/2018/07/31/9398768.html
-Advertisement-
Play Games

title: 網路流 date: 2018 07 31 22:01:22 tags: acm 演算法 網路流 概述 這篇博客主要是關於網路流的一些基本的知識點以及相應的模板，， 算了，，，還是先貼大佬的博客，，，暑假在補一下。。。。QAQ <! more 網路流 tan90，，，，，，， 習題 Pro ...


title: 網路流
date: 2018-07-31 22:01:22
tags:

  • acm
  • 演算法

  • 網路流

概述

這篇博客主要是關於網路流的一些基本的知識點以及相應的模板，，

算了，，，還是先貼大佬的博客，，，暑假在補一下。。。。QAQ

網路流

tan90，，，，，，，

習題

Problem A: 養豬

Time Limit: 1 Sec Memory Limit: 128 MB

Description

AveryBoy喜歡玩LOL，但是他技術太菜，總是被別人噴“這麼菜玩什麼游戲，回家養豬去吧”。終於有一天，他被噴的受不了了，於是回家養豬。不過他家的養豬場在下雨天的時候總是被淹，所以他用讀書學來的知識設計了一套排水系統。他還設計了一套裝置，可以控制排水管道的水流流量。現在有n個排水管道，m個排水節點，問你從1到m的最大排水流量。

Input

有多組測試數據，對於每組測試數據，第一行是兩個整數n，m（0 <= n <= 200，2 <= m <= 200），分別表示排水管道數和排水節點數。之後n行每行包含3個整數，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(a , b) memset(a , b , sizeof(a))

using 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(s);
    while (!q.empty())
    {
        int u = q.front();q.pop();
        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 (d > 0)
            {
                edge[i].w -= d;
                edge[i ^ 1].w += d;
                flow += d;                  //累加當前節點的某條路徑的合適流量
                f -= d;                     //當前節點的容量減去某條路徑的合適流量
                if (f == 0) break;          //如果當前節點的容量用完,說明無法再通過任何流量
            }
        }

    }
    if (flow == 0)  step[s] = inf;      //如果當前節點無任何流量通過,取消標記
    return flow;
}
int Dinic(int s , int t)
{
    int flow = 0;
    while (bfs(s , t))
    {
        flow += dfs(s , t , inf);
    }
    return flow;
}
int main()
{
    //ios_base::sync_with_stdio(0);
    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(1 , m));
        //cout << "Case " << k++ << ": " << ans << endl;
    }
    return 0;
}

學長用的鄰接表存的，，，

學長的代碼:

// hdu 1532
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define PB push_back
const 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(to),cap(cap),idx(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()-1));
}

int dfs(int s,int t,int f)
{
    if(s==t) return f;
    vis[s]=true;
    for(int i=0;i<V[s].size();i++)
    {
        Edge &cur = V[s][i];
        if(!vis[cur.to] && cur.cap>0)
        {
            int tmp = dfs(cur.to,t,min(f,cur.cap));
            if(tmp>0)
            {
                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(true)
    {
        memset(vis,false,sizeof(vis));
        int flow = dfs(s,t,INF);
        if(flow==0) 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(u,v,w);
        }
        printf("%d\n",Ford_Fulkerson(1,m));
    }
    return 0;
}

Problem B: 最大流

Time Limit: 1 Sec Memory Limit: 128 MB

Description

如題，給你一個容量網路，請你找出最大流。

Input

第一行輸入包含一個整數T，表示測試用例的數量。

對於每個測試用例，第一行包含兩個整數N和M，表示圖中頂點和邊的數量。（2 <= N <= 15,0 <= M <= 1000）

接下來的M行，每行包含三個整數X，Y和C，表示從X到Y有一個邊，它的容量是C.（1 <= X，Y <= N，1 <= C <= 1000）

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(a , b) memset(a , b , sizeof(a))

using 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(s);
    while (!q.empty())
    {
        int u = q.front();q.pop();
        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 (d > 0)
            {
                edge[i].w -= d;
                edge[i ^ 1].w += d;
                flow += d;                  //累加當前節點的某條路徑的合適流量
                f -= d;                     //當前節點的容量減去某條路徑的合適流量
                if (f == 0) break;          //如果當前節點的容量用完,說明無法再通過任何流量
            }
        }

    }
    if (flow == 0)  step[s] = inf;      //如果當前節點無任何流量通過,取消標記
    return flow;
}
int Dinic(int s , int t)
{
    int flow = 0;
    while (bfs(s , t))
    {
        flow += dfs(s , t , inf);
    }
    return flow;
}
int main()
{
    //ios_base::sync_with_stdio(0);
    int t;scanf("%d" , &t);
    //cin >> t;
    int k = 1;
    while (t--)
    {
        //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(1 , n));
        //cout << "Case " << k++ << ": " << ans << endl;
    }
    return 0;
}

學長的代碼：

// hdu 3549
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define PB push_back
const 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(p));
    memset(a,0,sizeof(a));
    a[1] = INF;
    q.push(1);
    while(!q.empty())
    {
        int u = q.front();q.pop();
        for(int i=1;i<=n;i++)
        {
            if(!a[i] && c[u][i]>f[u][i])
            {
                p[i] = u;
                q.push(i);
                a[i] = min(a[u],c[u][i]-f[u][i]);
            }
        }
        if(a[n]) break;
    }
    if(!a[n]) 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(true)
    {
        int tmp = bfs();
        if(tmp==0) 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(c));
        memset(f,0,sizeof(f));
        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

華中農業大學總共有n個老師，f種房子和d種車（1 <= n，f，d <= 200）。每個老師都有自己喜歡的一些房子和車的類型，現在要你把這些房子和車分配給這n個老師，每個老師只分配一套房子和一輛車。問你最多能使多少個老師滿意對應的分配。

Input

有多組測試數據，每組測試數據第一行是3個正整數，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(a , b) memset(a , b , sizeof(a))

using 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(s);
    while (!q.empty())
    {
        int u = q.front();q.pop();
        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 (d > 0)
            {
                edge[i].w -= d;
                edge[i ^ 1].w += d;
                flow += d;                  //累加當前節點的某條路徑的合適流量
                f -= d;                     //當前節點的容量減去某條路徑的合適流量
                if (f == 0) break;          //如果當前節點的容量用完,說明無法再通過任何流量
            }
        }

    }
    if (flow == 0)  step[s] = inf;      //如果當前節點無任何流量通過,取消標記
    return flow;
}
int Dinic(int s , int t)
{
    int flow = 0;
    while (bfs(s , t))
    {
        flow += dfs(s , t , inf);
    }
    return flow;
}
int main()
{
    //ios_base::sync_with_stdio(0);
    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(s , t));
    }
    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(s , t));

學長的代碼:

// hdu 4292
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using 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(vis,0);
    mem(dis,0);
    queue<int>q;
    q.push(s);
    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(e[i].v);
            }
        }
    }
    return dis[t];
}
int dfs(int u,int t,int flow)
{
    if(u==t)return 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(dd)
            {
                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(bfs(s,t))
    {
        while(flow=dfs(s,t,INF))
            ans+=flow;
    }
    return ans;
}
void init()
{
    mem(first,-1);
    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(0,i,a[i]);
        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美元的旅行費，直到他進入房子。每個房子只能容納一個人。現在問你所有人都回到房子所需要的最少費用是多少？輸入是一個網格圖，‘.’表示空地，‘H’表示房子，‘m’表示人。

Input

有多組測試數據，對於每組測試數據第一行是兩個正整數n，m表示地圖的行和列（2<=n，m<=100）。地圖上有相同數量的房子和人，房子最多不超過100。輸入以n=0，m=0結束。

Output

對於每組測試數據輸出一個整數，表示所有人都回到房子所需的最小費用。

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，，，換模板就行了，，，
主要思路是，先將人房找到，，，計算出每一個人和所有房子直接的距離，，這個距離也叫曼哈頓距離，，，然後人房直接建邊，，再弄一個超級原點和匯點求原點和會頂啊直接的最小費用的最大流就可以了，，，，

#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))

using 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(u) , v(v) , cap(cap) , cost(cost) , next(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(pe , -1);
    dis[0] = 0;
    vis[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();q.pop();
        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])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if (dis[t] == inf)  return false;
    return true;
}
int min_cost_flow(int s , int t , int f)
{
    int res = 0;
    while (spfa(s , t))
    {
        int flow = inf;
        for (int i = pe[t]; i != -1; i = pe[edge[i].u])
        {
            flow = min(flow , edge[i].cap);
        }
        f -= flow;
        if (f < 0)  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(0);
    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 = (int)fabs(man[i].x - home[j].x) + (int)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_back
const 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(u),v(v),cap(cap),cost(cost),next(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(dist));
    memset(vis,false,sizeof(vis));
    memset(pe,-1,sizeof(pe));
    dist[s]=0;
    vis[s]=true;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();q.pop();
        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])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if(dist[t]==INF) return false;
    else return true;
}

int min_cost_flow(int s,int t,int f)
{
    int res = 0;
    while(SPFA(s,t))
    {
        int flow = INF;
        for(int i=pe[t];i!=-1;i=pe[edge[i].u])
        {
            flow = min(flow,edge[i].cap);
        }
        f -= flow;
        if(f<0) 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(P a,P b)
{
    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(i,j+1);
                if(mp[i][j]=='H')
                    hos[++num2] = P(i,j+1);
            }
        }
        int s=0,t=num1+num2+1;
        memset(head,-1,sizeof(head));
        tot=0;
        for(int i=1;i<=num1;i++)
            add_edge(0,i,1,0);
        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(s,t,num1));
    }
    return 0;
}

鴿~~~~~~~~~~~~~~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 我和Python的Py交易》》》》》》 命名空間的小弟作用域
    命名空間的小弟作用域 在這要明確一個觀點，在Python中萬物皆對象，而變數指向的就是對象。 變數可以是 類名，函數名，儲存數據的變數…… 對象可以是 類 ，被封裝的一段代碼（函數），數據…… 命名空間 命名空間是從名字到對象的映射。在Python大多數命名空間目前以字典的形式實現。變數名是“鍵”， ...
  • Java中雙基準快速排序方法(DualPivotQuicksort.sort())的具體實現
    在Java語言的Arrays類下提供了一系列排序(sort)方法,幫助使用者對各種不同數據類型的數組進行排序. 在1.7之後的版本中, Arrays.sort()方法在操作過程中實際調用的是DualPivotQuicksort類下的sort方法,DualPivotQuicksort和Arrays一樣 ...
  • C語言實現線性表(鏈式存儲方式)
    #include #include //提供malloc()原型 typedef struct LNode *List; typedef int ElementType; //定義數據結構的自定義名稱 struct LNode{ ElementType Data; //數據域 List Next; ... ...
  • 列表和元組
    1.什麼是列表 列表是一種可變的數據類型 列表由[]來表示,每一項元素使用逗號隔開,列表什麼都能裝,叫做能裝對象的對象 列表可以裝大量的數據 2.列表的索引和切片 列表和字元串一樣,也有索引和切片,只不過切出來的內容是列表 索引的下標從0開始 切片:[起始位置:結束位置:步長] 3.列表的增刪改查 ...
  • Django從入門到精通--01 新建運行環境
    1.0 新建運行環境 命令： pyvip@Vip:~$ mkvirtualenv -p /usr/bin/python3 Django2Running virtualenv with interpreter /usr/bin/python3Using base prefix '/usr'New py ...
  • web server性能優化淺談
    作者: "Jack47, ZhiYan" 轉載請保留作者和 "原文出處" 性能優化，優化的東西一定得在主路徑上，結合測量的結果去優化。不然即使性能再好，邏輯相對而言執行不了幾次，其實對提示性能的影響微乎其微。記得抖哥以前說多隆在幫忙查廣告搜索引擎的問題，看到了一處代碼，激動的說這裡用他的辦法，性能可 ...
  • #if、#if defined 的使用
    if的使用 if 後面接的是表達式 如果 if後面的表達式能成立，就會把 if和 endif之間的代碼編譯進去 if defined的使用 如果x這個巨集又被定義過，則把 if和 endif之間的代碼編譯進去 註意點 1. 兩個都只是用來決定某段代碼是否被編譯 2. 記得加 endif ...
  • P2P網貸平臺網站開發，小額貸系統,現金貸款系統開發
    綠茶網貸系統是綠茶科技旗下自主開發的網貸系統，可以支持定製p2p網貸網站，網貸平臺網站開發，小額貸系統,現金網貸系統開發,小貸網站開發建設,p2p貸款網站程式,微信網貸網站源碼，這是一套網貸網站管理系統。可以支持定製電腦版+手機版+微信版+小程式版+APP版，由10年的技術團隊專業定製，需要的朋友可 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類