「BZOJ2132」圈地计划
Description
最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益，即如果区域(I,j)相邻（相邻是指两个格子有公共边）有K块（显然K不超过4）类型不同于(I,j)的区域，则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察，收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么？
Input
输入第一行为两个整数，分别为正整数N和M，分别表示区域的行数和列数；第2到N+1列，每行M个整数，表示商业区收益矩阵A；第N+2到2N+1列，每行M个整数，表示工业区收益矩阵B；第2N+2到3N+1行，每行M个整数，表示相邻额外收益矩阵C。第一行，两个整数，分别是n和m（1≤n，m≤100）；
Output
输出只有一行，包含一个整数，为最大收益值。
Sample Input
3 3
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
1 1 1
1 3 1
1 1 1
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
1 1 1
1 3 1
1 1 1
Sample Output
81
「数据规模」
对于100%的数据有N,M≤100
「数据规模」
对于100%的数据有N,M≤100
题解
黑白染色，对于每个黑点A，S->A:W商业，A->T:W工业，
对于每个白点B，S->B:W工业，B->T:W商业，对于每对有关系的两点A，B，A<–>B:c1+c2。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstring> #include<cstdio> #define T 10001 #define inf 0x7fffffff #define FOR for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) using namespace std; int n,m,cnt=1,tot,ans,head[10001],h[10002]; int a[101][101],b[101][101],c[101][101]; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; bool color[101][101]; struct data{int to,next,v;}e[100001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {tot+=w;ins(u,v,w);ins(v,u,0);} bool bfs() { int q[10005],t=0,w=1,i,now; memset(h,-1,sizeof(h)); q[0]=h[0]=0; while(t!=w) { now=q[t];t++;if(t==10001)t=0; for(i=head[now];i;i=e[i].next) { if(e[i].v&&h[e[i].to]<0) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==10001)w=0;} } } if(h[T]==-1)return 0;return 1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=head[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } } if(!used)h[x]=-1; return used; } void dinic(){while(bfs())ans+=dfs(0,inf);} void build() { FOR{ if(color[i][j])swap(a[i][j],b[i][j]); insert(0,(i-1)*m+j,a[i][j]); insert((i-1)*m+j,T,b[i][j]); if(color[i][j]) for(int k=0;k<4;k++) { int nowx=i+xx[k],nowy=j+yy[k]; if(nowx>n||nowy>m||nowx<1||nowy<1)continue; ins((i-1)*m+j,(nowx-1)*m+nowy,c[i][j]+c[nowx][nowy]); ins((nowx-1)*m+nowy,(i-1)*m+j,c[i][j]+c[nowx][nowy]); tot+=(c[i][j]+c[nowx][nowy]); } } } int main() { scanf("%d%d",&n,&m); FOR scanf("%d",&a[i][j]); FOR scanf("%d",&b[i][j]); FOR scanf("%d",&c[i][j]); FOR if((i+j)&1)color[i][j]=1; build();dinic(); printf("%d",tot-ans); return 0; } |
Subscribe
计数器 9787238
OI 课件=>
OI 课件=>