关于该题输入问题
查看原帖
关于该题输入问题
300735
HL_Imrt楼主2024/7/13 14:46

将st定义为char二维数组,并用scanf输入就过了

#include<iostream>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
const int N=5050,M=100050,INF=INT_MAX;//
int n,m,d,s,t,nm,ans,tot;
int hd[N],cnt=1;
int cur[N],dep[N];
char st[50][50];
queue<int>qa;
char c;
struct aaa{
	int to,w,nt;
}a[M];
void add(int u,int v,int w){
	a[++cnt].to=v;
	a[cnt].w=w;
	a[cnt].nt=hd[u];
	hd[u]=cnt;
}
void add1(int p,int i,int j,int x){
	if(i>n||i<1||j<1||j>m) add(p,t,x),add(t,p,0);
	else if(st[i][j]!='0') add(p,(i-1)*m+j,x),add((i-1)*m+j,p,0);
}
int bfs(){
	memset(dep,0,sizeof(dep));
	dep[s]=1;
	qa.push(s);
	while(!qa.empty()){
		for(int i=hd[qa.front()];i;i=a[i].nt){
			if(!dep[a[i].to]&&a[i].w>0){
				dep[a[i].to]=dep[qa.front()]+1;
				qa.push(a[i].to);
			}
		}
		qa.pop();
	}
	return dep[t];
} 
int dfs(int p,int f){
	if(p==t) return f;
	int sum=0,fi;
	for(int i=cur[p];i&&sum<f;i=a[i].nt){
		cur[p]=i;
		if(dep[a[i].to]==dep[p]+1&&a[i].w>0){
			fi=dfs(a[i].to,min(a[i].w,f-sum));
			if(fi>0) a[i].w-=fi,a[i^1].w+=fi,sum+=fi; 
		}
	}
	return sum;
}
void Dinic(){
	int x;
	while(bfs()){
		memcpy(cur,hd,sizeof(hd));
		x=dfs(s,INF);
		if(x>0) ans+=x; 
	}
}
int main(){
	cin>>n>>m>>d;
	nm=n*m,s=2*nm+1,t=2*nm+2;
	for(int i=1;i<=n;i++){
		scanf("%s",st[i]+1);
	}
	int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(st[i][j]!='0'){
			    int now=(i-1)*m+j+nm;//出点 
			    x=st[i][j]-'0';
				add((i-1)*m+j,now,x);  
				add(now,(i-1)*m+j,0);  
				for(int l=1;l<=d;l++) add1(now,i,j+l,INF),add1(now,i,j-l,INF),add1(now,i+l,j,INF),add1(now,i-l,j,INF);
				if(d>=2) add1(now,i-1,j-1,INF),add1(now,i-1,j+1,INF),add1(now,i+1,j-1,INF),add1(now,i+1,j+1,INF);
				if(d>=3){
					add1(now,i-1,j-2,INF),add1(now,i-1,j+2,INF),add1(now,i+1,j-2,INF),add1(now,i+1,j+2,INF);
					add1(now,i-2,j-1,INF),add1(now,i-2,j+1,INF),add1(now,i+2,j-1,INF),add1(now,i+2,j+1,INF);
					add1(now,i-2,j-2,INF),add1(now,i-2,j+2,INF),add1(now,i+2,j-2,INF),add1(now,i+2,j+2,INF); 
				}
				if(d==4){
					add1(now,i-1,j-3,INF),add1(now,i-1,j+3,INF),add1(now,i+1,j-3,INF),add1(now,i+1,j+3,INF);
					add1(now,i-3,j-1,INF),add1(now,i-3,j+1,INF),add1(now,i+3,j-1,INF),add1(now,i+3,j+1,INF);
					add1(now,i-2,j-3,INF),add1(now,i-2,j+3,INF),add1(now,i+2,j-3,INF),add1(now,i+2,j+3,INF);
					add1(now,i-3,j-2,INF),add1(now,i-3,j+2,INF),add1(now,i+3,j-2,INF),add1(now,i+3,j+2,INF);
				}
			} 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='L') add(s,(i-1)*m+j,1),add((i-1)*m+j,s,0),++tot;
		}
	}
	Dinic();
	cout<<tot-ans<<endl;
	return 0;
}

但是将st改为string用cin输入就RE 4个点

#include<iostream>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
const int N=5050,M=100050,INF=INT_MAX;//
int n,m,d,s,t,nm,ans,tot;
int hd[N],cnt=1;
//int cur[N],dep[N];
int pre[N],flow[N];
bool vis[N];
string st[500];
queue<int>qa;
char c;
struct aaa{
	int to,w,nt;
}a[M];
void add(int u,int v,int w){
	a[++cnt].to=v;
	a[cnt].w=w;
	a[cnt].nt=hd[u];
	hd[u]=cnt;
}
void add1(int p,int i,int j,int x){
	if(i>n||i<1||j<1||j>m) add(p,t,x),add(t,p,0);
	else if(st[i][j]!='0') add(p,(i-1)*m+j,x),add((i-1)*m+j,p,0);
}
void add(int u,int v,long long w){
	a[++cnt].to=v;
	a[cnt].w=w;
	a[cnt].nt=hd[u];
	hd[u]=cnt;
}
bool bfs(){
    while(!qa.empty()) qa.pop();
	qa.push(s);
	flow[s]=INF;
	memset(vis,0,sizeof(vis));
	while(!qa.empty()){
		for(int i=hd[qa.front()];i;i=a[i].nt){
			if(a[i].w<=0||vis[a[i].to]) continue;
			flow[a[i].to]=min(flow[qa.front()],a[i].w);
			vis[a[i].to]=true;
			pre[a[i].to]=i;
			qa.push(a[i].to);
			if(a[i].to==t) return true;
		}
		qa.pop();
	}
	return false;
}
void update(){
	int p=t;
	while(p!=s){
		a[pre[p]].w-=flow[t];
		a[pre[p]^1].w+=flow[t];
		p=a[pre[p]^1].to; 
	}
	ans+=flow[t];
}
int main(){
	cin>>n>>m>>d;
	nm=n*m,s=2*nm+1,t=2*nm+2;
	for(int i=1;i<=n;i++){
		st[i][0]=c;
		for(int j=1;j<=m;j++) cin>>st[i][j];
	}
	int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(st[i][j]!='0'){
			    int now=(i-1)*m+j+nm;//出点 
			    x=st[i][j]-'0';
				add((i-1)*m+j,now,x);  
				add(now,(i-1)*m+j,0);  
				for(int l=1;l<=d;l++) add1(now,i,j+l,INF),add1(now,i,j-l,INF),add1(now,i+l,j,INF),add1(now,i-l,j,INF);
				if(d>=2) add1(now,i-1,j-1,INF),add1(now,i-1,j+1,INF),add1(now,i+1,j-1,INF),add1(now,i+1,j+1,INF);
				if(d>=3){
					add1(now,i-1,j-2,INF),add1(now,i-1,j+2,INF),add1(now,i+1,j-2,INF),add1(now,i+1,j+2,INF);
					add1(now,i-2,j-1,INF),add1(now,i-2,j+1,INF),add1(now,i+2,j-1,INF),add1(now,i+2,j+1,INF);
					add1(now,i-2,j-2,INF),add1(now,i-2,j+2,INF),add1(now,i+2,j-2,INF),add1(now,i+2,j+2,INF); 
				}
				if(d==4){
					add1(now,i-1,j-3,INF),add1(now,i-1,j+3,INF),add1(now,i+1,j-3,INF),add1(now,i+1,j+3,INF);
					add1(now,i-3,j-1,INF),add1(now,i-3,j+1,INF),add1(now,i+3,j-1,INF),add1(now,i+3,j+1,INF);
					add1(now,i-2,j-3,INF),add1(now,i-2,j+3,INF),add1(now,i+2,j-3,INF),add1(now,i+2,j+3,INF);
					add1(now,i-3,j-2,INF),add1(now,i-3,j+2,INF),add1(now,i+3,j-2,INF),add1(now,i+3,j+2,INF);
				}
			} 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='L') add(s,(i-1)*m+j,1),add((i-1)*m+j,s,0),++tot;
		}
	}
//	Dinic();
    while(bfs())  update();
	cout<<tot-ans<<endl;
	return 0;
}

调了好久QAQ

求大佬解疑

2024/7/13 14:46
加载中...