社区讨论
全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 条回复,欢迎继续交流。
正在加载回复...