【NOI2007】 调兵遣将solution
简要方法：爬山+网络流
首先，如果所有士兵不动，整个图是一个二分图，对它做最小割求出哪些位置需要拦住，然后再以士兵为左侧点、需要拦住的位置为右侧点跑费用流，即可求出一个局部最优解。
但是这个解并不一定是最优的，因为最小割并不一定是最优解（费用流跑出来的一定是最优解），所以考虑如何求需要拦住的位置才能使得答案更优。
注意到前面我们是默认所有士兵在的格子已经被拦住后跑的最小割，为了找出其它方案，我们选择一些士兵，然后在跑最小割时忽略这些士兵（即默认他们所在的格子是空地）。
选士兵的方案并没有明确的最优解，因此我们用爬山来解决。
这种方法能通过 1、2、6、7、10 号点，对于 3、4、5、9 号点，忽略所有士兵用上述方法就能通过，对于 8 号点，我们手玩一下，找出哪些空格不能选即可。
代码基本相同：
1、2、6、7、10：
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=105,N2=105,P=3*N*N2+5,M=1e7+5,inf=1e9;
char s[N][N2],ss[N][N2],tt[N][N2];
int n,m;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
bool dl[N][N2],Dl[N][N2];
void add(int lu,int lv,int lf,int lw=0)
{
u[++tot]=lu,v[tot]=lv,flow[tot]=lf,w[tot]=lw,nxt[tot]=fst[lu],fst[lu]=tot;
u[++tot]=lv,v[tot]=lu,flow[tot]=0,w[tot]=-lw,nxt[tot]=fst[lv],fst[lv]=tot;
}
int d(int r,int c,int id) {return (r-1)*m+c+n*m*id;}
bool bfs()
{
memset(dis,0x3f,sizeof(dis)),dis[S]=0,que[h=t=1]=S;
while(h<=t)
for(int i=que[h++],j=fst[i];j;j=nxt[j])
if(flow[j]&&dis[v[j]]>dis[i]+1) dis[v[j]]=dis[i]+1,que[++t]=v[j];
return dis[T]<inf;
}
int dfs(int x,int lw,int tt=T)
{
if(x==tt) return lw;
int res=0,zl;
for(int &i=cur[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]==dis[x]+1&&(zl=dfs(v[i],min(lw,flow[i]),tt)))
{
lw-=zl,flow[i]-=zl,res+=zl,flow[i^1]+=zl;
if(!lw) return res;
}
return res;
}
int dinic() {int res=0; while(bfs()) memcpy(cur,fst,sizeof(cur)),res+=dfs(S,inf); return res;}
void bfs(int x)
{
bk[x]=1;
for(int i=fst[x];i;i=nxt[i])
if(!bk[v[i]]&&flow[i]) bfs(v[i]);
}
bool ade()
{
int i,j;
memset(fst,0,sizeof(fst)),tot=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(s[i][j]!='#'||dl[i][j]) add(d(i,j,0),d(i,j,1),s[i][j]!='O'? 1:inf);
i<n&&(add(d(i,j,1),d(i+1,j,0),inf),add(d(i+1,j,1),d(i,j,0),inf),0),
j<m&&(add(d(i,j,1),d(i,j+1,0),inf),add(d(i,j+1,1),d(i,j,0),inf),0),
s[i][j]=='O'&&(add(S,d(i,j,0),inf),0);
}
for(i=1;i<=n;i++) add(d(i,1,1),T,inf),add(d(i,m,1),T,inf);
for(i=2;i<m;i++) add(d(1,i,1),T,inf),add(d(n,i,1),T,inf);
int R=dinic();
if(R>=inf) return memset(fst,0,sizeof(fst)),tot=1,0;
memset(bk,0,sizeof(bk)),bfs(S);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(bk[d(i,j,0)]&&!bk[d(i,j,1)]) ch[i][j]=1;
else ch[i][j]=0;
memset(fst,0,sizeof(fst)),tot=1;
return 1;
}
int vs[N][N];
void adeg(int r,int c,int sr,int sc)
{
vs[r][c]=d(sr,sc,0);
if(ch[r][c]) add(d(sr,sc,0),d(r,c,1),1,abs(sr-r)+abs(sc-c));
if(abs(r-sr)+abs(c-sc)>10) return;
if(c<m&&vs[r][c+1]!=d(sr,sc,0)) adeg(r,c+1,sr,sc);
if(c>1&&vs[r][c-1]!=d(sr,sc,0)) adeg(r,c-1,sr,sc);
if(r<n&&vs[r+1][c]!=d(sr,sc,0)) adeg(r+1,c,sr,sc);
if(r>1&&vs[r-1][c]!=d(sr,sc,0)) adeg(r-1,c,sr,sc);
}
int res,ans=inf;
bool spfa()
{
memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)),q.push(S),dis[S]=0,inq[S]=1,a[S]=inf;
while(!q.empty())
{
int x=q.front(); q.pop(),inq[x]=0;
for(int i=fst[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]>dis[x]+w[i])
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);
}
if(dis[T]>inf) return 0;
res+=dis[T]*a[T],pp+=a[T];
for(int i=T;i!=S;i=u[pre[i]]) flow[pre[i]]-=a[T],flow[pre[i]^1]+=a[T];
return 1;
}
int Cl;
struct aa
{
int x1,y1,x2,y2;
}as[P];
stack<aa> st;
#define XX if(ss[x2][y2]=='#') while(!st.empty()) as[++Cl]=st.top(),st.pop();
void walk(int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2) return;
ss[x2][y2]='#';
while(y2>y1) {st.push(aa{x2,y2-1,x2,y2}),y2--;XX}
while(x2>x1) {st.push(aa{x2-1,y2,x2,y2}),x2--;XX}
while(y2<y1) {st.push(aa{x2,y2+1,x2,y2}),y2++;XX}
while(x2<x1) {st.push(aa{x2+1,y2,x2,y2}),x2++;XX}
ss[x1][y1]='.';
}
void cal()
{
int i,j,li;
if(ade())
{
pp=qq=0;
memset(vs,0,sizeof(vs));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(s[i][j]=='#'&&!ch[i][j]) adeg(i,j,i,j),add(S,d(i,j,0),1,0);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ch[i][j]&&s[i][j]!='#') add(d(i,j,1),T,1,0),qq++;
res=0;
while(spfa());
if(res<ans&&qq==pp)
{
ans=res,Cl=0;
memcpy(ss,s,sizeof(ss));
while(!st.empty()) st.pop();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ss[i][j]=='#')
for(li=fst[d(i,j,0)];li;li=nxt[li])
if(!flow[li]&&v[li]!=S) walk(i,j,(v[li]-n*m-1)/m+1,(v[li]-n*m-1)%m+1);
memcpy(tt,ss,sizeof(tt));
}
}
}
void gt()
{
memset(dl,0,sizeof(dl)),cal();
cerr<<ans<<'\n';
for(int t=1000;t>1;t*=0.99)
{
memcpy(Dl,dl,sizeof(Dl));
for(int i=1;i<=t;i++)
{
int la=rand()%n+1,lb=rand()%m+1;
dl[la][lb]^=1;
}
int lp=ans;
if(cal(),lp==ans) memcpy(dl,Dl,sizeof(dl));
else cerr<<ans<<'\n';
}
}
signed main()
{
freopen("surround10.in","r",stdin);
freopen("surround0.out","w",stdout);
int i,j,li,lj;
cin>>n>>m,srand(time(0));
for(i=1;i<=n;i++) scanf("%s",s[i]+1);
gt();
// for(i=1,cout<<'\n';i<=n;i++,cout<<'\n')
// for(j=1;j<=m;j++) cout<<tt[i][j];
cout<<ans<<'\n';
for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
return 0;
}3、4、5、9：
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=3005,N2=65,P=3*N*N2+5,M=1e7+5,inf=1e9;
char s[N][N2],ss[N][N2],tt[N][N2];
int n,m;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
void add(int lu,int lv,int lf,int lw=0)
{
u[++tot]=lu,v[tot]=lv,flow[tot]=lf,w[tot]=lw,nxt[tot]=fst[lu],fst[lu]=tot;
u[++tot]=lv,v[tot]=lu,flow[tot]=0,w[tot]=-lw,nxt[tot]=fst[lv],fst[lv]=tot;
}
int d(int r,int c,int id) {return (r-1)*m+c+n*m*id;}
bool bfs()
{
memset(dis,0x3f,sizeof(dis)),dis[S]=0,que[h=t=1]=S;
while(h<=t)
for(int i=que[h++],j=fst[i];j;j=nxt[j])
if(flow[j]&&dis[v[j]]>dis[i]+1) dis[v[j]]=dis[i]+1,que[++t]=v[j];
return dis[T]<inf;
}
int dfs(int x,int lw,int tt=T)
{
if(x==tt) return lw;
int res=0,zl;
for(int &i=cur[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]==dis[x]+1&&(zl=dfs(v[i],min(lw,flow[i]),tt)))
{
lw-=zl,flow[i]-=zl,res+=zl,flow[i^1]+=zl;
if(!lw) return res;
}
return res;
}
int dinic() {int res=0; while(bfs()) memcpy(cur,fst,sizeof(cur)),res+=dfs(S,inf); return res;}
void bfs(int x)
{
bk[x]=1;
for(int i=fst[x];i;i=nxt[i])
if(!bk[v[i]]&&flow[i]) bfs(v[i]);
}
bool ade()
{
int i,j;
memset(fst,0,sizeof(fst)),tot=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
add(d(i,j,0),d(i,j,1),s[i][j]!='O'? 1:inf);
i<n&&(add(d(i,j,1),d(i+1,j,0),inf),add(d(i+1,j,1),d(i,j,0),inf),0),
j<m&&(add(d(i,j,1),d(i,j+1,0),inf),add(d(i,j+1,1),d(i,j,0),inf),0),
s[i][j]=='O'&&(add(S,d(i,j,0),inf),0);
}
for(i=1;i<=n;i++) add(d(i,1,1),T,inf),add(d(i,m,1),T,inf);
for(i=2;i<m;i++) add(d(1,i,1),T,inf),add(d(n,i,1),T,inf);
int R=dinic();
if(R>=inf) return memset(fst,0,sizeof(fst)),tot=1,0;
memset(bk,0,sizeof(bk)),bfs(S);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(bk[d(i,j,0)]&&!bk[d(i,j,1)]) ch[i][j]=1;
else ch[i][j]=0;
memset(fst,0,sizeof(fst)),tot=1;
return 1;
}
int vs[N][N];
void adeg(int r,int c,int sr,int sc)
{
vs[r][c]=d(sr,sc,0);
if(ch[r][c]) add(d(sr,sc,0),d(r,c,1),1,abs(sr-r)+abs(sc-c));
if(abs(r-sr)+abs(c-sc)>10) return;
if(c<m&&vs[r][c+1]!=d(sr,sc,0)) adeg(r,c+1,sr,sc);
if(c>1&&vs[r][c-1]!=d(sr,sc,0)) adeg(r,c-1,sr,sc);
if(r<n&&vs[r+1][c]!=d(sr,sc,0)) adeg(r+1,c,sr,sc);
if(r>1&&vs[r-1][c]!=d(sr,sc,0)) adeg(r-1,c,sr,sc);
}
int res,ans=inf;
bool spfa()
{
memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)),q.push(S),dis[S]=0,inq[S]=1,a[S]=inf;
while(!q.empty())
{
int x=q.front(); q.pop(),inq[x]=0;
for(int i=fst[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]>dis[x]+w[i])
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);
}
if(dis[T]>inf) return 0;
res+=dis[T]*a[T],pp+=a[T];
for(int i=T;i!=S;i=u[pre[i]]) flow[pre[i]]-=a[T],flow[pre[i]^1]+=a[T];
return 1;
}
int Cl;
struct aa
{
int x1,y1,x2,y2;
}as[P];
stack<aa> st;
#define XX if(ss[x2][y2]=='#') while(!st.empty()) as[++Cl]=st.top(),st.pop();
void walk(int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2) return;
ss[x2][y2]='#';
while(y2>y1) {st.push(aa{x2,y2-1,x2,y2}),y2--;XX}
while(x2>x1) {st.push(aa{x2-1,y2,x2,y2}),x2--;XX}
while(y2<y1) {st.push(aa{x2,y2+1,x2,y2}),y2++;XX}
while(x2<x1) {st.push(aa{x2+1,y2,x2,y2}),x2++;XX}
ss[x1][y1]='.';
}
signed main()
{
freopen("surround5.in","r",stdin);
freopen("surround0.out","w",stdout);
int i,j,li,lj;
cin>>n>>m,srand(time(0));
for(i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int t=1;t;t--)
if(ade())
{
pp=qq=0;
memset(vs,0,sizeof(vs));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(s[i][j]=='#'&&!ch[i][j]) adeg(i,j,i,j),add(S,d(i,j,0),1,0);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ch[i][j]&&s[i][j]!='#') add(d(i,j,1),T,1,0),qq++;
res=0;
while(spfa());
if(res<ans&&qq==pp)
{
ans=res,Cl=0;
memcpy(ss,s,sizeof(ss));
while(!st.empty()) st.pop();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ss[i][j]=='#')
for(li=fst[d(i,j,0)];li;li=nxt[li])
if(!flow[li]&&v[li]!=S) walk(i,j,(v[li]-n*m-1)/m+1,(v[li]-n*m-1)%m+1);
memcpy(tt,ss,sizeof(tt));
}
cerr<<res<<'\n';
}
cout<<ans<<'\n';
for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
return 0;
}8：
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=335,N2=105,P=3*N*N2+5,M=1e7+5,inf=1e9;
char s[N][N2],ss[N][N2],tt[N][N2];
int n,m;
int fst[P],cur[P],nxt[M],u[M],v[M],flow[M],w[M],tot=1;
int que[P],dis[P],h,t,S=P-1,T=P-2;
int bk[P],vis[P];
int ch[N][N2];
int inq[P],a[P],pre[P];
queue<int> q;
int pp,qq;
void add(int lu,int lv,int lf,int lw=0)
{
u[++tot]=lu,v[tot]=lv,flow[tot]=lf,w[tot]=lw,nxt[tot]=fst[lu],fst[lu]=tot;
u[++tot]=lv,v[tot]=lu,flow[tot]=0,w[tot]=-lw,nxt[tot]=fst[lv],fst[lv]=tot;
}
int d(int r,int c,int id) {return (r-1)*m+c+n*m*id;}
bool bfs()
{
memset(dis,0x3f,sizeof(dis)),dis[S]=0,que[h=t=1]=S;
while(h<=t)
for(int i=que[h++],j=fst[i];j;j=nxt[j])
if(flow[j]&&dis[v[j]]>dis[i]+1) dis[v[j]]=dis[i]+1,que[++t]=v[j];
return dis[T]<inf;
}
int dfs(int x,int lw,int tt=T)
{
if(x==tt) return lw;
int res=0,zl;
for(int &i=cur[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]==dis[x]+1&&(zl=dfs(v[i],min(lw,flow[i]),tt)))
{
lw-=zl,flow[i]-=zl,res+=zl,flow[i^1]+=zl;
if(!lw) return res;
}
return res;
}
int dinic() {int res=0; while(bfs()) memcpy(cur,fst,sizeof(cur)),res+=dfs(S,inf); return res;}
void bfs(int x)
{
bk[x]=1;
for(int i=fst[x];i;i=nxt[i])
if(!bk[v[i]]&&flow[i]) bfs(v[i]);
}
int ck(int r,int c) {return r>0&&r<=n&&c>0&&c<=m? s[r][c]=='O':0;}
bool ade()
{
int i,j;
memset(fst,0,sizeof(fst)),tot=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
int la=ck(i-1,j-1)+ck(i-1,j)+ck(i-1,j+1)+ck(i,j-1)+ck(i,j+1)+ck(i+1,j-1)+ck(i+1,j)+ck(i+1,j+1),
lb=ck(i-2,j-2)+ck(i-2,j-1)+ck(i-2,j)+ck(i-2,j+1)+ck(i-2,j+2)+ck(i-1,j-2)+ck(i-1,j+2)+ck(i,j-2)+
ck(i,j+2)+ck(i+1,j-2)+ck(i+1,j+2)+ck(i+2,j-2)+ck(i+2,j-1)+ck(i+2,j)+ck(i+2,j+1)+ck(i+2,j+2);
add(d(i,j,0),d(i,j,1),s[i][j]!='O'&&la!=3&&lb!=5? 1:inf);
i<n&&(add(d(i,j,1),d(i+1,j,0),inf),add(d(i+1,j,1),d(i,j,0),inf),0),
j<m&&(add(d(i,j,1),d(i,j+1,0),inf),add(d(i,j+1,1),d(i,j,0),inf),0),
s[i][j]=='O'&&(add(S,d(i,j,0),inf),0);
}
for(i=1;i<=n;i++) add(d(i,1,1),T,inf),add(d(i,m,1),T,inf);
for(i=2;i<m;i++) add(d(1,i,1),T,inf),add(d(n,i,1),T,inf);
int R=dinic();
if(R>=inf) return memset(fst,0,sizeof(fst)),tot=1,0;
memset(bk,0,sizeof(bk)),bfs(S);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(bk[d(i,j,0)]&&!bk[d(i,j,1)]) ch[i][j]=1;
else ch[i][j]=0;
memset(fst,0,sizeof(fst)),tot=1;
return 1;
}
int vs[N][N];
void adeg(int r,int c,int sr,int sc)
{
vs[r][c]=d(sr,sc,0);
if(ch[r][c]) add(d(sr,sc,0),d(r,c,1),1,abs(sr-r)+abs(sc-c));
if(abs(r-sr)+abs(c-sc)>10) return;
if(c<m&&vs[r][c+1]!=d(sr,sc,0)) adeg(r,c+1,sr,sc);
if(c>1&&vs[r][c-1]!=d(sr,sc,0)) adeg(r,c-1,sr,sc);
if(r<n&&vs[r+1][c]!=d(sr,sc,0)) adeg(r+1,c,sr,sc);
if(r>1&&vs[r-1][c]!=d(sr,sc,0)) adeg(r-1,c,sr,sc);
}
int res,ans=inf;
bool spfa()
{
memset(dis,0x3f,sizeof(dis)),memset(inq,0,sizeof(inq)),q.push(S),dis[S]=0,inq[S]=1,a[S]=inf;
while(!q.empty())
{
int x=q.front(); q.pop(),inq[x]=0;
for(int i=fst[x];i;i=nxt[i])
if(flow[i]&&dis[v[i]]>dis[x]+w[i])
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);
}
if(dis[T]>inf) return 0;
res+=dis[T]*a[T],pp+=a[T];
for(int i=T;i!=S;i=u[pre[i]]) flow[pre[i]]-=a[T],flow[pre[i]^1]+=a[T];
return 1;
}
int Cl;
struct aa
{
int x1,y1,x2,y2;
}as[P];
stack<aa> st;
#define XX if(ss[x2][y2]=='#') while(!st.empty()) as[++Cl]=st.top(),st.pop();
void walk(int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2) return;
ss[x2][y2]='#';
while(y2>y1) {st.push(aa{x2,y2-1,x2,y2}),y2--;XX}
while(x2>x1) {st.push(aa{x2-1,y2,x2,y2}),x2--;XX}
while(y2<y1) {st.push(aa{x2,y2+1,x2,y2}),y2++;XX}
while(x2<x1) {st.push(aa{x2+1,y2,x2,y2}),x2++;XX}
ss[x1][y1]='.';
}
signed main()
{
freopen("surround8.in","r",stdin);
freopen("surround0.out","w",stdout);
int i,j,li,lj;
cin>>n>>m,srand(time(0));
for(i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int t=1;t;t--)
if(ade())
{
pp=qq=0;
memset(vs,0,sizeof(vs));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(s[i][j]=='#'&&!ch[i][j]) adeg(i,j,i,j),add(S,d(i,j,0),1,0);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ch[i][j]&&s[i][j]!='#') add(d(i,j,1),T,1,0),qq++;
res=0;
while(spfa());
if(res<ans&&qq==pp)
{
ans=res,Cl=0;
memcpy(ss,s,sizeof(ss));
while(!st.empty()) st.pop();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(ss[i][j]=='#')
for(li=fst[d(i,j,0)];li;li=nxt[li])
if(!flow[li]&&v[li]!=S) walk(i,j,(v[li]-n*m-1)/m+1,(v[li]-n*m-1)%m+1);
memcpy(tt,ss,sizeof(tt));
}
cerr<<res<<'\n';
}
cout<<ans<<'\n';
for(i=1;i<=Cl;i++) cout<<as[i].x1<<' '<<as[i].y1<<' '<<as[i].x2<<' '<<as[i].y2<<'\n';
return 0;
}