11175-From D to E and Back（思维）

Problem UVA11175-From D to E and Back

Accept: 164 Submit: 607
Time Limit: 3000 mSec

Problem Description

Take any directed graph D with n vertices and m edges. You can make the Lying graph E of B in the following way. E will have m vertices, one for each edge of D. For example, if D has an edge uv, then E will have a vertex called uv. Now, whenever D has edges uv and vw, E will have an edge from vertex uv to vertex vw. There are no other edges in E. You will be given a graph E and will have to determine whether it is possible for E to be the Lying graph of some directed graph D.

Input

The ﬁrst line of input gives the number of cases, N (N < 220). N test cases follow. Each one starts with two lines containing m (0 ≤ m ≤ 300) and k. The next k lines will each contain a pair of vertices, x and y, meaning that there is an edge from x to y in E. The vertices are numbered from 0 to m−1

Output

For each test case, output one line containing ‘Case #x:’ followed by either ‘Yes’ or ‘No’, depending on whether E is a valid Lying graph or not. Note that D is allowed to have duplicate edges and self-edges.

Sample Input

4 2 1 0 1 5 0 4 3 0 1 2 1 2 3 3 9 0 1 0 2 1 2 1 0 2 0 2 1 0 0 1 1 2 2

Sample Output

Case #1: Yes

Case #2: Yes

Case #3: No

Case #4: Yes

题解：这种结论题真的是做不来。首先第一感觉是这怎么会不存在呢，然后样例三强势打脸，但是感觉上不成立的情况应该很少，但是少到何种程度完全没有认识，最后思来想去还是看了题解，题解都是千篇一律的结论，并且没有人证明那是充要的，至多证明是必要的，做这个题就当涨见识了。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 int gra[maxn][maxn];

 int m, t;

 int read() {

     int q = ;

     char ch = ' ';

     while (ch<'' || ch>'') ch = getchar();

     while ('' <= ch && ch <= '') {

         q = q *  + ch - '';

         ch = getchar();

     }

     return q;

 }

 bool solve() {

     for (int i = ; i < m; i++) {

         for (int j = ; j < m; j++) {

             int f1 = , f2 = ;

             for (int k = ; k < m; k++) {

                 if (gra[i][k] && gra[j][k]) f1 = ;

                 if (gra[i][k] ^ gra[j][k]) f2 = ;

                 if (f1 && f2) return false;

             }

         }

     }

     return true;

 }

 int T = ;

 int main()

 {

     int iCase;

     iCase = read();

     while (iCase--) {

         memset(gra, , sizeof(gra));

         m = read(), t = read();

         int u, v;

         for (int i = ; i < t; i++) {

             u = read(), v = read();

             gra[u][v] = ;

         }

         printf("Case #%d: ",T++);

         if (solve()) printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }

巴特西

11175-From D to E and Back（思维）

Accept: 164 Submit: 607
Time Limit: 3000 mSec

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

11175-From D to E and Back（思维）

Accept: 164 Submit: 607Time Limit: 3000 mSec

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

Accept: 164 Submit: 607
Time Limit: 3000 mSec