题解 P4012 【深海机器人问题】

wjyyy

2019-01-15 18:54:49

Solution

**我的博客:[传送门](https://www.wjyyy.top/3069.html)** ## 题解: 看上去还是一个**“方格取数”类**问题,实际上每个点、每条边是可以经过多次的。我们直接按图上网格建边就可以了,方向是$\rightarrow,\uparrow$。 但是重点是每条边只在第一次被经过时产生收益,这个看来是不好在费用流中进行特判的了。 如果这些边的容量全部设为$l1$,那么一条边就不能被经过第二次了,这当$\sum k+\sum r$很大的时候会存在机器人跑不过去的情况。 如果这些边的容量为$\inf$,那么不容易判断这条边是第几次被经过,而且残量网络也不方便更新。 此时我们可以建两条边,一条是带费用的,容量为$1$,另一条是不带费用的,容量为$\inf$。但是这两条边的优先级怎么确定呢? 由于费用流的特殊性,EK费用流是通过spfa来增广的,当存在上述带费用的边时,会先跑带费用的边(_最大费用最大流中权值实际为负*****_)。此时就既解决了收益最大化问题,也解决了收益单次性问题。 不过像【洛谷 P4001 狼抓兔子[题目](https://www.luogu.org/problemnew/show/P4001),[题解](https://www.wjyyy.top/1540.html)】这一题的建模就更考察思维了。 ***最大费用最大流中把原边权取反(负)跑最短路增广会方便很多,最后答案再取反。** ## Code: ```cpp #include<queue> #include<cstdio> #include<cstring> #define s 290 #define t 291 using std::queue; struct edge { int n,nxt,v,w; edge(int n,int nxt,int v,int w) { this->n=n; this->nxt=nxt; this->v=v; this->w=w; } edge(){} }e[2000]; int head[300],ecnt=-1; void add(int from,int to,int v,int w) { e[++ecnt]=edge(to,head[from],v,w); head[from]=ecnt; e[++ecnt]=edge(from,head[to],0,-w); head[to]=ecnt; } int dis[300],pre[300]; bool used[300]; bool spfa() { memset(dis,0x3f,sizeof(dis)); queue<int> q; q.push(s); used[s]=1; dis[s]=0; while(!q.empty()) { int x=q.front(); q.pop(); used[x]=0; for(int i=head[x];~i;i=e[i].nxt) if(e[i].v&&dis[e[i].n]>dis[x]+e[i].w) { dis[e[i].n]=dis[x]+e[i].w; pre[e[i].n]=i; if(!used[e[i].n]) { used[e[i].n]=1; q.push(e[i].n); } } } return dis[t]!=0x3f3f3f3f; } int main() { memset(head,-1,sizeof(head)); int a,b,n,m,u,v,w; scanf("%d%d%d%d",&a,&b,&n,&m); for(int i=0;i<=n;++i) for(int j=0;j<m;++j) { scanf("%d",&u);//计算一维坐标时需要注意 add(i*(m+1)+j,i*(m+1)+j+1,1,-u);//每一行既有0又有m add(i*(m+1)+j,i*(m+1)+j+1,0x3fffffff,0);//所以有m+1个数 } for(int i=0;i<=m;++i) for(int j=0;j<n;++j) { scanf("%d",&u); add(j*(m+1)+i,(j+1)*(m+1)+i,1,-u); add(j*(m+1)+i,(j+1)*(m+1)+i,0x3fffffff,0); } for(int i=1;i<=a;++i) { scanf("%d%d%d",&u,&v,&w); add(s,v*(m+1)+w,u,0); } for(int i=1;i<=b;++i) { scanf("%d%d%d",&u,&v,&w); add(v*(m+1)+w,t,u,0); } int ans=0; pre[s]=-1; while(spfa()) { int p=pre[t],mn=0x3fffffff; while(~p) { mn=mn<e[p].v?mn:e[p].v; p=pre[e[p^1].n]; } p=pre[t]; while(~p) { e[p].v-=mn; e[p^1].v+=mn; ans+=e[p].w*mn; p=pre[e[p^1].n]; } } printf("%d\n",-ans); return 0; } ```