昆明网站建设c3sales,证件查询网入口,中国石化工程建设公司网站,如何创建网址免费注册题干#xff1a;
我们称一个有向图G是传递的#xff0c;当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 我们称图G是一个竞赛图#xff0c;当且仅当它是一个有向图且它的基图是完全图。换句 话说#xff0c;将完全图每…题干
我们称一个有向图G是传递的当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 我们称图G是一个竞赛图当且仅当它是一个有向图且它的基图是完全图。换句 话说将完全图每条边定向将得到一个竞赛图。 下图展示的是一个有4个顶点的竞赛图。 现在给你两个有向图P (V,Ep)和Q (V,Ee)满足: 1. EP与Ee没有公共边 2. (V,Ep⋃Ee)是一个竞赛图。 你的任务是判定是否PQ同时为传递的。 Input
包含至多20组测试数据。 第一行有一个正整数表示数据的组数。 对于每组数据第一行有一个正整数n。接下来n行每行为连续的n个字符每 个字符只可能是’-’,’P’,’Q’中的一种。 ∙如果第i行的第j个字符为’P’表示有向图P中有一条边从i到j; ∙如果第i行的第j个字符为’Q’表示有向图Q中有一条边从i到j; ∙否则表示两个图中均没有边从i到j。 保证1 n 2016一个测试点中的多组数据中的n的和不超过16000。保证输入的图一定满足给出的限制条件。 Output
对每个数据你需要输出一行。如果P! Q都是传递的那么请输出’T’。否则 请输出’N’ (均不包括引号)。
Sample Input
4 4 -PPP --PQ ---Q ---- 4 -P-P --PQ P--Q ---- 4 -PPP --QQ ---- --Q- 4 -PPP --PQ ---- --Q-
Sample Output
T N T N
Hint
在下面的示意图中左图为图为Q。 注在样例2中P不是传递的。在样例4中Q不是传递的。
解题报告
让你求边的传递关系考虑到每一对关系只涉及三个点a-b-c所以枚举中间那个点b然后枚举abitset直接看c就可以了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includebitset
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2016 5;
char s[MAX][MAX];
bitsetMAX bs[MAX];
struct Node {int to,ne;
} e[MAX*MAX],f[MAX*MAX];
int tot,totf,head[MAX],headf[MAX],n;
void add(int u,int v) {e[tot].to v;e[tot].ne head[u];head[u] tot;
}
void addf(int u,int v) {f[totf].to v;f[totf].ne headf[u];headf[u] totf;
}
int main()
{int T;cinT;while(T--) {scanf(%d,n);tottotf0;for(int i 1; in; i) head[i] headf[i] -1;for(int i 1; in; i) {scanf(%s,s[i]1); }int flag 1;//PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPfor(int i 1; in; i) {bs[i].reset();for(int j 1; jn; j) {if(s[i][j] P) add(i,j),addf(j,i),bs[i][j]1;}}for(int v 1; vn; v) {for(int i headf[v]; ~i; i f[i].ne) {int u f[i].to;if((bs[v]bs[u]) ! bs[v]) {flag 0;break;}}if(flag 0) break;}if(flag 0) {printf(N\n);continue;}tottotf0;for(int i 1; in; i) head[i] headf[i] -1;for(int i 1; in; i) {bs[i].reset();for(int j 1; jn; j) {if(s[i][j] Q) add(i,j),addf(j,i),bs[i][j]1;}}for(int v 1; vn; v) {for(int i headf[v]; ~i; i f[i].ne) {int u f[i].to;if((bs[v]bs[u]) ! bs[v]) {flag 0;break;}}if(flag 0) break;}if(flag 0) {printf(N\n);continue;}else printf(T\n);}return 0 ;
}
