BJ模拟：Mr. Panda and Tube Master（费用流）

传送门

题解：
考虑黑白染色，把原来的点拆为两个点，令黑点左右连边，白点上下连边做最大匹配。 如果不是必需点，则自己和自己连边。

显然任意合法方案都对应着一组匹配，而任意一组匹配都可以还原出一个方案。 我们做最大费用最大流即可。

#include  
using namespace std;
inline int rd(int x=0) {return (scanf("%d",&x),x);}
const int N=1e3+50,M=2e5+50,L=25,INF=0x3f3f3f3f;
int n,m,src,des,cx[L][L],cy[L][L],ms[L][L],gg; queue <int> q;
int g[N],nt[M],vt[M],c[M],w[M],ec,dis[M],vis[M],exi[M],vs,cur[N];
inline int id(int x,int y,int t) {return (x-1)*m+y+(t==2)*n*m;}
inline void init()  {memset(g+1,0,sizeof(int)*des); ec=1; gg=0;}
inline void add(int x,int y,int cc,int ww) {nt[++ec]=g[x]; g[x]=ec; vt[ec]=y; c[ec]=cc; w[ec]=ww;nt[++ec]=g[y]; g[y]=ec; vt[ec]=x; c[ec]=0; w[ec]=-ww;
}
inline bool spfa() {for(int i=1;i<=des;i++) dis[i]=-INF;q.push(src); dis[src]=0;while(!q.empty()) {int u=q.front(); q.pop(); exi[u]=0;for(int e=g[u];e;e=nt[e]) {if(!c[e] || dis[vt[e]]>=dis[u]+w[e]) continue;dis[vt[e]]=dis[u]+w[e]; if(!exi[vt[e]]) exi[vt[e]]=1, q.push(vt[e]);}} return dis[des]>-INF;
}
inline int dinic(int x,int f,int cost) {if(x==des) {gg+=cost*f; return f;}int rs=0; vis[x]=vs;for(int &e=cur[x];e;e=nt[e]) {if(!c[e] || vis[vt[e]]==vs || (dis[vt[e]]!=dis[x]+w[e])) continue;int o=dinic(vt[e],min(f-rs,c[e]),cost+w[e]);rs+=o; c[e]-=o; c[e^1]+=o;if(rs==f) return rs;} return dis[x]=-INF, rs;
}
inline int maxflow() {int rs=0;while(spfa()) {int t; ++vs, memcpy(cur+1,g+1,sizeof(int)*des);while((t=dinic(src,INF,0))) rs+=t, ++vs, memcpy(cur+1,g+1,sizeof(int)*des);} return rs;
}
inline void solve() {n=rd(), m=rd(), src=id(n,m,2)+1; des=src+1; init(); memset(ms,0,sizeof(ms));for(int i=1;i<=n;i++) for(int j=1;jfor(int i=1;ifor(int j=1;j<=m;j++) cy[i][j]=rd();for(int i=rd();i>=1;i--) {int x=rd(), y=rd(); ms[x][y]=1;}for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {if((i+j)&1) {if(j>1) add(id(i,j,1),id(i,j-1,2),1,cx[i][j-1]);if(j1),id(i,j+1,2),1,cx[i][j]);} else {if(i>1) add(id(i,j,1),id(i-1,j,2),1,cy[i-1][j]);if(i1),id(i+1,j,2),1,cy[i][j]);}add(src,id(i,j,1),1,0); add(id(i,j,2),des,1,0);if(!ms[i][j]) add(id(i,j,1),id(i,j,2),1,0);}static int tl=0; printf("Case #%d: ",++tl);if(maxflow()==n*m) cout<else cout<<"Impossible"<int main() {for(int i=rd();i;i--) solve();
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！