为啥不可以这样子输入数据
查看原帖
为啥不可以这样子输入数据
90562
我要考北大楼主2021/3/17 00:33
#include<bits/stdc++.h>
#define r read()
#define bb printf("!!\n");
#define cc printf("\n");
using namespace std;
inline int read()
{
	bool ok=0 ;int res=0;char c;
	while(((c=getchar())<'0'||c>'9')&&c!='-');
	if(c=='-') ok=1;else res=c-48;
	while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+(c-48);
	return ok ? ~res + 1:res;
}
const int N=1e5+100;
int h[N],net[N],go[N],val[N],ecnt=1;
void add(int u,int v,int w){go[++ecnt]=v;val[ecnt]=w;net[ecnt]=h[u];h[u]=ecnt;}
int s,t,n,m;int vis[N];
int g[110][110];
int id[110][110];
int dis(int a,int b,int c,int d)
{
	return ((a-c)*(a-c)+(b-d)*(b-d));
}
int dfs(int u)
{
//	printf("u=%d->",u);
	if(u==t)return 1;
	vis[u]=1;
	for(int e=h[u];e;e=net[e])
	{
		int v=go[e];
		if(vis[v]||val[e]==0)continue;
		if(dfs(v))
		{
			val[e]--;
			val[e^1]++;
			return 1;
		}
	}
	return 0;
}

int main()
{
 #ifndef ONLINE_JUDGE
	freopen("cin.txt","r",stdin);
//	freopen("cout.txt","w",stdout);
	#endif
	int d;
	n=r;m=r;d=r;
	s=2*n*m+1;
	t=2*n*m+2;
//	printf("s=%d t=%d\n",s,t);
	int cnt=1;
	
	
		for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			id[i][j]=cnt;
			cnt++;
		}
	}
	cnt=n*m;
//	cout<<d<<" "<<dis(2,0,2,2)<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%1d",&g[i][j]);
			if(g[i][j])
			{
				add(id[i][j]+cnt,id[i][j],g[i][j]);
				add(id[i][j],id[i][j]+cnt,0); 
				
				for(int k1=0;k1<=n+1;k1++)
				{
					for(int k2=0;k2<=m+1;k2++)
					{
						if(k1==i&&k2==j)continue;
						if(d*d>=dis(k1,k2,i,j))//d>dis(k1,k2,i,j)+1e-6||fabs(d-dis(k1,k2,i,j))<1e-6
						{
							
							if(id[k1][k2])
							{
								add(id[i][j],id[k1][k2]+cnt,1e9);
								add(id[k1][k2]+cnt,id[i][j],0);	
//								printf("k1=%d k2=%d i=%d j=%d id=%d \n",k1,k2,i,j,id[i][j]);
								
							}else
							{
								
								add(id[i][j],t,1e9);
								add(t,id[i][j],0);
							}
							
						}
					}
				}
			}
			
		}
	}
	
	int tot=0;
	char op;
		for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%c",&op);
			while(op==10)scanf("%c",&op);
			if(op=='L')
			{
				//printf("")
				add(s,id[i][j]+cnt,1),add(id[i][j]+cnt,s,0),tot++;	
			}
			//printf("%c",op);
		}
	//	printf("\n");
	}
	
	int res=0,ans=0;
	while((res=dfs(s))>0)
	{
		ans+=res;
//		cc
//		bb
		memset(vis,0,sizeof(vis));
	}
	printf("%d\n",tot-ans);
	return 0;
}
2021/3/17 00:33
加载中...