題意：
? ? ? 給你一個(gè)n*m的地圖，上面有w個(gè)人，和w個(gè)房子，每個(gè)人都要進(jìn)房子，每個(gè)房子只能進(jìn)一個(gè)人，問(wèn)所有人都進(jìn)房子的路徑總和最少是多少？


思路：
? ? ? 比較簡(jiǎn)單的最大流，直接建立兩排，左邊人，右邊房子，廣搜或者深搜求距離建圖，然后一邊費(fèi)用流就行了，比較簡(jiǎn)單，沒(méi)啥說(shuō)的地方，就這樣。
? ?


#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 200 + 10
#define N_edge (200 * 200 + 200 ) * 2 + 100
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int from ,to ,cost ,flow ,next;
}STAR;


typedef struct
{
? ? int x ,y ,t;
}NODE;


STAR E[N_edge];
NODE xin ,tou;
int list[N_node] ,tot;
int s_x[N_node];
int mer[N_node];
int map[102][102] ,n ,m;
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};


void add(int a ,int b ,int c ,int d)
{
? ? E[++tot].from = a;
? ? E[tot].to = b;
? ? E[tot].cost = c;
? ? E[tot].flow = d;
? ? E[tot].next = list[a];
? ? list[a] = tot;




? ? E[++tot].from = b;
? ? E[tot].to = a;
? ? E[tot].cost = -c;
? ? E[tot].flow = 0;
? ? E[tot].next = list[b];
? ? list[b] = tot;
}


bool SPFA(int s ,int t ,int n)
{
? ? for(int i = 0 ;i <= n ;i ++)
? ? s_x[i] = INF;
? ? bool mark[N_node] = {0};
? ? queue<int>q;
? ? q.push(s);
? ? mark[s] = 1;
? ? s_x[s] = 0;
? ? memset(mer ,255 ,sizeof(mer));
? ? while(!q.empty())
? ? {
? ? ? ? int xin ,tou;
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? mark[tou] = 0;
? ? ? ? for(int k = list[tou] ;k ;k = E[k].next)
? ? ? ? {
? ? ? ? ? ? xin = E[k].to;
? ? ? ? ? ? if(s_x[xin] > s_x[tou] + E[k].cost && E[k].flow)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x[xin] = s_x[tou] + E[k].cost;
? ? ? ? ? ? ? ? mer[xin] = k;
? ? ? ? ? ? ? ? if(!mark[xin])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return mer[t] != -1;
}




int M_C_Flow(int s ,int t ,int n)
{
? ? int mincost = 0 ,maxflow = 0 ,minflow;
? ? while(SPFA(s ,t ,n))
? ? {
? ? ? ? minflow = INF;
? ? ? ? for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
? ? ? ? if(minflow > E[i].flow) minflow = E[i].flow;
? ? ? ? for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
? ? ? ? {
? ? ? ? ? ? E[i].flow -= minflow;
? ? ? ? ? ? E[i^1].flow += minflow;
? ? ? ? ? ? mincost += E[i].cost;
? ? ? ? }
? ? ? ? maxflow += minflow;
? ? }
? ? return mincost;
}




void BFS_Buid(int x ,int y ,int N)
{
? ? xin.x = x ,xin.y = y ,xin.t = 0;
? ? int mark[105][105] = {0};
? ? queue<NODE>q;
? ? mark[x][y] = 1;
? ? q.push(xin);
? ? while(!q.empty())
? ? {
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? if(map[tou.x][tou.y] > N)
? ? ? ? add(map[x][y] ,map[tou.x][tou.y] ,tou.t ,INF);
? ? ? ? for(int i = 0 ;i < 4 ;i ++)
? ? ? ? {
? ? ? ? ? ? xin.x = tou.x + dir[i][0];
? ? ? ? ? ? xin.y = tou.y + dir[i][1];
? ? ? ? ? ? xin.t = tou.t + 1;
? ? ? ? ? ? if(xin.x >= 1 && xin.x <= n && xin.y >= 1 && xin.y <= m && !mark[xin.x][xin.y])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[xin.x][xin.y] = 1;
? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return ;
}


int main ()
{
? ? int i ,j;
? ? char str[105][105];
? ? while(~scanf("%d %d" ,&n ,&m) && n + m)
? ? {
? ? ? ? int M = 0 ,H = 0 ,N = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%s" ,str[i]);
? ? ? ? ? ? for(j = 0 ;j < m ;j ++)
? ? ? ? ? ? if(str[i][j] == 'm')
? ? ? ? ? ? N ++;
? ? ? ? }
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? for(j = 1 ;j <= m ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(str[i][j-1] == '.') map[i][j] = 0;
? ? ? ? ? ? ? ? else if(str[i][j-1] == 'm') map[i][j] = ++M;
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ++H;
? ? ? ? ? ? ? ? ? ? map[i][j] = H + N;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? memset(list ,0 ,sizeof(list)) ,tot = 1;
? ? ? ? for(i = 1 ;i <= N ;i ++)
? ? ? ? add(0 ,i ,0 ,1) ,add(i + N ,N + N + 1 ,0 ,1);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= m ;j ++)
? ? ? ? {
? ? ? ? ? ? if(map[i][j] && map[i][j] <= N)
? ? ? ? ? ? BFS_Buid(i ,j ,N);
? ? ? ? }
? ? ? ? printf("%d\n" ,M_C_Flow(0 ,N + N + 1 ,N + N + 1));
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ2195费用流+BFS建图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。