網路流

来源: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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類