NOI'2001第一试第一题《食物链（eat）》解题报告
东北育才学校 俞玮
2001年10月11日
摘要：
算法# 算法1 算法2
时间复杂度 Θ(nlogn+m) Θ(mα(n+m,m)+n)
空间复杂度 O(n) O(n)
特殊数据结构 分离集合 分离集合
问题转述：
　　给定某个含有n个元素的集合S，其中每个元素都具有三种属性（A、B或C）中的一种，是根据已给出的各个元素之间的相对关系[ 甲与乙的相对关系有四种，分别为甲和乙属性相同、甲吃乙、甲被乙吃和无法确定。下文还有“相对属性关系”，指的是当定义甲的属性为A时，乙的属性（这里由于存在“不确定”的关系，故乙的属性可能无定义，但本文中提到的地方保证并不会遇到这种情况）。]集R来确定某两个元素之间的相对关系。
分析：
　　在读题之后我们可以简单地得出处理一条输入的流程图如下：
　　其中的“简单判定”本身也十分简单，还需要进一步思考的就是“逻辑判定”和“把当前输入加入已知关系集”两个部分。
逻辑判定（算法部分）：
　　这一部分也是流程中唯一需要算法设计的部分。考虑输入中的两个元素a、b和它们之间的相对关系r(a, b)，问题就是要通过已知的关系集R求出a、b之间的相对关系。
　　我们可知对于任意a≠b有如下定理：
　　定理1. 当且仅当S中存在一个有限元素序列(P1, P2, …, Pm)（m≥0）使得aP1、P1P2、…、Pm-1Pm、Pmb（或m=0时的ab）之间的相对关系均已确定时，b对a的相对关系属性才可以确定。
　　更形象些说，如果我们把集合S看作点集、已知关系集R看作边集，则在无向图G<S，R>中，点a和点b的相对关系能确定的充要条件就是a和b在同一连同分量中。
　　这样，求a、b之间的相对关系就可以通过一次以a或b为起点的广度搜索[ 搜索时，与点a直接相连的点集Q1中的点对a的相对关系属性可以直接得出，与点集Q1中的点相连的点集Q2中的点对a的相对关系属性可以通过Q1对a的相对关系间接得出，以此类推，就可以得到所有点对a的相对关系属性。]来实现。这样进行一次判定的时间复杂度为O(|R|)，由于共有m次判定，故共需时间O(m|R|)=O(m2)大了一些。仔细考虑一下，是由于每次都重复搜索了一部分。是不是能把搜索过的部分保存下来呢？这就需要结合下一部分一起考虑。
把当前输入加入已知关系集（数据结构部分）：
　　由于我们要求的是两点间的一条路径，故我们可以用邻接链表来存储个点之间的关系。不过这样的结构即麻烦有庞大还不便于更新[ 这里的更新不仅仅指的是保存输入，还指保存已搜索过的部分。]。我们注意到，两点间保存超过一条的路径其实是冗余无意义的。也就是所，我们所需要保存的只是一个森林而不是图。这样，如果我们对森林中的每棵树使用父节点表示法，只用O(n)的空间就可以了。更特殊的，路径实际上只是一个表现形式，也不是必须的。我们可以一每棵树中的某一点为“根”，每个节点以它为参照来得出各自的相对关系属性，在通过对同一节点的相对关系属性来得出两两之间的相对关系。在加入关系时，我们需要加入的也只是符合逻辑的在不同的两棵树上的点之间的关系[ 很明显的，加入在同一棵树上两个点之间的关系什么也不会改变。]。这样，我们可以看出这种操作非常类似于数据结构中的分离集合树实现的合并操作。为了简化思考过程，我们可以直接在分离集合这种数据结构的基础上进行改进。在存储时对每个节点增设一个域来保存当前节点与父节点的相对关系，在获取节点信息时需要同时根据该域来确定当前节点与“根”的相对关系属性，并在路径压缩时同时对相对关系进行压缩[ 具体处理方法请参见源程序。]，并在合并时也要更新消失的“根”与保留下来的“根”的关系。
　　这样，我们可以得到用分离集合树实现的改进实现“逻辑判定”和“加入关系”的算法如下[ 设分离集合为DisjointSet，合并两棵树的操作为DisjointSet.Union(a, b)、a, b为树根，获取节点信息的操作为DisjointSet.FindRoot(a ,var ra, var ga)，这里返回的ra为a所在树的树根，ga为a对于树根的相对关系属性。]：
　　逻辑判定：
DisjointSet.FindRoot(a, ra, ga);
DisjointSet.FindRoot(b, rb, gb);
If (r(ga, gb)≠r(a, b)) Then Return “否” Else Return “是”;
　　加入关系：
If (ra≠rb) Then DisjointSet.Union(ra, rb);
　　这个算法的时间复杂度为Θ(mα(n+m,m)+n)，空间复杂度为O(n)。[ 这个算法称作算法1。]
　　同样的，我们还知道分离集合还有一种快速实现为链式实现，这种方法是不是也可以应用呢？在这种实现时，我们对每个节点增加一个域用来保存该节点与“根”节点的关系。在获取节点信息时只需要取出这个域的值就可以了。而在合并时由于链式实现本身就要访问某条链中所有的节点，故我们可以在访问节点是参照输入的a和b的关系来更改这条链中的节点对于新的“根”的相对关系属性，并且也不会增加时间复杂度。
　　这个算法的时间复杂度为Θ(m+nlogn)，空间复杂度为O(n)。[ 这个算法称作算法2。]
总结：
　　算法+数据结构=程序。在解决这道题目，我们很好的理解了算法和数据结构是如何有机的结合在一起的。对于一个算法，我们要采用最合适的数据结构，甚至对数据结构进行相应的改进来适应算法。而另一方面，我们也可以对于各种不同形式的数据结构来改进算法，使得两者得到最好的配合。
附录：
　　 甲与乙的相对关系有四种，分别为甲和乙属性相同、甲吃乙、甲被乙吃和无法确定。下文还有“相对属性关系”，指的是当定义甲的属性为A时，乙的属性（这里由于存在“不确定”的关系，故乙的属性可能无定义，但本文中提到的地方保证并不会遇到这种情况）。
搜索时，与点a直接相连的点集Q1中的点对a的相对关系属性可以直接得出，与点集Q1中的点相连的点集Q2中的点对a的相对关系属性可以通过Q1对a的相对关系间接得出，以此类推，就可以得到所有点对a的相对关系属性。
这里的更新不仅仅指的是保存输入，还指保存已搜索过的部分。
很明显的，加入在同一棵树上两个点之间的关系什么也不会改变。
具体处理方法请参见源程序。
设分离集合为DisjointSet，合并两棵树的操作为DisjointSet.Union(a, b)、a, b为树根，获取节点信息的操作为DisjointSet.FindRoot(a ,var ra, var ga)，这里返回的ra为a所在树的树根，ga为a对于树根的相对关系属性。

import java.util.Scanner;

public class Main {
    static int n,k;static int[] f =new int[50001]; 
    static  int[] w =new int[50001]; 
    public static int root(int x) {
        int d ,temp ;
        if(f[x] == -1) return x;
        temp = f[x];
        f[x] = root(f[x]);
        w[x] += w[temp];
        w[x] %=3;
        return f[x];
    }
    public  static void main(String[] args) {
        int d,x,y,ans=0;
        int a,b;
        Scanner sc = new Scanner(System.in);
        n= sc.nextInt();
        k = sc.nextInt();
        
        for(int i=0; i<=n;++i) {
            f[i] = -1;
            w[i] = 0;
        }
        for(int i=1; i<=k; i++)
        {
           d = sc.nextInt();
           x = sc.nextInt();
           y = sc.nextInt();
           
           if(x>n || y>n || (d==2 && x == y))
               {
                 ans++;
               }
           else {
             a=root(x);
             b=root(y);
             if(a==b)
             {
                 if(((w[y]-w[x])%3+3)%3!=0&&d==1) ans++;
                 if(((w[y]-w[x])%3+3)%3!=1&&d==2) ans++;
             }
             else {
                 if(d==1)
                 {
                     f[a] = b;
                     w[a] = (w[y] -w[x]%3+3)%3;
                 }
                 if(d ==2)
                 {
                     f[a] = b;
                     w[a] = (w[y] -w[x]%3-1+3)%3;
                     
                 }
             }         
           }      
        }       
        System.out.println(ans);
    }
}

https://blog.csdn.net/Ike940067893/article/details/56484375?locationNum=2&fps=1 题解这里我参考用java写的

Accepted

状态 耗时 内存占用

#1 Accepted 2ms 256.0 KiB
#2 Accepted 3ms 256.0 KiB
#3 Accepted 3ms 256.0 KiB
#4 Accepted 4ms 256.0 KiB
#5 Accepted 5ms 256.0 KiB
#6 Accepted 8ms 256.0 KiB
#7 Accepted 27ms 256.0 KiB
#8 Accepted 38ms 256.0 KiB
#9 Accepted 49ms 376.0 KiB
#10 Accepted 990ms 620.0 KiB

难度6？？？？？
并没有用并查集（所以码量有点大。。。）

经典套路题
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 50000 + 5;

int n, k, pa[N * 3];

int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n * 3; i++) pa[i] = i;
int ans = 0;
for (int i = 1; i <= k; i++) {
int d, x, y; scanf("%d%d%d", &d, &x, &y);
if ((x > n || y > n) || (d == 2 && x == y)) { ans++; continue; }
if (d == 1) {
if (findset(x) == findset(y + n) || findset(x + n) == findset(y)) ans++;
else {
pa[findset(x)] = findset(y);
pa[findset(x + n)] = findset(y + n);
pa[findset(x + n * 2)] = findset(y + n * 2);
}
} else {
if (findset(x) == findset(y) || findset(x + n) == findset(y)) ans++;
else {
pa[findset(x)] = findset(y + n);
pa[findset(x + n)] = findset(y + n * 2);
pa[findset(x + n * 2)] = findset(y);
}
}
}
printf("%d\n", ans);
return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50000 * 3 + 10;

int f[MAXN];

int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]);
}

void ad(int x, int y){
int u = find(x);
int v = find(y);
if(u != v)
f[u] = v;
}

int main()
{
int n, k, ans = 0;
cin>>n>>k;
for(int i=1; i<=3*n; i++) f[i] = i;
while(k--){
int d, x, y;
cin>>d>>x>>y;
if(x > n || y > n) {ans++; continue;}
if(d == 1){
if(find(x) == find(y+n) || find(x) == find(y+2*n)){
ans++;
continue;
}
ad(x, y);
ad(x+n, y+n);
ad(x+2*n, y+2*n);
}
else{
if(find(x) == find(y) || find(x) == find(y+2*n)){
ans++;
continue;
}

ad(x, y+n);
ad(x+n, y+2*n);
ad(x+2*n, y);
}
}
cout<<ans;
return 0;
}
一年后

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
#define tz(x) while(x<0) x+=3; x%=3;
pair<int,int> f[50005],w1,w2;
pair<int,int> check(int w,int r)
{
if( f[w].first ==w ) {

pair<int,int> z;
tz(r);
z.first =w; z.second =r;
return z;
}

return check(f[w].first,r+f[w].second);
}
void out(int n)
{
FOR(i,1,n)
{
if(f[i].first!=i)

{ printf(" %d [%d] %d " ,i,f[i].second,f[i].first);}
}

}
int main()
{ int ans=0,d,x,y,n,k;
scanf("%d%d",&n,&k);
FOR(i,1,n) { f[i].first=i; f[i].second=0;}
FOR(i,1,k)
{
scanf("%d%d%d",&d,&x,&y);
if(x==y&&d==2) {ans++; continue;}
if(x>n||y>n) {ans++; continue;}
f[x]=check(x,0); f[y]=check(y,0);
if(f[x].first!=f[y].first) {

f[ f[x].first ].second =-f[x].second+(d-1)+f[y].second;
f[ f[x].first ].first =f[y].first;
tz( f[ f[x].first ].second ); continue;
}
else {

if( ( -f[x].second+(d-1)+f[y].second+9) %3!=0 ) {ans++; continue;}
}

}
printf("%d",ans);
return 0;
}

编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

Accepted 有效得分：100 有效耗时：0ms
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 50000*3+10;

int f[MAXN];

void init(int n){
for(int i=1; i<=3*n; i++)
f[i] = i;
}

int find(int x){
if(f[x] != x)
return f[x]=find(f[x]);
return x;
}

bool same(int x, int y){
return find(x) == find(y);
}

void add(int x, int y){
int u = find(x);
int v = find(y);
if(u != v)
f[u] = v;
}
orz
int main()
{
int n, k, d , x, y,ans=0;

scanf("%d%d",&n,&k);
init(n);
while(k--){
scanf("%d%d%d",&d,&x,&y);
if(x>n || y>n){
ans++;

continue;

}

if(d == 1){

if(same(x, y+n) || same(x, y+2*n))
ans++;
else{
add(x, y);

add(x+n, y+n);
add(x+2*n, y+2*n);

}
}
else{
if(same(x, y) || same(x, y+2*n))
ans++;
else{
add(x, y+n);

add(x+n, y+2*n);
add(x+2*n, y);

}
}

}
cout<<ans;
system("pause");
return 1;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 50000*3+10;

int f[MAXN];

void init(int n){
for(int i=1; i<=3*n; i++)
f[i] = i;
}

int find(int x){
if(f[x] != x)
return f[x]=find(f[x]);
return x;
}

bool same(int x, int y){
return find(x) == find(y);
}

void add(int x, int y){
int u = find(x);
int v = find(y);
if(u != v)
f[u] = v;
}

int main()
{
int n, k, d , x, y,ans=0;

scanf("%d%d",&n,&k);
init(n);
while(k--){
scanf("%d%d%d",&d,&x,&y);
if(x>n || y>n){
ans++;

continue;

}

if(d == 1){

if(same(x, y+n) || same(x, y+2*n))
ans++;
else{
add(x, y);

add(x+n, y+n);
add(x+2*n, y+2*n);

}
}
else{
if(same(x, y) || same(x, y+2*n))
ans++;
else{
add(x, y+n);

add(x+n, y+2*n);
add(x+2*n, y);

}
}

}
cout<<ans;
system("pause");
return 0;
}
感谢大神点播~~

并查集，细节

测试数据 #0: Accepted, time = 0 ms, mem = 2116 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2120 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2120 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2120 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2116 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2120 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 2116 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 2120 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 2116 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 2124 KiB, score = 10
Accepted, time = 200 ms, mem = 2124 KiB, score = 100
#include<iostream>
#include<cstdio>
using namespace std;
const int maxd=50005;
const int maxb=100005;
int numd,numb;
int sum=0;
int rel[maxd]={0};
int fa[maxd];
struct m
{
int r;
int x;
int y;
}; m k[maxb];
int anti(int x)
{
if(x==2)
return 0;
if(x==0)
return 2;
return 1;
}
int get(int x)
{
int xroot=x;
int xrel=1;
while(fa[xroot]!=xroot)
{

xrel=(xrel+rel[xroot]+2)%3;
xroot=fa[xroot];
}
int lr=1;
while(x!=xroot)
{
int tfa=fa[x];
int trel=rel[x];
rel[x]=(lr+xrel+2)%3;
xrel=rel[x];
lr=anti(trel);
fa[x]=xroot;
x=tfa;
}
return xroot;
}
void link(int x,int y,int r)
{
int xroot=get(x);
int yroot=get(y);
rel[xroot]=(anti(rel[x])+r+rel[y]+1)%3;
fa[xroot]=yroot;
}
void work()
{
for(int i=1;i<=numb;i++)
{
if(k[i].x==k[i].y&&k[i].r==2)
{
sum++;
continue;
}
if(k[i].x>numd||k[i].y>numd)
{
sum++;
continue;
}
int xroot=get(k[i].x);
int yroot=get(k[i].y);
if(xroot==yroot)
{
if((rel[k[i].x]+anti(rel[k[i].y])+2)%3!=k[i].r)
{
sum++;

continue;
}
}
else
link(k[i].x,k[i].y,k[i].r);
}

}
int main()
{
int a,b;
scanf("%d%d",&numd,&numb);
for(int i=1;i<=numd;i++)
{
fa[i]=i;
rel[i]=1;
}
for(int i=1;i<=numb;i++)
scanf("%d%d%d",&k[i].r,&k[i].x,&k[i].y);
work();
printf("%d\n",sum);
return 0;
}
居然是因为少加了一组括号。。。。。。。调了这么长时间

#include<iostream>
using namespace std;
int f[501000]={0},l[501000]={0},t[501000]={0};
int g(int x)
{
int i=x,j,k;
for(;f[i];i=f[i]);
for(j=x;f[j];k=f[j],f[j]=i,j=k);
return i;
}
int m(int x,int y)
{
if(!x)
return y;
if(!y)
return x;
return f[y]=x;
}
main()
{
int a,b,c,n,k,s=0,d,x,y,u,v;
cin>>n>>k;
while(k--)
{
cin>>d>>x>>y;
if(x>n||y>n)
{
s++;
continue;
}
u=g(x);
v=g(y);
if(d==1)
{
if(u==v)
continue;
if(l[u]==v||t[u]==v)
{
s++;
continue;
}
a=m(u,v);
b=m(l[u],l[v]);
c=m(t[u],t[v]);
t[a]=c;
t[c]=b;
t[b]=a;
l[a]=b;
l[b]=c;
l[c]=a;
}
else
{
if(t[u]==v)
continue;
if(u==v||l[u]==v)
{
s++;
continue;
}
a=m(u,l[v]);
b=m(t[u],v);
c=m(l[u],t[v]);
t[a]=b;
t[b]=c;
t[c]=a;
l[a]=c;
l[c]=b;
l[b]=a;
}
}
cout<<s;
}

把一个点拆成三个不就好了。。。（但是没搞懂为什么是三个。。。）

#include <cstdio>
#include <cstring>

const int maxn = 501000 ;

int father[ maxn ] , lst[ maxn ] , nxt[ maxn ] , N , K , ans = 0 ;

inline int getfa( int x ) {
int i = x ; for ( ; father[ i ] ; i = father[ i ] ) ;
for ( int j = x , k ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;
return i ;
}

inline int merge( int x , int y ) {
if ( ! x ) return y ;
if ( ! y ) return x ;
return father[ y ] = x ;
}

int main( ) {
memset( father , 0 , sizeof( father ) ) ;
memset( lst , 0 , sizeof( lst ) ) ;
memset( nxt , 0 , sizeof( nxt ) ) ;
scanf( "%d%d" , &N , &K ) ;
while ( K -- ) {
int d , x , y ; scanf( "%d%d%d" , &d , &x , &y ) ;
if ( x > N || y > N ) {
++ ans ; continue ;
}
int u = getfa( x ) , v = getfa( y ) ;
if ( d == 1 ) {
if ( u == v ) continue ;
if ( lst[ u ] == v || nxt[ u ] == v ) {
++ ans ; continue ;
}
int a = merge( u , v ) , b = merge( lst[ u ] , lst[ v ] ) , c = merge( nxt[ u ] , nxt[ v ] ) ;
nxt[ a ] = c , nxt[ c ] = b , nxt[ b ] = a ;
lst[ a ] = b , lst[ b ] = c , lst[ c ] = a ;
} else {
if ( nxt[ u ] == v ) continue ;
if ( u == v || lst[ u ] == v ) {
++ ans ; continue ;
}
int a = merge( u , lst[ v ] ) , b = merge( nxt[ u ] , v ) , c = merge( lst[ u ] , nxt[ v ] ) ;
nxt[ a ] = b , nxt[ b ] = c , nxt[ c ] = a ;
lst[ a ] = c , lst[ c ] = b , lst[ b ] = a ;
}
}
printf( "%d\n" , ans ) ;
return 0 ;
}

这个题我弄了很久啊
终于AC了。。
两种解法思路点拨+AC代码