两种做法。
扩展域不bb了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=5e4+3;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int fa[N*3];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
// 1~n,1~n same 1~n,n+1~2*n x是y的天敌 1~n,2*n+1~2*n x是y的肉食
int main()
{
int n,m;qr(n),qr(m);int ans=0;
for(int i=1;i<=n*3;i++)fa[i]=i;
for(int i=1,x,y,op;i<=m;i++)
{
qr(op),qr(x),qr(y);
if(x>n||y>n||(x==y&&op==2)){++ans;continue;}
if(op==1)
{
int x1=x,x2=x+n,x3=x+2*n;
int y1=y,y2=y+n,y3=y+2*n;
if(get(x1)==get(y2)||get(x1)==get(y3)){++ans;continue;}
int p=get(x1),q=get(y1);fa[p]=q;
p=get(x2),q=get(y2);fa[p]=q;
p=get(x3),q=get(y3);fa[p]=q;
}
else
{
int x1=x,x2=x+n,x3=x+2*n;
int y1=y+n,y2=y+2*n,y3=y;
if(get(x1)==get(y2)||get(x1)==get(y3)){++ans;continue;}
int p=get(x1),q=get(y1);fa[p]=q;
p=get(x2),q=get(y2);fa[p]=q;
p=get(x3),q=get(y3);fa[p]=q;
}
}
qw(ans);puts("");
return 0;
}
边带权
$d[x]=1 fa[x]$被吃了,$d[x]=2 x$被吃了,$d[x]=0 fa[x]$与$x$为同类。
那么关于合并的处理,$ans=d[x]+d[p]+(3-d[y])$,由于边是向上传递的,也就是$y$这条边,要逆回$y$,则权值就为$3-d[y]$
关于判断合法,x与y的关系也就是$d[x]-d[y]$。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=5e4+4;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int fa[N],d[N];
// d[x]=1 fa[x]被吃了 d[x]=2 x被吃了 d[x]=0 fa[x]与x为同类
int get(int x)
{
if(x==fa[x])return x;
int root=get(fa[x]);
d[x]=(d[x]+d[fa[x]])%3;
return fa[x]=root;
}
int main()
{
int n,m;qr(n),qr(m);int ans=0;
for(int i=1;i<=n;i++)fa[i]=i,d[i]=0;
for(int i=1;i<=m;i++)
{
int op,x,y;qr(op),qr(x),qr(y);
int p=get(x),q=get(y);
if(x>n||y>n||(x==y&&op==2)){++ans;continue;}
if(p!=q)
{
fa[p]=q;
if(op==2)d[p]=(d[y]-d[x]+4)%3;
if(op==1)d[p]=(d[y]-d[x]+3)%3;
}
else
{
if(op==2&&(d[x]-d[y]+3)%3!=1)++ans;
if(op==1&&(d[x]-d[y]+3)%3!=0)++ans;
}
}
printf("%d\n",ans);
return 0;
}
最后一次更新于2019-10-11
0 条评论