首页 > 代码库 > 20140711 eat

20140711 eat

2024-07-11 16:33:12   220人阅读

不多说 NOI2001食物链

 

核心就是并查集，并查集数组中存0 1 2 3 表示未分营养级 A  B  C

 然后再一个个恶心的判断....

inline bool Union(int x,int y,int D){
int a=find(x), b=find(y);
if(a==b){
if(D==1&&rank[x]!=rank[y]) return false;
if(D==2){
if(rank[x]==2&&rank[y]!=1)return false;
if(rank[x]==1&&rank[y]!=0)return false;
if(rank[x]==0&&rank[y]!=2)return false;
}
return true;
}
f[a] = b;
if(D==2){
rank[a] = (rank[y]-rank[x]+3+1)%3;
}
else{
rank[a] = (rank[y]-rank[x]+3)%3;
}
return true;
}

 

其实一开始我想的是用3个set，原因嘛，跟set（那道题）一样........

 

 1 #include<cstdio>  2   3 const int N = 100005;  4 int n, m, f[N], rank[N];  5   6 inline void init(){  7     for(int i=0; i<=n; ++i)  8         f[i]=i,rank[i]=0;  9 } 10  11 int find(int x){ 12     if(x==f[x])return x; 13     int fa=f[x]; 14     f[x]=find(f[x]); 15     rank[x] = (rank[x]+rank[fa])%3; 16     return f[x]; 17 } 18  19 inline bool Union(int x,int y,int D){ 20     int a=find(x), b=find(y); 21     if(a==b){ 22         if(D==1&&rank[x]!=rank[y]) return false; 23         if(D==2){ 24             if(rank[x]==2&&rank[y]!=1)return false; 25             if(rank[x]==1&&rank[y]!=0)return false; 26             if(rank[x]==0&&rank[y]!=2)return false; 27         } 28         return true; 29     } 30     f[a] = b; 31     if(D==2){ 32         rank[a] = (rank[y]-rank[x]+3+1)%3; 33     } 34     else{ 35         rank[a] = (rank[y]-rank[x]+3)%3;   36     } 37     return true; 38 } 39  40 int main(){ 41     freopen("eat.in","r",stdin);42     freopen("eat.out","w",stdout);43     int x,y,d; 44     scanf("%d%d",&n,&m); 45     init(); 46     int cnt=0; 47     for(int i=0; i<m; ++i){ 48         scanf("%d%d%d",&d,&x,&y); 49         if(x>n || y>n || d==2&&x==y){ 50             ++cnt; continue; 51         } 52         if(!Union(x,y,d)) { 53             ++cnt; 54         } 55     } 56     printf("%d\n",m-cnt); 57     return 0; 58 }
View Code

 


联系
我们