54分求助
查看原帖
54分求助
632131
Kevin911楼主2023/12/23 23:35
#include<bits/stdc++.h>
using namespace std;
string s[21];
char ch[21][21];
bool vis[401],endd[401];
const int size=160001;
int to[size],nxt[size],w[size],v[401],head[401],pre[401],cnt=-1; 
int a[21][21],x[401],y[401];
int k=0,ans;
void addedge(int x,int y)
{//建正向边和反向边
	to[++cnt]=y;
	nxt[cnt]=head[x];
	//w[cnt]=1;
	head[x]=cnt;
	to[++cnt]=x;
	nxt[cnt]=head[y];
	//w[cnt]=1;
	head[y]=cnt;
}
bool bfs()
{
	queue<int> q;
	q.push(0);
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	while(!q.empty())
	{
		int no=q.front();
		q.pop();
		for(int i=head[no];i;i=nxt[i])
		{
			int node=to[i];
			if(node==k+1&&!endd[no])
			{
				pre[node]=i;
				endd[no]=1;
				return 1;
			}
			else if(node!=k+1)
			{
				if(vis[node]) continue;
				if(!v[node]) continue;
				pre[node]=i;
				q.push(node);
				vis[node]=1;
			}
		}
	}
	return 0;
}
void calc()
{
	ans--;
	int nw=k+1;
	while(nw!=0)
	{	
		//cout<<nw<<' ';
		int i=pre[nw];
		v[nw]--;
		nw=to[i^1];
	}
	//cout<<endl;
}
int main()
{
	int r,c,d;
	cin>>r>>c>>d;
	for(int i=1;i<=r;i++)
	{
		cin>>s[i];
		for(int j=1;j<=c;j++) a[i][j]=s[i][j-1]-'0';
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
		{
			cin>>ch[i][j];
			if(ch[i][j]=='L'||a[i][j])
			{
				y[++k]=i;
				x[k]=j;
				v[k]=a[i][j];
			}
			if(ch[i][j]=='L') ans++;
		}
	for(int i=1;i<=k;i++)
		if(x[i]-d<=0||y[i]-d<=0||x[i]+d>c||y[i]+d>r)
			addedge(0,i);
	for(int i=1;i<=k;i++)
		if(ch[y[i]][x[i]]=='L')
			addedge(i,k+1);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			if(i!=j)
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d*d)
					addedge(i,j);
	//for(int i=1;i<=cnt;i+=2)
	//	cout<<to[i^1]<<' '<<to[i]<<endl;
	while(bfs()) calc();
	//cout<<endd[3]<<' '; 
	cout<<ans;
}
2023/12/23 23:35
加载中...