社区讨论

全RE,求助大佬QwQ,搞不明白为什么

P2962[USACO09NOV] Lights G参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@ly8gdijj
此快照首次捕获于
2024/07/05 16:47
2 年前
此快照最后确认于
2024/07/05 16:49
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int h[100005],e[100005],ne[100005],idx;
string qs[100005],qe[1000005];
int n,m;int ans=0x3f3f3f3f;
int hs,ts=-1,he,te=-1;
void add(int a,int b){
	ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}
map<string,int> st;
map<string,int> num;
int bfs()
{
    ts=te=0;
	for(int i=1;i<=n;i++)qs[ts]+= '0',qe[te]+='1';
	num[qs[ts]]=0;st[qs[ts]]=1;
	num[qe[te]]=0,st[qe[te]]=2;
	while(hs<=ts||hs<=ts){
		if(hs<=ts){
			string q;
			for(int i=1;i<=n;i++){
				q=qs[hs];
				if(q[i-1]=='0')q[i]='1';
				else q[i-1]='0';
				for(int j=h[i];j!=-1;j=ne[j]){
					if(q[j-1]=='0')q[j-1]='1';
					else q[j-1]='0';
				}
				if(st[q]==0)qs[++ts]=q,st[q]=1,num[q]=num[qs[hs]]+1;
				else if(st[q]==2){
					int a=num[qs[hs]]+1,b=num[q];
					ans=min(ans,a+b);
				}
			}
			hs++;
		}
		if(he<=te){
			string q;
			for(int i=1;i<=n;i++){
				q=qe[he];
				if(q[i-1]=='0')q[i-1]='1';
				else q[i-1]='0';
				for(int j=h[i];j!=-1;j=ne[j]){
					if(q[j-1]=='0')q[j-1]='1';
					else q[j-1]='0';
				}
				if(st[q]==0)qe[++te]=q,st[q]=2,num[q]=num[qe[he]]+1;
				else if(st[q]==1){
					int a=num[qe[he]]+1,b=num[q];
					ans=min(ans,a+b);
				}
			}
			he++;
		}
		if(ans!=0x3f3f3f3f)break;
	}
	return ans;
}

int main()
{
	memset(h,-1,sizeof(h));
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	cout<<bfs();
}
/*
5 6
1 2
1 3
4 2
3 4
2 5
5 3
*/

回复

0 条回复,欢迎继续交流。

正在加载回复...