【题意】

　　深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器

人。 潜艇到达深海海底后， 深海机器人将离开潜艇向预定目标移动。 深海机器人在移动中还

必须沿途采集海底生物标本。 沿途生物标本由最先遇到它的深海机器人完成采集。 每条预定

路径上的生物标本的价值是已知的， 而且生物标本只能被采集一次。 本题限定深海机器人只

能从其出发位置沿着向北或向东的方向移动， 而且多个深海机器人可以在同一时间占据同一

位置。

输入文件示例

input.txt

1 1

2 2

1 2

3 4

5 6

7 2

8 10

9 3

2 0 0

2 2 2

输出文件示例

output.txt

42

 

 

 

【分析】

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

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

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 #define Maxn 1010 10 #define INF 0xfffffff 11 12 struct node 13 { 14 int x,y,f,o,c,next; 15 }t[Maxn*Maxn];int len; 16 int first[Maxn]; 17 18 int mymin(int x,int y) { return x
             
              y?x:y;} 20 21 void ins(int x,int y,int f,int c) 22 { 23 t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c; 24 t[len].next=first[x];first[x]=len;t[len].o=len+1; 25 t[++len].x=y;t[len].y=x;t[len].f=0;t[len].c=-c; 26 t[len].next=first[y];first[y]=len;t[len].o=len-1; 27 } 28 29 int st,ed; 30 queue
              
                q; 31 int dis[Maxn],pre[Maxn],flow[Maxn]; 32 bool inq[Maxn]; 33 bool bfs() 34 { 35 while(!q.empty()) q.pop(); 36 // memset(dis,-1,sizeof(dis)); 37 for(int i=1;i<=ed;i++) dis[i]=-INF; 38 memset(inq,0,sizeof(inq)); 39 q.push(st);dis[st]=0;flow[st]=INF;inq[st]=1; 40 while(!q.empty()) 41 { 42 int x=q.front(); 43 for(int i=first[x];i;i=t[i].next) if(t[i].f>0) 44 { 45 int y=t[i].y; 46 if(dis[y]
               
                -INF) return 1; 61 return 0; 62 } 63 64 void output() 65 { 66 for(int i=1;i<=len;i++) if(t[i].f!=0&&(t[i].x==29||t[i].x==44||t[i].x==30)) 67 printf("%d->%d %d %d\n",t[i].x,t[i].y,t[i].f,t[i].c); 68 printf("\n"); 69 } 70 71 int max_flow() 72 { 73 int ans=0,sum=0; 74 while(bfs()) 75 { 76 sum+=dis[ed]*flow[ed]; 77 ans+=flow[ed]; 78 int now=ed; 79 while(now!=st) 80 { 81 t[pre[now]].f-=flow[ed]; 82 t[t[pre[now]].o].f+=flow[ed]; 83 now=t[pre[now]].x; 84 } 85 } 86 return sum; 87 } 88 89 int num[Maxn][Maxn],n,m,cnt; 90 91 void init() 92 { 93 int a,b; 94 scanf("%d%d",&a,&b); 95 scanf("%d%d",&n,&m); 96 len=0;cnt=0; 97 memset(first,0,sizeof(first)); 98 for(int i=0;i<=n;i++) 99 for(int j=0;j<=m;j++) num[i][j]=++cnt;100 st=cnt+1;ed=st+1;101 for(int i=0;i<=n;i++)102 for(int j=0;j
               
              
             
            
           
          
         
        
       
      

 

 

2016-11-07 20:15:40