社区讨论
请求NOIPT2代码错误
学术版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lp45da25
- 此快照首次捕获于
- 2023/11/18 22:31 2 年前
- 此快照最后确认于
- 2023/11/19 09:15 2 年前
如下,这是我的代码(疑问点我用注释标注出来了)
CPPWANGZHAOLAN19829799068#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=1145141919810ll;
int a[N],n,m;
int head[N],tot;
struct edge{
int next,to,d;
}e[N<<1];
void add(int from,int to,int d){
e[++tot].next=head[from];head[from]=tot;e[tot].to=to;e[tot].d=d;
}
bool v1[N],v2[N],v3[N];
int v4[N];//v1,v2,v3,v4分别是为了算出图上有无U,图上有几个点,图上有无TF,图上可否黑白染色
bool dfs1(int x){
v1[x]=1;bool ret=0;if(a[x]==0)ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v1[y])continue;if(dfs1(y))ret=1;}return ret;
}
int dfs2(int x){
v2[x]=1;int ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v2[y])continue;ret+=dfs2(y);}return ret;
}
bool dfs3(int x){
v3[x]=1;bool ret=0;if(a[x]==1||a[x]==2)ret=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(v3[y])continue;if(dfs3(y))ret=1;}return ret;
}
bool dfs4(int x,int c){
v4[x]=c;bool ret=1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(e[i].d==1){
if(v4[y]==0)dfs4(y,c);
else if(v4[y]!=c)ret=0;
}
else{
if(v4[y]==0)dfs4(y,3-c);
else if(v4[y]==c)ret=0;
}
}
return ret;
}
//int t,c;
signed main(){
int t,c;//如果将这句话放到全局变量里洛谷上就可以AC了,反之就不行,求大佬指点。
cin>>c>>t;
while(t--){
int ans=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
v1[i]=0;
v2[i]=0;
v3[i]=0;
v4[i]=0;
e[i].d=0;
e[i].next=0;
e[i].to=0;
e[i+n].d=0;
e[i+n].next=0;
e[i+n].to=0;
}
for(int i=1;i<=n;i++)a[i]=i;
while(m--){
char x;scanf("%s",&x);//经检测,如果t在局部变量里,到这里t会直接归零,请求这是为啥
if(x=='-'){int l,r;scanf("%lld%lld",&l,&r);a[l]=-a[r];}
if(x=='+'){int l,r;scanf("%lld%lld",&l,&r);a[l]=a[r];}
if(x=='U'){int l;scanf("%lld",&l);a[l]=0;}
if(x=='T'){int l;scanf("%lld",&l);a[l]=n+1;}
if(x=='F'){int l;scanf("%lld",&l);a[l]=-n-1;}
}
tot=0;for(int i=1;i<=n;i++)head[i]=0;
for(int i=1;i<=n;i++){
if(abs(a[i])<=n&&a[i]!=0){
if(a[i]==i);else if(-a[i]==i)a[i]=0;else {add(i,abs(a[i]),abs(a[i])/a[i]);add(abs(a[i]),i,abs(a[i])/a[i]);a[i]=n+114;}
}
if(a[i]==-n-1)a[i]=1;
if(a[i]==n+1)a[i]=2;
}
for(int i=1;i<=n;i++){
if(!v1[i]){
int num=dfs2(i);
if(dfs1(i)){
ans+=num;
}
else if((!dfs3(i))&&(!dfs4(i,1))){
ans+=num;
}
}
}
cout<<ans<<"\n";
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...