\u9996\u5148\u662f\u4e00\u4e2a\u5e38\u89c1\u5957\u8def\uff1a\u5c06\u68cb\u5b50\u7684\u4ea4\u6362\u7b49\u4ef7\u4e3a\u68cb\u5b50\u7684\u79fb\u52a8\u2014\u2014\u8fd9\u5f88\u91cd\u8981\u3002\u6211\u4eec\u4e0d\u59a8\u628a\u4ea4\u6362\u770b\u505a\u9ed1\u5b50\u7684\u79fb\u52a8\u3002
\n\u90a3\u4e48\u6211\u4eec\u8003\u8651\u8fd9\u4e2a\u95ee\u9898\u7684\u5f31\u5316\u7248\uff1a\u5047\u8bbe\u6bcf\u4e2a\u683c\u5b50\u7684\u79fb\u52a8\u6b21\u6570\u6ca1\u6709\u9650\u5236\uff0c\u8be5\u600e\u4e48\u505a\u3002
\n\u5f88\u663e\u7136\u5c06\u6bcf\u4e2a\u683c\u5b50\u62c6\u6210\u4e24\u4e2a\u70b9\uff0c\u7136\u540e\u6bcf\u4e2a\u53f3\u70b9\u5411\u76f8\u90bb\u7684\u5de6\u70b9\u8fde\u8fb9\uff0c\u8dd1\u6700\u5927\u6d41\u5373\u53ef\u3002
\n\u5bf9\u4e8e\u4e00\u4e2a\u9ed1\u5b50\u7684\u79fb\u52a8\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u5982\u679c\u4e00\u4e2a\u683c\u5b50\u662f\u8fd9\u4e2a\u9ed1\u5b50\u4e2d\u9014\u7ecf\u8fc7\u7684\u70b9\uff0c\u90a3\u4e48\u8fd9\u4e2a\u683c\u5b50\u5fc5\u7136\u4f1a\u6d88\u8017\u4e24\u6b21\u4ea4\u6362\u6b21\u6570\u3002
\n\u6545\u800c\uff0c\u6211\u4eec\u7ed9\u4ece\u5de6\u70b9\u5230\u53f3\u70b9\u7684\u8fb9\u8bbe\u7f6e\u4e00\u4e2a\u5bb9\u91cf\u4e0a\u9650\uff0c\u5176\u503c\u4e3a\u4ea4\u6362\u6b21\u6570\u4e0a\u9650\u7684\u4e00\u534a\u3002
\n\u4f46\u662f\u8fd9\u4e48\u505a\u7684\u8bdd\u6211\u4eec\u53d1\u73b0\u4e86\u4e00\u4e2a\u95ee\u9898\uff1a\u5018\u82e5\u4e00\u4e2a\u70b9\u8d77\u59cb\u72b6\u6001\u548c\u7ed3\u675f\u72b6\u6001\u4e0d\u4e00\u6837\uff0c\u8fd9\u4e2a\u6a21\u578b\u662f\u65e0\u6cd5\u6709\u6548\u63cf\u8ff0\u7ed3\u679c\u7684\u3002
\n\u8fd9\u662f\u56e0\u4e3a\uff0c\u5982\u679c\u4e00\u4e2a\u70b9\u7684\u8d77\u59cb\u72b6\u6001\u548c\u7ed3\u675f\u72b6\u6001\u4e0d\u4e00\u6837\uff0c\u90a3\u4e48\u5b83\u901a\u8fc7\u7684\u6b21\u6570\u5fc5\u7136\u662f\u5947\u6570\u3002
\n\u6211\u4eec\u8003\u8651\u8fd9\u6837\u62c6\u70b9\uff1a\u5c06\u6bcf\u4e2a\u70b9\u62c6\u6210\u5de6\uff0c\u4e2d\uff0c\u53f3\u4e09\u4e2a\u70b9\u3002\u7136\u540e\uff0c\u5c06\u6bcf\u4e2a\u70b9\u7684\u53f3\u70b9\u5411\u5b83\u7684\u6240\u6709\u76f8\u90bb\u70b9\u7684\u5de6\u70b9\u8fde\u8fb9\uff0c\u6d41\u91cf1\uff0c\u8d39\u75280\u3002\u8868\u793a\u67d0\u4e2a\u68cb\u5b50\u8d70\u5411\u4e86\u5b83\u7684\u53e6\u4e00\u4e2a\u76f8\u90bb\u7684\u68cb\u5b50\u3002
\n\u4ece\u4e2d\u70b9\u5411\u53f3\u70b9\u8fde\u4e00\u6761\u8fb9\uff0c\u8868\u793a\u8fd9\u4e2a\u70b9\u79fb\u51fa\u53bb\u7684\u6b21\u6570\u3002\u663e\u7136\uff0c\u5982\u679c\u6700\u7ec8\u60c5\u51b5\u662f\u767d\u7684\u800c\u521d\u59cb\u60c5\u51b5\u662f\u9ed1\u7684\uff0c\u8fd9\u4e2a\u70b9\u5e94\u8be5\u4f1a\u591a\u79fb\u51fa\u53bb\u4e00\u6b21\u3002
\n\u4ece\u5de6\u70b9\u5411\u4e2d\u70b9\u8fde\u4e00\u6761\u8fb9\uff0c\u8868\u793a\u8fd9\u4e2a\u70b9\u79fb\u8fdb\u6765\u7684\u6b21\u6570\u3002\u663e\u7136\uff0c\u5982\u679c\u6700\u7ec8\u60c5\u51b5\u662f\u9ed1\u7684\u800c\u521d\u59cb\u60c5\u51b5\u662f\u767d\u7684\uff0c\u8fd9\u4e2a\u70b9\u5e94\u8be5\u4f1a\u591a\u79fb\u8fdb\u6765\u4e00\u6b21\u3002
\n\u6211\u4eec\u8003\u8651\u8fd9\u4e2a\u300c\u591a\u79fb\u8fdb\u6765\u300d\u548c\u300c\u591a\u79fb\u51fa\u53bb\u300d\u5bf9\u8fd9\u4e2a\u70b9\u53ef\u4ee5\u53c2\u4e0e\u7684\u4ea4\u6362\u6b21\u6570\u7684\u5f71\u54cd\u3002
\n\u5047\u82e5\u9650\u5b9a\u6b21\u6570\u662f\u5076\u6570\uff0c\u90a3\u4e48\u591a\u51fa\u6765\u7684\u8fd9\u4e00\u6b21\u79fb\u52a8\u5c06\u4f7f\u5f97\u8fd9\u4e2a\u70b9\u80fd\u53c2\u4e0e\u7684\u4ea4\u6362\u6b21\u6570\u5c11\u4e00\u6b21\uff1b\u5018\u82e5\u9650\u5b9a\u6b21\u6570\u662f\u5947\u6570\uff0c\u90a3\u4e48\u591a\u51fa\u6765\u7684\u8fd9\u4e00\u6b21\u79fb\u52a8\u5c06\u4e0d\u5f71\u54cd\u8fd9\u4e2a\u70b9\u80fd\u53c2\u4e0e\u7684\u4ea4\u6362\u6b21\u6570\u3002
\n\u6240\u4ee5\uff0c\u6211\u4eec\u53ef\u4ee5\u7528\u5f62\u5982\\(\\lfloor \\frac{limit+[end>begin]}{2} \\rfloor \\)\u548c\\(\\lfloor \\frac{limit+[begin>end]}{2} \\rfloor \\)\u7684\u5f0f\u5b50\u6765\u63cf\u8ff0\u8fd9\u4e24\u6761\u8fb9\u7684\u6d41\u91cf\u3002
\n\u7136\u540e\uff0c\u5bf9\u4e8e\u9898\u76ee\u8981\u6c42\u7684\u6700\u5c0f\u4ea4\u6362\u6b21\u6570\uff0c\u6211\u4eec\u8003\u8651\u5c06\u539f\u6765\u5c31\u5b58\u5728\u7684\u8fde\u8fb9\u52a0\u4e0a\u8d39\u7528\u3002\u8fd9\u6837\u5c31\u6ee1\u8db3\u4e86\u9898\u76ee\u7684\u8981\u6c42\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<queue>\n\nconst int dx[8]={-1,-1,-1,0,0,1,1,1};\nconst int dy[8]={1,0,-1,1,-1,1,0,-1};\n\nconst int INF = 0x3f3f3f3f;\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint c;\n\tint nxt;\n}e[200005];\nint h[1205],et=-1;\ninline void Eadd(int U,int V,int W,int C){\n\te[++et]=(ee){V,W,C,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V,int W,int C){\n\tEadd(U,V,W,C);\n\tEadd(V,U,0,-C);\n}\n\nint n,m,s,t,vis[1205],dis[1205],val[1205],fa[1205],nw[1205];\n\nstd::queue<int> q;\ninline bool SPFA(){\n\tfor(int i=1;i<=t;++i){\n\t\tvis[i]=0,dis[i]=INF,val[i]=INF;\n\t}\n\tvis[s]=1,dis[s]=0,fa[t]=-1;\n\tq.push(s);\n\tint p;\n\twhile(!q.empty()){\n\t\tp=q.front();\n\t\tq.pop();\n\t\tvis[p]=0;\n\t\tfor(int i=h[p];i>=0;i=e[i].nxt){\n\t\t\tif(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){\n\t\t\t\tdis[e[i].v]=dis[p]+e[i].c;\n\t\t\t\tfa[e[i].v]=p;\n\t\t\t\tnw[e[i].v]=i;\n\t\t\t\tval[e[i].v]=Min(e[i].w,val[p]);\n\t\t\t\tif(!vis[e[i].v]){\n\t\t\t\t\tvis[e[i].v]=1;\n\t\t\t\t\tq.push(e[i].v);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn fa[t]!=-1;\n}\nint answ=0,ansc=0;\ninline void zkw(){\n\tint p;\n\twhile(SPFA()){\n\t\tp=t;\n\t\tansw+=val[t];\n\t\tansc+=val[t]*dis[t];\n\t\twhile(p!=s){\n\t\t\te[nw[p]].w-=val[t];\n\t\t\te[nw[p]^1].w+=val[t];\n\t\t\tp=fa[p];\n\t\t}\n\t}\n}\n\nchar begin[25][25],end[25][25],limit[25][25];\ninline int calc(int X,int Y,int T){\n\treturn T*n*m+(X-1)*m+Y;\n}\n\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\ts=3*n*m+1,t=3*n*m+2;\n\tint cnt=0;\n\tfor(int i=1;i<=t;++i){\n\t\th[i]=-1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tstd::cin>>begin[i]+1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tstd::cin>>end[i]+1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tstd::cin>>limit[i]+1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tfor(int j=1;j<=m;++j){\n\t\t\tif(begin[i][j]=='1'){\n\t\t\t\t++cnt;\n\t\t\t\tadd(s,calc(i,j,1),1,0);\n\t\t\t}\n\t\t\tadd(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);\n\t\t\tif(end[i][j]=='1'){\n\t\t\t\tadd(calc(i,j,1),t,1,0);\n\t\t\t}\n\t\t\tadd(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);\n\t\t\tfor(int k=0;k<8;++k){\n\t\t\t\tint x=i+dx[k],y=j+dy[k];\n\t\t\t\tif(x>=1&&x<=n&&y>=1&&y<=m){\n\t\t\t\t\t\/\/n,m!!!\n\t\t\t\t\tadd(calc(i,j,2),calc(x,y,0),INF,0);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tzkw();\n\tprintf(\"%d\\n\",(answ==cnt?ansc:-1)>>1);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9996\u5148\u662f\u4e00\u4e2a\u5e38\u89c1\u5957\u8def\uff1a\u5c06\u68cb\u5b50\u7684\u4ea4\u6362\u7b49\u4ef7\u4e3a\u68cb\u5b50\u7684\u79fb\u52a8\u2014\u2014\u8fd9\u5f88\u91cd\u8981\u3002\u6211\u4eec\u4e0d\u59a8\u628a\u4ea4\u6362\u770b\u505a\u9ed1\u5b50\u7684\u79fb\u52a8\u3002 \u90a3\u4e48\u6211\u4eec\u8003\u8651\u8fd9\u4e2a … <\/p>\n