1 条题解

  • 0
    @ 2025-4-17 17:14:05

    注意: 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
    上传者