• [NOI2007] 调兵遣将

    题目描述

    我军截获的情报显示，敌军正在集结兵力试图向我军重要的军械研究所发起进攻。由于我军正处于多线作战的状态，无法抽调大批兵力前去支援，指挥部决定通过有效的战前部署来提高胜率，减少伤亡和损失。

    该军械研究所的平面图可以看作是一个 �×�N×M 的矩阵，每个1×11×1 的格子都表示一个区域，每个区域只与它上下左右的四个区域相邻。每个区域的用途可分为以下3 种之一：

    1． 该区域被用于军事研究（用字母 O 表示）；

    2． 该区域内驻扎有一个机械化中队（用 # 表示）；

    3． 该区域是空地（用.表示）。

    由于空间有限，任一个 1×11×1 的格子内都无法驻扎两队以上的机械化中队（包括两队），否则会大大降低战斗时的机动性。

    遗憾的是，由于战前估计不足，我军的防御部署显得十分分散，这很容易让敌军所擅长的偷袭战术得逞。为了确保万无一失，我军决定利用为数不多的防御部队以最少的移动步骤将所有重要研究区域都包围起来。所谓的“包围”即从该矩阵边界侵入的敌军找不到任意一条路，使得他们不遭受任何机械化中队的反抗就能到达某研究区域。

    由于军队内部的传令权限的限制，每个单位时间指挥部只能向所有中队中的一个中队下达指令（朝上/下/左/右移动 11 格）。由于时间紧迫，指挥部希望能够尽快完成部署，这个任务就交给你来完成。

    注意：在部署的过程中军队可以进入研究区域，而在最终的部署结果中军队不可以在研究区域中。另外，在任何时刻，两个军队都不可以在同一个方格中。

    输入格式

    该题为提交答案型题目。

    对于每个数据：

    第一行 22 个整数 �N,�M，接下来 �N 行，每行包括 �M 个字符（., O或 #）。

    输出格式

    每个输出文件的第一行，包括你的答案所花费的时间 �T。

    接下来 �T 行，按顺序输出每条命令，每行包括 44 个整数 �1,�1,�2,�2x1,y1,x2,y2，表示将位于 (�1,�1)(x1,y1) 的部队移向 (�2,�2)(x2,y2)。

    输入输出样例

    输入 #1复制

    5 5
..##.
#...#
#OOO#
#..O#
.###.

    输出 #1复制

    1
2 1 2 2

    说明/提示

    如果选手的输出方案不合法（方案执行过程中出现军队重叠，军队移出矩形边界，最终方案有军队和研究所在同一区域，军队没有包围研究所等），则得零分，否则设选手输出的方案耗时为ans ，则得分按如下计算：

    对于每个数据，都有两个评分参数 ��Ai​ 与 ��Bi​，其中保证 ��<��Ai​ 

    1. #include
    2. #define int ll
    3. using namespace std;
    4. typedef long long ll;
    5. const int N=105,N2=105,P=3*N*N2+5,M=1e7+5,inf=1e9;
    6. char s[N][N2],ss[N][N2],tt[N][N2];
    7. int n,m;
    8. int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
    9. int que[P],dis[P],h,t,S=P-1,T=P-2;
    10. int bk[P],vis[P];
    11. int ch[N][N2];
    12. int inq[P],a[P],pre[P];
    13. queue<int> q;
    14. int pp,qq;
    15. bool dl[N][N2],Dl[N][N2];
    16. void add(int lu,int lv,int lf,int lw=0)
    17. {
    18. 	u[++tot]=lu,v[tot]=lv,flow[tot]=lf,w[tot]=lw,nxt[tot]=fst[lu],fst[lu]=tot;
    19. 	u[++tot]=lv,v[tot]=lu,flow[tot]=0,w[tot]=-lw,nxt[tot]=fst[lv],fst[lv]=tot;
    20. }
    21. int d(int r,int c,int id) {return (r-1)*m+c+n*m*id;}
    22. bool bfs()
    23. {
    24. 	memset(dis,0x3f,sizeof(dis)),dis[S]=0,que[h=t=1]=S;
    25. 	while(h<=t)
    26. 		for(int i=que[h++],j=fst[i];j;j=nxt[j])
    27. 			if(flow[j]&&dis[v[j]]>dis[i]+1) dis[v[j]]=dis[i]+1,que[++t]=v[j];
    28. 	return dis[T]
    29. }
    30. int dfs(int x,int lw,int tt=T)
    31. {
    32. 	if(x==tt) return lw;
    33. 	int res=0,zl;
    34. 	for(int &i=cur[x];i;i=nxt[i])
    35. 		if(flow[i]&&dis[v[i]]==dis[x]+1&&(zl=dfs(v[i],min(lw,flow[i]),tt)))
    36. 		{
    37. 			lw-=zl,flow[i]-=zl,res+=zl,flow[i^1]+=zl;
    38. 			if(!lw) return res;
    39. 		}
    40. 	return res;
    41. }
    42. int dinic() {int res=0; while(bfs()) memcpy(cur,fst,sizeof(cur)),res+=dfs(S,inf); return res;}
    43. void bfs(int x)
    44. {
    45. 	bk[x]=1;
    46. 	for(int i=fst[x];i;i=nxt[i])
    47. 		if(!bk[v[i]]&&flow[i]) bfs(v[i]);
    48. }
    49. bool ade()
    50. {
    51. 	int i,j;
    52. 	memset(fst,0,sizeof(fst)),tot=1;
    53. 	for(i=1;i<=n;i++)
    54. 		for(j=1;j<=m;j++)
    55. 		{
    56. 			if(s[i][j]!='#'||dl[i][j]) add(d(i,j,0),d(i,j,1),s[i][j]!='O'? 1:inf);
    57. 			iadd(d(i,j,1),d(i+1,j,0),inf),add(d(i+1,j,1),d(i,j,0),inf),0),
    58. 			jadd(d(i,j,1),d(i,j+1,0),inf),add(d(i,j+1,1),d(i,j,0),inf),0),
    59. 			s[i][j]=='O'&&(add(S,d(i,j,0),inf),0);
    60. 		}
    61. 	for(i=1;i<=n;i++) add(d(i,1,1),T,inf),add(d(i,m,1),T,inf);
    62. 	for(i=2;iadd(d(1,i,1),T,inf),add(d(n,i,1),T,inf);
    63. 	int R=dinic();
    64. 	if(R>=inf) return memset(fst,0,sizeof(fst)),tot=1,0;
    65. 	memset(bk,0,sizeof(bk)),bfs(S);
    66. 	for(i=1;i<=n;i++)
    67. 		for(j=1;j<=m;j++)
    68. 			if(bk[d(i,j,0)]&&!bk[d(i,j,1)]) ch[i][j]=1;
    69. 			else ch[i][j]=0;
    70. 	memset(fst,0,sizeof(fst)),tot=1;
    71. 	return 1;
    72. }
    73. int vs[N][N];
    74. void adeg(int r,int c,int sr,int sc)
    75. {
    76. 	vs[r][c]=d(sr,sc,0);
    77. 	if(ch[r][c]) add(d(sr,sc,0),d(r,c,1),1,abs(sr-r)+abs(sc-c));
    78. 	if(abs(r-sr)+abs(c-sc)>10) return;
    79. 	if(c1]!=d(sr,sc,0)) adeg(r,c+1,sr,sc);
    80. 	if(c>1&&vs[r][c-1]!=d(sr,sc,0)) adeg(r,c-1,sr,sc);
    81. 	if(r1][c]!=d(sr,sc,0)) adeg(r+1,c,sr,sc);
    82. 	if(r>1&&vs[r-1][c]!=d(sr,sc,0)) adeg(r-1,c,sr,sc);
    83. }
    84. int res,ans=inf;
    85. bool spfa()
    86. {
    87. 	memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)),q.push(S),dis[S]=0,inq[S]=1,a[S]=inf;
    88. 	while(!q.empty())
    89. 	{
    90. 		int x=q.front(); q.pop(),inq[x]=0;
    91. 		for(int i=fst[x];i;i=nxt[i])
    92. 			if(flow[i]&&dis[v[i]]>dis[x]+w[i])
    93. 				dis[v[i]]=dis[x]+w[i],pre[v[i]]=i,a[v[i]]=min(a[x],flow[i]),!inq[v[i]]&&(q.push(v[i]),inq[v[i]]=1);
    94. 	}
    95. 	if(dis[T]>inf) return 0;
    96. 	res+=dis[T]*a[T],pp+=a[T];
    97. 	for(int i=T;i!=S;i=u[pre[i]]) flow[pre[i]]-=a[T],flow[pre[i]^1]+=a[T];
    98. 	return 1;
    99. }
    100. int Cl;
    101. struct aa
    102. {
    103. 	int x1,y1,x2,y2;
    104. }as[P];
    105. stack st;
    106. #define XX if(ss[x2][y2]=='#') while(!st.empty()) as[++Cl]=st.top(),st.pop();
    107. void walk(int x1,int y1,int x2,int y2)
    108. {
    109. 	if(x1==x2&&y1==y2) return;
    110. 	ss[x2][y2]='#';
    111. 	while(y2>y1) {st.push(aa{x2,y2-1,x2,y2}),y2--;XX}
    112. 	while(x2>x1) {st.push(aa{x2-1,y2,x2,y2}),x2--;XX}
    113. 	while(y2push(aa{x2,y2+1,x2,y2}),y2++;XX}
    114. 	while(x2push(aa{x2+1,y2,x2,y2}),x2++;XX}
    115. 	ss[x1][y1]='.';
    116. }
    117. void cal()
    118. {
    119. 	int i,j,li;
    120. 	if(ade())
    121. 	{
    122. 		pp=qq=0;
    123. 		memset(vs,0,sizeof(vs));
    124. 		for(i=1;i<=n;i++)
    125. 			for(j=1;j<=m;j++)
    126. 				if(s[i][j]=='#'&&!ch[i][j]) adeg(i,j,i,j),add(S,d(i,j,0),1,0);
    127. 		for(i=1;i<=n;i++)
    128. 			for(j=1;j<=m;j++)
    129. 				if(ch[i][j]&&s[i][j]!='#') add(d(i,j,1),T,1,0),qq++;
    130. 		res=0;
    131. 		while(spfa());
    132. 		if(res
    133. 		{
    134. 			ans=res,Cl=0;
    135. 			memcpy(ss,s,sizeof(ss));
    136. 			while(!st.empty()) st.pop();
    137. 			for(i=1;i<=n;i++)
    138. 				for(j=1;j<=m;j++)
    139. 					if(ss[i][j]=='#')
    140. 						for(li=fst[d(i,j,0)];li;li=nxt[li])
    141. 							if(!flow[li]&&v[li]!=S) walk(i,j,(v[li]-n*m-1)/m+1,(v[li]-n*m-1)%m+1);
    142. 			memcpy(tt,ss,sizeof(tt));
    143. 		}
    144. 	}
    145. }
    146. void gt()
    147. {
    148. 	memset(dl,0,sizeof(dl)),cal();
    149. 	cerr<'\n';
    150. 	for(int t=1000;t>1;t*=0.99)
    151. 	{
    152. 		memcpy(Dl,dl,sizeof(Dl));
    153. 		for(int i=1;i<=t;i++)
    154. 		{
    155. 			int la=rand()%n+1,lb=rand()%m+1;
    156. 			dl[la][lb]^=1;
    157. 		}
    158. 		int lp=ans;
    159. 		if(cal(),lp==ans) memcpy(dl,Dl,sizeof(dl));
    160. 		else cerr<'\n';
    161. 	}
    162. }
    163. signed main()
    164. {
    165. 	freopen("surround10.in","r",stdin);
    166. 	freopen("surround0.out","w",stdout);
    167. 	int i,j,li,lj;
    168. 	cin>>n>>m,srand(time(0));
    169. 	for(i=1;i<=n;i++) scanf("%s",s[i]+1);
    170. 	gt();
    171. //	for(i=1,cout<<'\n';i<=n;i++,cout<<'\n')
    172. //		for(j=1;j<=m;j++) cout<
    173. 	cout<'\n';
    174. 	for(i=1;i<=Cl;i++) cout<' '<' '<' '<'\n';
    175. 	return 0;
    176. }

  • 相关阅读:
    【Mybatis 源码】 Mybatis 是如何解析配置文件中的内容 -- settings
    【每日一题】652. 寻找重复的子树
    冬季寒冷，普通空调如何做到智能控制，增温又降耗的？
    WEB逆向—X-Bogus逆向分析(纯算+补环境)
    DataStream（二）
    谢尔平斯基三角形分形 - 产生随机性的最简方法
    Ubuntu 命令行安装 nodejs 并更新
    PHP & MySQL图解学习指南：开启Web开发新篇章
    大疆图像算法面试流程
    Workfine新手入门：日期间隔函数
  • 原文地址：https://blog.csdn.net/SYC20110120/article/details/131143943