[NOI2001]食物鍊
題目大意是肯定能夠看得懂的,就是怎麼做是個問題而已。。
我的方法是用帶權并查集 ,首先我們可以加多一個數組r表示 r和父親(根) 的關系
詳情看代碼就懂了
#include<bits/stdc++.h> //a==fa[a] 0 a -> fa[a] 1 a <- fa[a] 2
using namespace std; //上面就是表示r的三種狀态,如果為0就說明和父親相等,為1就表明可以吃父親,為2就是被父親吃。
int fa[],r[],ans,n,m;
int get(int x){
if(fa[x]==x) return x;
int y=fa[x];//記住原來的父親
fa[x]=get(fa[x]);//路徑壓縮
r[x]=(r[y]+r[x])%;//更新和現在的父親的關系
return fa[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) fa[i]=i;
for(;m--;){
int c,x,y;
scanf("%d%d%d",&c,&x,&y);
if(x>n||y>n) ans++;
else
{
int xx=get(x),yy=get(y);
if(xx==yy){
if(c==&&r[x]!=r[y]) ans++;//就是判斷和根的關系十分相同
if(c==&&(r[x]==r[y]||(r[y]+)%==r[x])) ans++;//判斷沖突關系
}
else {
fa[xx]=yy;//建立關系
if(c==) r[xx]=(r[y]-r[x]+)%;
else r[xx]=(r[y]-r[x]+)%;
}
}
}
printf("%d",ans);
return ;
}
其實還有一種方法,就是反正我們不确定每個動物是屬于A、B還是C,我們就每種情況都考慮進去(開3倍空間)。假設是1操作,輸入的x和y,我們就把每個種類的x和連起來,成為一個集合(并查集),如果是2操作就把三種情況:1、x是A y是B 2、x是B y是C 3、x是C y是A
分别連起來,然後判斷沖突就很簡單了。
看代碼吧
#include<bits/stdc++.h>
using namespace std;
int fa[*],n,m,ans;
int get(int x){
return x==fa[x]? x:(fa[x]=get(fa[x]));//簡單的并查集
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=*n;i++) fa[i]=i;
for(;m--;){
int c,x,y;
scanf("%d%d%d",&c,&x,&y);
if(x>n||y>n) ans++;//不屬于這條食物鍊
else
if(c==){
if(get(x+n)==get(y)||get(x)==get(y+n)) ans++;//如果x是y的獵物或y是x的獵物就沖突
else fa[get(x)]=fa[get(y)],fa[get(x+n)]=fa[get(y+n)],fa[get(x+*n)]=fa[get(y+*n)];//就是上面講的
}
else{
if(get(x)==get(y)||get(x+n)==get(y)) ans++; //如果x和y同類或x是y的獵物就沖突
else fa[get(x)]=fa[get(y+n)],fa[get(x+n)]=fa[get(y+*n)],fa[get(x+*n)]=fa[get(y)];//就是上面講的+1
}
}
printf("%d",ans);
return ;
}
做完這題感覺對并查集的了解又深了一些