hdu 5961 传递 (2016ccpc 合肥站 A题)

传递

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 753 Accepted Submission(s): 335

Problem Description

我们称一个有向图G是传递的，当且仅当对任意三个不同的顶点a,,若G中有一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。
我们称图G是一个竞赛图，当且仅当它是一个有向图且它的基图是完全图。换句话说，将完全图每条边定向将得到一个竞赛图。
下图展示的是一个有4个顶点的竞赛图。

现在，给你两个有向图P = $(V,

Input

包含至多20组测试数据。
第一行有一个正整数，表示数据的组数。
对于每组数据，第一行有一个正整数n。接下来n行，每行为连续的n个字符，每个字符只可能是’-’,’P’,’Q’中的一种。

Output

对每个数据，你需要输出一行。如果P! Q都是传递的，那么请输出’T’。否则，请输出’N’ (均不包括引号)。

Sample Input

4 4

-PPP

--PQ

---Q

----

-P-P

--PQ

P--Q

----

-PPP

--QQ

----

--Q-

-PPP

--PQ

----

--Q-

Sample Output

Hint

在下面的示意图中，左图为图为Q。

注：在样例2中，P不是传递的。在样例4中，Q不是传递的。

Source

2016年中国大学生程序设计竞赛（合肥）-重现赛（感谢安徽大学）

Recommend

jiangzijing2015

比赛的时候没做出来，其实也是水题，就是对所有顶点bfs，看是否有bfs深度为2的顶点。然后卡卡时就可以过了。

代码如下

  1 #include<cstdio>
  2 #include<iostream> 
  3 #include<cstring>
  4 #include<queue>
  5 #include<vector>
  6 #define clr(x) memset(x,0,sizeof(x))
  7 using namespace std;
  8 int inf[2500];
  9 vector<int> map1[2500],map2[2500];
 10 queue<int> que;
 11 bool bfs1();
 12 bool bfs2(); 
 13 int main()
 14 {
 15     int T;
 16     scanf("%d",&T);
 17     int n,m;
 18     int flag1,flag2;
 19     char c;
 20     while(T--)
 21     {
 22         scanf("%d",&n);
 23         for(int i=1;i<=n;i++)
 24         {
 25             map1[i].clear();
 26             map2[i].clear();
 27         }
 28         for(int i=1;i<=n;i++)
 29         {
 30             for(int j=1;j<=n;j++)
 31             {
 32                 scanf(" %c",&c);
 33                 if(c=='P')
 34                 {
 35                     map1[i].push_back(j);
 36                 }
 37                 if(c=='Q')
 38                 {
 39                     map2[i].push_back(j);
 40                 }                
 41             }
 42         }
 43         flag1=1;
 44         flag2=1;
 45         while(!que.empty())
 46             que.pop();
 47         for(int i=1;i<=n;i++)
 48         {
 49             clr(inf);
 50             inf[i]=1;
 51             for(int j=0;j<map1[i].size();j++)
 52             {
 53                 inf[map1[i][j]]=1;
 54                 que.push(map1[i][j]);
 55             }
 56             if(!bfs1())
 57             {
 58                 flag1=0;
 59                 break;
 60             }
 61         }
 62         if(que.empty())
 63         for(int i=1;i<=n;i++)
 64         {
 65             clr(inf);
 66             inf[i]=1;
 67             for(int j=0;j<map2[i].size();j++)
 68             {
 69                 inf[map2[i][j]]=1;
 70                 que.push(map2[i][j]);
 71             }
 72             if(!bfs2())
 73             {
 74                 flag2=0;
 75                 break;
 76             }
 77         }
 78         if(flag2==0 || flag1==0)
 79         {
 80             printf("N
");
 81         }
 82         else
 83             printf("T
");
 84     }
 85     return 0;
 86 }
 87 bool bfs1()
 88 {
 89     int m; 
 90     while(!que.empty())
 91     {
 92         m=que.front();
 93         que.pop();
 94         for(int j=0;j<map1[m].size();j++)
 95             if(inf[map1[m][j]]==0)
 96             {
 97                 return 0;
 98             }
 99     }
100     return 1;
101 }
102 bool bfs2()
103 {
104     int m;
105     while(!que.empty())
106     {
107         m=que.front();
108         que.pop();
109         for(int j=0;j<map2[m].size();j++)
110             if(inf[map2[m][j]]==0)
111             {
112                 return 0;
113             }
114     }
115     return 1;
116 }