【NOI 2000/codevs 1074/tyvj 1438】食物連鎖解題報告
2713 ワード
【NOI 2000/codevs 1074/tyvj 1438】食物連鎖解題報告
説明
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.AはBを食べ、BはCを食べ、CはAを食べる.
既存のN個の動物は、1−Nで番号付けされている.どの動物もA,B,Cの一種ですが、どれなのか分かりません.
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる.
1つ目の言い方は「1 X Y」で、XとYが同類であることを表す.
2つ目の言い方は「2 X Y」で、XがYを食べることを意味します.
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです.
1)現在の話は前のいくつかの本当の話と衝突し、うそである.
2)現在の話ではXやYがNより大きく、うそである.
3)現在の言葉はXがXを食べることを意味し,うそである.
あなたの任務は、与えられたN(1<=N<=50000)とK文(0<=K<=10000000)に基づいて、偽話の総数を出力することです.
入力フォーマット
最初の行は2つの整数NとKで、1つのスペースで区切られています.
以下のK行は、行ごとに3つの正の整数D,X,Yであり、2つの数の間に1つのスペースで区切られており、Dは言い方の種類を表す.
D=1であれば、XとYは同類であることを示す.
D=2なら、XがYを食べることを表す.
出力フォーマット
うその数を表す整数は1つしかありません.
試験例1
入力
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
しゅつりょく
3
コメント
入力ファイル対7文の分析
100 7
1 101嘘
2 1 2本当のこと
2 2 3本当の話
2 3うそ
1 1 3うそ
2 3 1本当の話
1 5 5真実NOI 2001食物連鎖(eat)
【問題解きの考え方】
自分で+先生の话を闻いて+问题解を见て+コードを书きます=AC;
私の自信を暴いて集めた问题...
见た问题解は虚点+で调べてみたが、今はまだ虚点が何なのか分からない...よろしくお愿いします
しかし、問題解の構想は理解できた.の
1~nはn種の動物の同類集合であり、n+1~n+はこの動物の天敵集合であり、n*2+1~3*nはこの動物の食物集合である.
もしD==1:うそを判断する方法は:Xの食べ物の集合の中にYがあって、あるいはYの食べ物の集合の中にXがあって、あるいはXの天敵の集合の中にYがあって、あるいはYの天敵の集合の中にXがあります;合併の方法は、Xの同類集合とYの同類集合を合併し、Xの天敵集合とYの天敵集合を合併し、Xの食物集合とYの食物集合を合併する.
もしD==2:うそを判断する方法は、Xの天敵の集合にYがあるか、Yの食べ物の集合にXがあるか.合併の方法は、XとYの天敵が集合し、YとXの食物が集合し、Xの天敵が集合してYの食物が集合する(題意から分かるように、ZがXの天敵であれば、YがXの食物であれば、ZはYの食物である).
【コード】
説明
動物王国には3種類の動物A,B,Cがあり,この3種類の動物の食物連鎖は興味深い環状を構成している.AはBを食べ、BはCを食べ、CはAを食べる.
既存のN個の動物は、1−Nで番号付けされている.どの動物もA,B,Cの一種ですが、どれなのか分かりません.
このN個の動物が構成する食物連鎖関係を2つの説で説明する人がいる.
1つ目の言い方は「1 X Y」で、XとYが同類であることを表す.
2つ目の言い方は「2 X Y」で、XがYを食べることを意味します.
この人はN個の動物に対して、上記の2つの言い方を使って、次から次へとK文の言葉を言って、このK文の言葉はあるのは本当で、あるのは偽物です.一言が次の3つの1つを満たすと、この言葉はうそで、そうでなければ本当のことです.
1)現在の話は前のいくつかの本当の話と衝突し、うそである.
2)現在の話ではXやYがNより大きく、うそである.
3)現在の言葉はXがXを食べることを意味し,うそである.
あなたの任務は、与えられたN(1<=N<=50000)とK文(0<=K<=10000000)に基づいて、偽話の総数を出力することです.
入力フォーマット
最初の行は2つの整数NとKで、1つのスペースで区切られています.
以下のK行は、行ごとに3つの正の整数D,X,Yであり、2つの数の間に1つのスペースで区切られており、Dは言い方の種類を表す.
D=1であれば、XとYは同類であることを示す.
D=2なら、XがYを食べることを表す.
出力フォーマット
うその数を表す整数は1つしかありません.
試験例1
入力
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
しゅつりょく
3
コメント
入力ファイル対7文の分析
100 7
1 101嘘
2 1 2本当のこと
2 2 3本当の話
2 3うそ
1 1 3うそ
2 3 1本当の話
1 5 5真実NOI 2001食物連鎖(eat)
【問題解きの考え方】
自分で+先生の话を闻いて+问题解を见て+コードを书きます=AC;
私の自信を暴いて集めた问题...
见た问题解は虚点+で调べてみたが、今はまだ虚点が何なのか分からない...よろしくお愿いします
しかし、問題解の構想は理解できた.の
1~nはn種の動物の同類集合であり、n+1~n+はこの動物の天敵集合であり、n*2+1~3*nはこの動物の食物集合である.
もしD==1:うそを判断する方法は:Xの食べ物の集合の中にYがあって、あるいはYの食べ物の集合の中にXがあって、あるいはXの天敵の集合の中にYがあって、あるいはYの天敵の集合の中にXがあります;合併の方法は、Xの同類集合とYの同類集合を合併し、Xの天敵集合とYの天敵集合を合併し、Xの食物集合とYの食物集合を合併する.
もしD==2:うそを判断する方法は、Xの天敵の集合にYがあるか、Yの食べ物の集合にXがあるか.合併の方法は、XとYの天敵が集合し、YとXの食物が集合し、Xの天敵が集合してYの食物が集合する(題意から分かるように、ZがXの天敵であれば、YがXの食物であれば、ZはYの食物である).
【コード】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=350005;
int n,m,i,ans,a1,b1,c1,maxp;
int fa[MAXN];
int findf(int x)
{
if (fa[x]==x) return x;
return fa[x]=findf(fa[x]);
}
void unions(int x,int y)
{
if (findf(x)!=findf(y))
fa[fa[x]]=fa[y];
return;
}
int main()
{
scanf("%d%d",&n,&m);
maxp=3*n;
for (i=1;i<=maxp;++i)
fa[i]=i;
for (i=1;i<=m;++i)
{
scanf("%d%d%d",&a1,&b1,&c1);
if (b1>n||c1>n||b1==c1&&a1==2)
{
ans++;
continue;
}
if (a1==1)
{
if (findf(b1)==findf(n+c1)||findf(b1)==findf(n*2+c1)||findf(n+b1)==findf(c1)||findf(n*2+b1)==findf(c1))
{
++ans;
continue;
}
unions(b1,c1);
unions(n+b1,n+c1);
unions(n*2+b1,n*2+c1);
}
if (a1==2)
{
if (findf(b1)==findf(c1)||findf(b1)==findf(n+c1)||findf(n*2+b1)==findf(c1))
{
++ans;
continue;
}
unions(b1,n*2+c1);
unions(n+b1,c1);
unions(n*2+b1,n+c1);
}
}
printf("%d
",ans);
return 0;
}