标签：6005 int House add Nanami pr2 pr1 Problem id
- 求出最大流后，从源点开始沿残量网络BFS，标记能够到达的点。E中所有连接已标记点和未标记点的边构成最小割
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[6005];
vector<int>c[6005];
vector<int>d[6005];
bool v[6005];
int pr1[6005],pr2[6005];
char w[1005][1005];
int n,m;
int s=0,t;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
void update(int l)
{
int p=t;
while(p!=s)
{
c[pr1[p]][pr2[p]]-=l;
c[p][d[pr1[p]][pr2[p]]]+=l;
p=pr1[p];
}
}
int dfs1(int n1,int l)
{
if(n1==t)
{
update(l);
return l;
}
else
{
for(int i=0;i<a[n1].size();i++)
{
if(c[n1][i]!=0&&v[a[n1][i]]==false)
{
pr1[a[n1][i]]=n1;
pr2[a[n1][i]]=i;
v[a[n1][i]]=true;
int va=dfs1(a[n1][i],min(l,c[n1][i]));
if(va!=0)
{
return va;
}
}
}
}
return 0;
}
void dfs2(int n1)
{
v[n1]=true;
for(int i=0;i<a[n1].size();i++)
{
if(v[a[n1][i]]==false&&c[n1][i]!=0)
{
dfs2(a[n1][i]);
}
}
}
void add(int u,int v,int w)
{
a[u].push_back(v);
a[v].push_back(u);
c[u].push_back(w);
c[v].push_back(0);
d[u].push_back(a[v].size()-1);
d[v].push_back(a[u].size()-1);
}
int id(int i,int j,int opt)
{
return (i-1)*m+j+opt*n*m;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
t=2*n*m+1;
for(int i=0;i<=2*n*m+1;i++)
{
a[i].clear();
c[i].clear();
d[i].clear();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
if(w[i][j]=='H')
{
add(s,id(i,j,0),INT_MAX);
}
if(w[i][j]=='.')
{
if(i==1||i==n||j==1||j==m)
{
add(id(i,j,1),t,INT_MAX);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int f;
cin>>f;
if(f>0)
{
add(id(i,j,0),id(i,j,1),f);
}
else
{
add(id(i,j,0),id(i,j,1),INT_MAX);
}
if(w[i][j]!='#')
{
for(int k=0;k<4;k++)
{
if(w[i+dx[k]][j+dy[k]]=='.'||w[i+dx[k]][j+dy[k]]=='H')
{
add(id(i+dx[k],j+dy[k],1),id(i,j,0),INT_MAX);
}
}
}
}
}
int ans=0,va;
memset(v,false,sizeof(v));
v[s]=true;
while(va=dfs1(s,INT_MAX))
{
for(int i=0;i<=2*n*m+1;i++)
{
v[i]=false;
}
v[s]=true;
ans+=va;
}
memset(v,false,sizeof(v));
dfs2(s);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(v[id(i,j,0)]==true&&v[id(i,j,1)]==false)
{
w[i][j]='#';
}
}
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<w[i][j];
w[i][j]=' ';
}
cout<<endl;
}
}
return 0;
}
/*
1
5 5
1 2 2
2 3 2
3 5 3
1 4 5
4 3 6
*/
标签：6005,
int,
House,
add,
Nanami,
pr2,
pr1,
Problem,
id
From： https://www.cnblogs.com/watersail/p/18279678