1 条题解
-
0
注意: 1.如果一名司机知道了甲司机的情况。则与乙相遇时,则自己所知道的所有消息都告诉乙(即是自己和甲的消息) 2.每条线路是循环开的。即是最后一个站点是与第一个站点相连的.
思路: 主要是用了暴力的搜索,因为数据量不大。过程中,遇到要解模方程的,鉴于数据量不大,用了一个遍历,减少了代码量。主要说明代码中有体现。这道关键是数据结构的,要组织好数据。
#include<iostream> #include<cstdio> //poj上要加上这句,不然会CE. using namespace std; int n, m, k; // n是线路 ,m是司机人数 ,k是站的个数。 int path [ 20 ] [ 30 ]; //path[i]表示第i个路线经过的站点。 int n_path [ 20 ]; //表示第i条路线的站点个数。 int visitor [ 30 ] [ 2 ]; //表示第i个司机在第[0]个起点,在[1]个条线上。 int ans [ 1000 ]; //辅助变量 int visit [ 30 ] [ 30 ]; //表示i是不是得到j的消息 。 void solve ( int s, int t ) { int i, j; int check; //检查i,j所在线上有没有相同的起点。check来标志 int p = visitor [s ] [ 1 ]; //s的所在线 int q = visitor [t ] [ 1 ]; //t的所在线。 int starts = visitor [s ] [ 0 ]; //s的起点 int startt = visitor [t ] [ 0 ]; //t的起点。 if (p == q ) { if (starts == startt ) { check = 1; } else return; } else { check = 0; for (i = 0; i < n_path [p ]; i++ ) { for (j = 0; j < n_path [q ]; j++ ) { if (path [p ] [i ] == path [q ] [j ] ) { //说明两条线上有相同的站点。 for (k = 0; k < 100; k++ ) { if ( (path [p ] [ (starts + k ) % n_path [p ] ] == path [p ] [i ] ) && (path [q ] [ (startt + k ) % n_path [q ] ] == path [p ] [i ] ) ) { check = 1; break; } } if (check == 1 ) break; } } if (check == 1 ) break; } if (check == 0 ) return ; } //说明两者相遇 //p与q的所有消息 。 visit [s ] [t ] = 1; for (j = 1; j <= m; j++ ) { if (visit [s ] [j ] == 1 || visit [j ] [s ] == 1 ) { visit [t ] [j ] = visit [j ] [t ] = 1; } } visit [t ] [s ] = 1; for (j = 1; j <= m; j++ ) { if (visit [t ] [j ] == 1 || visit [j ] [t ] == 1 ) { visit [s ] [j ] = visit [j ] [s ] = 1; } } } int main ( ) { char str [ 100 ]; int i, j, k; int num; int s; while (cin >> n >> m >> k ) { if (n == 0 && m == 0 && k == 0 ) break; getchar ( ); //初始化 for (i = 1; i <= m; i++ ) { for (j = 1; j <= m; j++ ) { if (i == j ) visit [i ] [j ] = 1; else visit [i ] [j ] = 0; } } for (i = 0; i < n; i++ ) { //输入站点 的。 gets (str ); n_path [i ] = 0; k = 0; s = 0; for (j = 0; str [j ] != '/0'; j++ ) { if (str [j ] == ' ' ) { path [i ] [n_path [i ] ] = s; n_path [i ]++; s = 0; } else { s = str [j ] - '0' + s * 10; } } path [i ] [n_path [i ] ] = s; n_path [i ]++; gets (str ); num = 0; s = 0; for (j = 0; str [j ] != '/0'; j++ ) { if (str [j ] == ' ' ) { ans [num++ ] = s; s = 0; } else s = str [j ] - '0' + s * 10; } ans [num++ ] = s; for (j = 0; j < num; j += 2 ) { for (k = 0; k < n_path [i ]; k++ ) { if (ans [j ] == path [i ] [k ] ) { ans [j ] = k; break; } } visitor [ans [j + 1 ] ] [ 0 ] = ans [j ]; visitor [ans [j + 1 ] ] [ 1 ] = i; } } // for(i=1;i<=m;i++) cout<<visitor[i][0]<<" "<<visitor[i][1]<<endl; /// 解决输入问题。下面解决问题。 for (i = 1; i <= m; i++ ) { //看i能不能得到j的消息 。 for (j = i + 1; j <= m; j++ ) { //判断i是不是能得到j的消息 。 solve (i, j ); } } int key = 1; for (i = 1; i <= m; i++ ) { for (j = 1; j <= m; j++ ) { if (visit [i ] [j ] == 0 ) { key = 0; break; } } if (key == 0 ) break; } if (key ) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
- 1
信息
- ID
- 371
- 时间
- 1000ms
- 内存
- 10MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者