白駿アルゴリズム15723号:n段説
15140 ワード
リンク
https://www.acmicpc.net/problem/15723
質問する
中央大学コンピュータ工学部(ソフトウェア学部)の学生はみな美人だ.
季武勤は中央大学コンピュータ工学部の学生です.
だから知木勤は美人です.
上の演繹論証は典型的な三段論法の例である.三段論法とは,二つの前提と一つの結論からなる演繹論証である.これを適用すると,n個の前提がある場合,m個の結論が得られる.このときのnとmはすべての意味で適切な数であると仮定する.詳細については、I/Oの例を参照してください.
入力
第1行は整数n(2≦n≦26)を与える.
2行目から、各行に前提があります.前提はすべてa is bの形式で与えられて、aとbは異なる任意のアルファベットの小文字です.特に指示はありませんが、すべての前提は「すべてのaはb」です.しかし、「すべてのbがaである」という意味は不可能です.また、aはbであってcであってはならないが、aとbは同時にcであってもよい.
n+2行は整数m(1≦m≦10)を与える.次に、m行では、各行に前提と同じ形式で結論が与えられる.
しゅつりょく
m行では、各行が結論を出すのは本当かどうか.もし本当にTならば、偽物ならFを出力します.未知の状況も偽物だ.答えは大文字でなければなりません.
入力と出力の例
解法
簡単に言えば、A->Bへ行く経路がINFでなければ、T、INFであればFを出力します.:)
プールコード(C++)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 27
#define INF 1000000000
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
int dist[MAX][MAX];
void resetGraph(){
for(int i = 0; i < MAX; i++){
for(int j = 0; j < MAX; j++){
dist[i][j] = INF;
}
}
}
void floyd(){
for(int k = 0; k < MAX; k++){ // k : 거쳐가는 정점
for(int i = 0; i < MAX; i++){ // i : 행(출발 정점)
for(int j = 0; j < MAX; j++){ // j : 열(도착 정점)
// 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int n,m;
int main(){
fastio;
cin >> n;
resetGraph();
char a,b;
string s;
for(int i = 0; i < n; i++){
cin >> a >> s >> b;
dist[a - 'a'][b - 'a'] = 1;
}
cin >> m;
floyd();
while(m--){
char x,y;
string s;
cin >> x >> s >> y;
cout << (dist[x - 'a'][y - 'a'] == INF ? 'F' : 'T') << "\n";
}
return 0;
}
Reference
この問題について(白駿アルゴリズム15723号:n段説), 我々は、より多くの情報をここで見つけました https://velog.io/@inwooleeme/백준-알고리즘-15723번-n단-논법テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol