【网络流24题】No. 20 深海机器人问题 （费用流）

【题意】

　　深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器
人。 潜艇到达深海海底后， 深海机器人将离开潜艇向预定目标移动。 深海机器人在移动中还
必须沿途采集海底生物标本。 沿途生物标本由最先遇到它的深海机器人完成采集。 每条预定
路径上的生物标本的价值是已知的， 而且生物标本只能被采集一次。 本题限定深海机器人只
能从其出发位置沿着向北或向东的方向移动， 而且多个深海机器人可以在同一时间占据同一
位置。

【分析】

　　求最大费用流，spfa时不要清-1，要清-INF！！！！！

　　挑了我那么久，悲伤辣么大！！！

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 1010

 #define INF 0xfffffff

 struct node

 {

     int x,y,f,o,c,next;

 }t[Maxn*Maxn];int len;

 int first[Maxn];

 int mymin(int x,int y) {return x<y?x:y;}

 int mymax(int x,int y) {return x>y?x:y;}

 void ins(int x,int y,int f,int c)

 {

     t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;

     t[len].next=first[x];first[x]=len;t[len].o=len+;

     t[++len].x=y;t[len].y=x;t[len].f=;t[len].c=-c;

     t[len].next=first[y];first[y]=len;t[len].o=len-;

 }

 int st,ed;

 queue<int > q;

 int dis[Maxn],pre[Maxn],flow[Maxn];

 bool inq[Maxn];

 bool bfs()

 {

     while(!q.empty()) q.pop();

     // memset(dis,-1,sizeof(dis));

     for(int i=;i<=ed;i++) dis[i]=-INF;

     memset(inq,,sizeof(inq));

     q.push(st);dis[st]=;flow[st]=INF;inq[st]=;

     while(!q.empty())

     {

         int x=q.front();

         for(int i=first[x];i;i=t[i].next) if(t[i].f>)

         {

             int y=t[i].y;

             if(dis[y]<dis[x]+t[i].c)

             {

                 dis[y]=dis[x]+t[i].c;

                 pre[y]=i;

                 flow[y]=mymin(flow[x],t[i].f);

                 if(!inq[y])

                 {

                     inq[y]=;

                     q.push(y);

                 }

             }

         }

         inq[x]=;q.pop();

     }

     if(dis[ed]>-INF) return ;

     return ;

 }

 void output()

 {

     for(int i=;i<=len;i++) if(t[i].f!=&&(t[i].x==||t[i].x==||t[i].x==))

      printf("%d->%d %d %d\n",t[i].x,t[i].y,t[i].f,t[i].c);

     printf("\n");

 }

 int max_flow()

 {

     int ans=,sum=;

     while(bfs())

     {

         sum+=dis[ed]*flow[ed];

         ans+=flow[ed];

         int now=ed;

         while(now!=st)

         {

             t[pre[now]].f-=flow[ed];

             t[t[pre[now]].o].f+=flow[ed];

             now=t[pre[now]].x;

         }

     }

     return sum;

 }

 int num[Maxn][Maxn],n,m,cnt;

 void init()

 {

     int a,b;

     scanf("%d%d",&a,&b);

     scanf("%d%d",&n,&m);

     len=;cnt=;

     memset(first,,sizeof(first));

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++) num[i][j]=++cnt;

     st=cnt+;ed=st+;

     for(int i=;i<=n;i++)

      for(int j=;j<m;j++)

      {

          int x;

          scanf("%d",&x);

          ins(num[i][j],num[i][j+],,x);

          ins(num[i][j],num[i][j+],INF,);

      }

     for(int j=;j<=m;j++)

      for(int i=;i<n;i++)

      {

          int x;

          scanf("%d",&x);

          ins(num[i][j],num[i+][j],,x);

          ins(num[i][j],num[i+][j],INF,);

      }

     for(int i=;i<=a;i++)

     {

         int k,x,y;

         scanf("%d%d%d",&k,&x,&y);

         ins(st,num[x][y],k,);

     }

     for(int i=;i<=b;i++)

     {

         int k,x,y;

         scanf("%d%d%d",&k,&x,&y);

         ins(num[x][y],ed,k,);

     }

 }

 int main()

 {

     init();

     int ans;

     ans=max_flow();

     printf("%d\n",ans);

     return ;

 }

2016-11-07 20:15:40