UVA11175 有向图D和E From D to E and Back
题目描述
采用任意有n个顶点和m个边的有向图D. 您可以通过以下方式制作D的Lying图E. E将有m个顶点，每个用于表示D的每个边。例如，如果D具有边(u,v)，则E将具有称为uv的顶点。现在，每当D具有边(u,v)和(v,w)时，E将具有从顶点uv到顶点vw的边。 E中没有其他边。您将获得一个图E，并且必须确定E是否可能是某个有向图D的Lying图。
输入
输入的第一行给出案例数N (N < 220)。接下来是N个测试用例。每一个开始两行分别包含m(0≤m≤300)和k。接下来的k行每一行包含一对顶点，即e中存在一条从x到y的边。顶点编号从0到m−1.
输出
对于每个测试用例，输出一行包含’ case #x: ‘，后面跟着’ Yes ‘或’ No '，具体取决于具体情况,E是否是一个有效的Lying图。注意，D允许有重复的边和自边。
输入样例
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
输出样例
Case #1: Yes
Case #2: Yes
Case #3: No
Case #4: Yes
题目分析
这个题主要考察图的临界矩阵的使用
①实际上就是把有向图D中得边缩点，有向图D中得一条边对应图E中得一个点，如果存在D具有边(u,v)和(v,w)时，E将具有从顶点uv到顶点vw的边。
如图所示:
②题目的意思是判断给出的E是不是可能存在？我们分析下：如果i边和j边有公共端点，则i能到达的的边j也一定能到达。不存在i能到达，j不能到达的情况。下图中E图i,j存在公共点,这时候E图中i能到达的点,j也能到达.所以最后一个E图不成立,是错的.
3.因为这个题中我们需要不断的判断两个顶点之间是否存在边，所以使用邻接矩阵比较方便。
代码演示
#include<bits/stdc++.h> using namespace std; const int maxn = 320; int N,m,k,case1,arr[maxn][maxn],u,v; bool flag,flag2; bool solve(){ for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ flag = false,flag2 = false; for(int k = 0; k < m; k++){ if(arr[i][k]&&arr[j][k]){ flag = true; } if(arr[i][k]^arr[j][k]){ flag2 = true; } } if(flag&&flag2){ return false; } } } return true; } int main() { cin>>N; while(N--){ memset(arr,0,sizeof(arr)); cin>>m>>k; for(int i = 0; i < k; i++){ cin>>u>>v; arr[u][v] = 1; } if(solve()){ cout<<"Case #"<<++case1<<": "<<"Yes"<<endl; }else{ cout<<"Case #"<<++case1<<": "<<"No"<<endl; } } return 0; }
自己该开始写的solve方法，存在一些问题。
bool solve2(){//自己刚开始写的代码，有点小坑。公共点的判断和 i - -k> j-/-> k判断不能放在一起。 for(int i = 0; i < m; i++){ for(int j = 0; j < m; j++){ flag = false; for(int k = 0; k < m; k++){ if(arr[i][k]&&arr[j][k]){ flag = true; } if(flag&&((arr[i][k]&&!arr[j][k])||(!arr[i][k]&&(arr[j][k])))){//如果这样写可能会出现检测不到的情况,如flag为true的情况在最后几次循环出现,而之前也出现过i-->k j-/->k的情况. //所以应该分开进行讨论. 而且只有一个成立还可以用^ return false; } } } } return true; }
代码分析
首先这个题中判断两顶点边的次数较多,所以应使用邻接矩阵.
判断(i , k), (j , k) 边是否存在时,涉及到了三个变量,所以应该使用三层循环,一个变,另外两个不变.
此题精妙之处在于判断是否存在k,当i,j有公共顶点时,如果 (i , k ),(j , k)
中,只有一个成立,说明该E图不能由D图化来.原因在于:前面说过了.为此可以用 ^ 来实现,当两个条件只有一个成立时,便为真.
心得收获
如果题中循环过多,也可以采用宏定义的方式.
#define REP(i,b,e) for(int i=(b);i<(e);i++) ==>>for(int i = b; i <= e; i++)
- ^ 的使用:当两个条件只有一个成立结果为真.
