开发者社区> 余二五> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

poj 2195 Going Home

简介:
+关注继续查看
/*
   做网络流的题建图真的是太重要了!
   本题是将人所在的位置和房子所在的位置建立边的联系,其中man到house这一条边的流量为 1, 费用为两者的距离
   而方向边的流量为 0, 费用为正向边的相反数(也就是沿着反向边进行增广时,费用要减少,更改先前错误的选择) 
   最后增加一个源点和一个汇点完毕(源点映射到man, house映射到汇点, 费用为0, 流量为1) 
*/
#include<iostream> 
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#define Max 0x3f3f3f3f
#define N 205
using namespace std;

class node
{
public:  
   int x, y;
};

node xyM[N];
node xyH[N];
int cost[N][N], cap[N][N];
int cntM, cntH;
int pre[N*2], dist[N*2], vis[N*2], n, m;

void addE(int i, int j, int ct, int cp)
{
    cost[i][j]=ct;
    cap[i][j]=cp;
    cost[j][i]=-ct;
    //cap[j][i]=0;
}

int s, t, minCost;

void buildMap()
{
   int i, j;
   memset(cap, 0, sizeof(cap));
   s=0; t=cntM+cntH+1;
   for(i=0; i<cntM; ++i)
     addE(0, i+1, 0, 1);  
   for(i=0; i<cntH; ++i)
     addE(cntM+i+1, t, 0, 1);
   for(i=0; i<cntM; ++i)
     for(j=0; j<cntH; ++j)
       addE(i+1, cntM+j+1, abs(xyM[i].x-xyH[j].x)+abs(xyM[i].y-xyH[j].y), 1);
}

queue<int>q;

int spfa()
{
    int u, v;
    memset(dist, 0x3f, sizeof(dist));
    dist[0]=0;
    q.push(0);
    vis[0]=1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=0;
        for(v=0; v<=t; ++v)
          if(cap[u][v]>0 && dist[v]>dist[u]+cost[u][v])
          {
              dist[v]=dist[u]+cost[u][v];
              pre[v]=u;
              if(!vis[v])
              {
                    vis[v]=1;
                    q.push(v);
          }
      }
    }
    if(dist[t]==Max)
      return 0;
    return 1;
}

void updateEdge()
   int u, minFlow=Max;
   for(u=t; u!=s; u=pre[u])//通过最短路径寻找这条路径上的最小流量 
      if(cap[pre[u]][u]<minFlow)
        minFlow=cap[pre[u]][u];
    for(u=t; u!=s; u=pre[u])
    {
        cap[pre[u]][u]-=minFlow;
        cap[u][pre[u]]+=minFlow;
        minCost+=cost[pre[u]][u];
    }
}

int main()
{
   int i, j;
   char c;
   while(scanf("%d%d", &n, &m) && (n||m))
   {
       cntM=cntH=0;
       minCost=0;
       for(i=1; i<=n; ++i)
         {
           getchar();
       for(j=1; j<=m; ++j)
             {
            scanf("%c", &c);
            if(c=='m')
            {
               xyM[cntM].x=i;
               xyM[cntM++].y=j;
        }
        else if(c=='H')
        {
           xyH[cntH].x=i;
               xyH[cntH++].y=j;
        }
         }
        }
        buildMap();
        while(spfa())
          updateEdge();
        printf("%d\n", minCost);
   }
   return 0;
}//邻接表
复制代码
  1 #include<iostream>
  2 #include<queue>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #define INF 0x3f3f3f3f
  7 #define N 1000005
  8 using namespace std;
  9 
 10 int cntH, cntM;
 11 
 12 struct node{
 13     int x, y;
 14 };
 15 
 16 struct EDGE{
 17     int u, v, cap, cost, nt;
 18 };
 19 EDGE edge[N];
 20 
 21 queue<int>q;
 22 node man[105], house[105];
 23 int first[205];
 24 int dist[205];
 25 int pre[205], flow[205], vis[205];
 26 int cnt, t;
 27 int minCost;
 28 int n, m;
 29 
 30 void addEdge(int u, int v, int cap, int cost){
 31     edge[cnt].u=u;
 32     edge[cnt].v=v;
 33     edge[cnt].cap=cap;
 34     edge[cnt].nt=first[u];
 35     edge[cnt].cost=cost;
 36     first[u]=cnt++;
 37     
 38     edge[cnt].u=v;
 39     edge[cnt].v=u;
 40     edge[cnt].cap=0;
 41     edge[cnt].nt=first[v];
 42     edge[cnt].cost=-cost;
 43     first[v]=cnt++;
 44 }
 45 
 46 void buildMap(){
 47     memset(first, -1, sizeof(first));
 48     t=cntH+cntM+1;
 49     for(int i=1; i<=cntM; ++i)
 50         for(int j=1; j<=cntH; ++j)
 51             addEdge(i, cntM+j, 1, abs(man[i].x-house[j].x) + abs(man[i].y-house[j].y));
 52     for(int i=1; i<=cntM; ++i)
 53         addEdge(0, i, 1, 0);
 54     for(int i=1; i<=cntH; ++i)
 55         addEdge(cntM+i, t, 1, 0); 
 56 }
 57 
 58 bool MCMF(){
 59     memset(dist, 0x3f, sizeof(dist));
 60     memset(vis, 0, sizeof(vis));
 61     q.push(0);
 62     flow[0]=INF;
 63     dist[0]=0;
 64     vis[0]=1;
 65     while(!q.empty()){
 66         int u=q.front(); q.pop();
 67         vis[u]=0;
 68         for(int e=first[u]; ~e; e=edge[e].nt){
 69             int v=edge[e].v, cap=edge[e].cap, cost=edge[e].cost;
 70             if(cap>0 && dist[v]>dist[u]+cost){
 71                 dist[v]=dist[u]+cost;
 72                 flow[v]=min(flow[u], cap);
 73                 pre[v]=e;
 74                 if(!vis[v]){
 75                     vis[v]=1;
 76                     q.push(v);
 77                 }
 78             }
 79         }
 80     }
 81     if(dist[t]==INF) return false;
 82     minCost+=dist[t];
 83     int x=t;
 84     while(x!=0){
 85         edge[pre[x]].cap-=flow[t];
 86         edge[pre[x]^1].cap+=flow[t];
 87         x=edge[pre[x]].u;
 88     }
 89     return true;
 90 }
 91  
 92 int main(){
 93     while(scanf("%d%d", &n, &m) && (n||m)){
 94         cnt=cntH=cntM=0;
 95         for(int i=1; i<=n; ++i){
 96             getchar();
 97             for(int j=1; j<=m; ++j){
 98                 char ch;
 99                 scanf("%c", &ch);
100                 if(ch=='m'){
101                     man[++cntM].x=i;
102                     man[cntM].y=j;
103                 }
104                 else if(ch=='H'){
105                     house[++cntH].x=i;
106                     house[cntH].y=j;
107                 }
108             }
109         }
110         buildMap();
111         minCost=0;
112         while(MCMF());
113         printf("%d\n", minCost);
114     }
115     return 0;
116 } 
复制代码









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3809620.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
GIF图像动态生成-JAVA后台生成
本文简要讲述了GIF图像知识,并且以JAVA技术为例,介绍了后台生成GIF的技术,并提供较详细的代码示例,希望对您有帮助。最后怀念因新冠感染去世的GIF的发明者,斯蒂芬•威尔海特。
18 0
那些必会用到的 ES6 精粹(下)
那些必会用到的 ES6 精粹(下)
37 0
重磅 | 山东省医保信息平台引入阿里云产品技术,结算响应速度提升近10倍
阿里云承载了山东省医保业务核心系统,助力医保信息平台顺利交付,并与国家局业务系统进行适配和对接,是医保业务系统的坚实底座。医保系统的信息化升级,让老百姓就医更便利,医保服务更智能、更高效
328 0
阿里云基础产品技术月刊 2019年3月
3月20日阿里云在2019 NVIDIA GPU技术大会上发布了国内首个公共云上的轻量级GPU异构计算产品VGN5i实例。
4706 0
GIF、JPEG 和 PNG的区别在哪…
原文地址:GIF、JPEG 和 PNG的区别在哪里?作者:苗得雨 GIF、JPEG 和 PNG 是三种最常见的图片格式。 GIF:1987 年诞生,常用于网页动画,使用无损压缩,支持 256 种颜色(一般叫 8 bit 彩色),支持单一透明色; JPEG:1992 年出世,照片一...
909 0
+关注
20376
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载