深海机器人问题

题目描述

题解：

最大费用最大流。

建图很简单，就是将机器人作为流，进入就从$S$向内流，出来就从图向$T$流。

代码：

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 300 #define ll long long const int inf = 0x3f3f3f3f; const ll Inf = 0x3f3f3f3f3f3f3f3fll; inline int rd() {int f=1,c=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}return f*c; } int a,b,P,Q,S,T,hed[N],cnt=-1; int _id(int x,int y){return x*(Q+1)+y;} struct EG {int to,nxt;ll w,c; }e[10*N]; void ae(int f,int t,ll w,ll c) {e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;e[cnt].c = c;hed[f] = cnt; } queue<int>q; ll dis[N],fl[N]; int pre[N],fa[N]; bool vis[N]; bool spfa() {memset(dis,0x3f,sizeof(dis));dis[S] = 0,fl[S] = Inf,vis[S] = 1;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int j=hed[u];~j;j=e[j].nxt){int to = e[j].to;if(e[j].w&&dis[to]>dis[u]+e[j].c){dis[to] = dis[u]+e[j].c;fl[to] = min(fl[u],e[j].w);pre[to] = j,fa[to] = u;if(!vis[to]){vis[to] = 1;q.push(to);}}}vis[u] = 0;}return dis[T]!=Inf; } ll mcmf() {ll ret = 0;while(spfa()){ret+=fl[T]*dis[T];int u = T;while(u!=S){e[pre[u]].w-=fl[T];e[pre[u]^1].w+=fl[T];u=fa[u];}}return ret; } int main() {a = rd(),b = rd(),P = rd(),Q = rd();memset(hed,-1,sizeof(hed));for(int i=0;i<=P;i++)for(int c,j=0;j<Q;j++){int f = _id(i,j);int t = _id(i,j+1);c = rd();ae(f,t,1,-c);ae(t,f,0,c);ae(f,t,Inf,0);ae(t,f,0,0);}for(int i=0;i<=Q;i++)for(int c,j=0;j<P;j++){int f = _id(j,i);int t = _id(j+1,i);c = rd();ae(f,t,1,-c);ae(t,f,0,c);ae(f,t,Inf,0);ae(t,f,0,0); }S = _id(P,Q)+1,T = S+1;for(int w,x,y,i=1;i<=a;i++){w = rd(),x = rd(),y = rd();int t = _id(x,y);ae(S,t,w,0);ae(t,S,0,0);}for(int w,x,y,i=1;i<=b;i++){w = rd(),x = rd(),y = rd();int f = _id(x,y);ae(f,T,w,0);ae(T,f,0,0);}printf("%lld\n",-mcmf());return 0; }

 

转载于:https://www.cnblogs.com/LiGuanlin1124/p/10255940.html

总结

以上是生活随笔为你收集整理的深海机器人问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。