（2019 CCPC 秦皇岛）E - Escape

本文主要是介绍（2019 CCPC 秦皇岛）E - Escape，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解：这个题如果能想到每个机器人的路径都不是相同的那就很好解决了，因为在一个地方只能有一种转向的选择嘛。然后将一个点拆点四个方向就行了，（不过我交了网上几个代码都wa了，emmm

#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data) memset(_data,0,sizeof(_data))
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e5+5;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
struct edge {int to, cap, rev;
};
vector<edge> eg[N];
int dep[N],arc[N],s,t,n,m,a,b,base;
il void init(){for(int i=s;i<=t;++i) eg[i].clear();
}
il int hs(int x,int y){return x*m+y;
}
il void add(int f,int t,int w) {eg[f].pb(edge {t,w,(int)eg[t].size()});eg[t].pb(edge {f,0,(int)eg[f].size()-1});
}
il void bfs(int s) {memset(dep,-1,sizeof(dep));queue<int>q;q.push(s);dep[s]=0;int v;while(!q.empty()) {v=q.front();q.pop();for (int i=0; i<(int)eg[v].size(); ++i) {edge &e=eg[v][i];if (e.cap>0 && dep[e.to]==-1) {dep[e.to]=dep[v]+1;q.push(e.to);}}}
}
il int dfs(int v,int t,int f) {if(v==t) 	return f;int d;for(int &i=arc[v]; i<(int)eg[v].size(); ++i) {edge &e=eg[v][i];if (e.cap>0 && dep[v]+1==dep[e.to]) {d=dfs(e.to,t,min(f, e.cap));if (d>0) {e.cap -= d;eg[e.to][e.rev].cap+=d;return d;}}}return 0;
}
il int dinic(int s,int t) {int flow = 0,d;while(1) {bfs(s);if (dep[t]==-1)	return flow;memset(arc,0,sizeof(arc));while ((d=dfs(s,t,inf))>0) {flow+=d;}}
}
char mp[105][105];
int main() {int T;read(T);while(T--){read(n),read(m),read(a),read(b);s=0,base=(n+2)*(m+2),t=2*base;init();for(int i=1;i<=n;++i){scanf("%s",mp[i]+1);}int x;for(int i=1;i<=a;++i){read(x);add(s,hs(1,x),1);}for(int i=1;i<=b;++i){read(x);add(hs(n+1,x),t,1);}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(mp[i][j]=='0'){if(i-1>=1) add(hs(i,j),hs(i-1,j),1);if(i+1<=n) add(hs(i,j),hs(i+1,j),1);if(j-1>=1) add(hs(i,j)+base,hs(i,j-1)+base,1);if(j+1<=m) add(hs(i,j)+base,hs(i,j+1)+base,1);if(i+1==n+1) add(hs(i,j),hs(i+1,j),1);add(hs(i,j),hs(i,j)+base,1);add(hs(i,j)+base,hs(i,j),1);}}}if(dinic(s,t)==a) printf("Yes\n");else printf("No\n");}return 0;
}

 

这篇关于（2019 CCPC 秦皇岛）E - Escape的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---