Pool construction Time Limit: 3000MS 64bit IO Format: %lld & %llu
这道题可以用最小割来求解。 首先定义与S连通的是草，与T连通的是洞，那么需要切掉某些边使得S与T不连通，也就是要求最小割。 那么把S与原图所有草连上一条容量d的边，代表要把这个格子变成洞需要花费d的费用，同样所有洞与T连边。 然后对于任意两个相邻的格子，连边 u->v v->u 容量都为b，分别代表如果u是草v是洞，v是草u是洞秀栅栏的费用（这样才能保证S与T不连通）。这样就用最大流求最小割即可。 注意原题要求最外圈必须是草，那么需要把这些S到草的容量改成INF，表示不能切这条边，然后预先求出把最外围洞改成草所需费用，最后加上就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> using namespace std; const int INF=0x3f3f3f3f; const int mx=300; const int maxn=mx*mx+5; const int dx[]={0,-1,1,0,0}; const int dy[]={0,0,0,-1,1}; struct Edge { int to,next; int cap; }edge[maxn<<3];//maxn*4*2 int head[maxn]; int maxedge; inline void addedge(int u,int v,int cap) { edge[++maxedge]=(Edge){v,head[u],cap}; head[u]=maxedge; edge[++maxedge]=(Edge){u,head[v],0}; head[v]=maxedge; } int dig,fil,build,m,n,add; bool g[mx+5][mx+5]; int S,T; inline int id(int i,int j) { return (i-1)*n+j; } inline bool ingraph(int i,int j) { if(i>=1&&i<=m&&j>=1&&j<=n) return true; else return false; } inline int change(int i,int j) { int u=id(i,j); if(!g[i][j]) add+=fil,g[i][j]=true; addedge(S,u,INF); } inline void init() { memset(g,false,sizeof(g)); add=0; scanf("%d%d%d%d%d",&n,&m,&dig,&fil,&build);//m*n getchar(); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { char c=getchar(); if(c=='#') g[i][j]=true; } getchar(); } memset(head,-1,sizeof(head)); maxedge=-1;S=m*n+1,T=S+1;//order at here!!! before addedge!! for(int i=1;i<=m;i++) { change(i,1);change(i,n); } for(int i=2;i<n;i++) { change(1,i);change(m,i); } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { int u=id(i,j); for(int k=1;k<=4;k++) { if(!ingraph(i+dx[k],j+dy[k])) continue; int v=id(i+dx[k],j+dy[k]); addedge(u,v,build); } if(i==1||i==m||j==1||j==n) continue; if(g[i][j]) addedge(S,u,dig); else addedge(u,T,fil); } } int cur[maxn],d[maxn]; bool vis[maxn]; inline bool bfs() { queue <int> que; memset(vis,false,sizeof(vis)); que.push(S);d[S]=1;vis[S]=true; while(!que.empty()) { int u=que.front();que.pop(); for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(!edge[i].cap||vis[v]) continue; d[v]=d[u]+1; if(v==T) return true; vis[v]=true;que.push(v); } } return false; } int dfs(int u,int minflow) { if(u==T||!minflow) return minflow; int flow=0; for(int &i=cur[u];~i;i=edge[i].next) { int v=edge[i].to,f; if(d[v]==d[u]+1&&(f=dfs(v,min(minflow,edge[i].cap)))) { edge[i].cap-=f;edge[i^1].cap+=f; flow+=f;minflow-=f; if(!minflow) break; } } return flow; } inline int dinic() { int ret=0; while(bfs()) { memcpy(cur,head,sizeof(head)); ret+=dfs(S,INF); } return ret; } int main() { freopen("pool.in","r",stdin); freopen("pool.out","w",stdout); int cas; scanf("%d",&cas); while(cas--) { init(); printf("%d\n",dinic()+add); } return 0; }