1090 危险品装箱 (25分)
输入样例:
6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333
输出样例:
No Yes Yes
思路:
1.将每种成对违禁品链起来
2.对每箱货物存储货物编号和其货物是否存在,然后遍历每个货物,看是否有对应的违禁品
首次通过代码:
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef struct node{ 4 int num; 5 struct node*next; 6 }node,*n; 7 8 n initial_node(int x){ 9 n n1=(n)malloc(sizeof(node)); 10 n1->num=x; 11 n1->next=NULL; 12 return n1; 13 } 14 15 int main(){ 16 int x,y; 17 scanf("%d %d",&x,&y); 18 n dan[100005]={NULL}; 19 for(int i=0;i<x;i++){ 20 int x1,x2; 21 scanf("%d %d",&x1,&x2); 22 n n1=initial_node(x2); 23 n n2=initial_node(x1); 24 if(dan[x1]==NULL) dan[x1]=n1; 25 else { 26 n n3=dan[x1]; 27 while(n3->next!=NULL) n3=n3->next; 28 n3->next=n1; 29 } 30 if(dan[x2]==NULL) dan[x2]=n2; 31 else{ 32 n n3=dan[x2]; 33 while(n3->next!=NULL) n3=n3->next; 34 n3->next=n2; 35 } 36 } 37 for(int i=0;i<y;i++){ 38 int k;scanf("%d",&k); 39 int list[100005]={0}; 40 int save[1004]={0}; 41 int flag=0; 42 for(int j=0;j<k;j++){ 43 scanf("%d",&save[j]); 44 list[save[j]]=1; 45 } 46 for(int j=0;j<k;j++){ 47 if(dan[save[j]]!=NULL) { 48 n n1=dan[save[j]]; 49 while(n1!=NULL){ 50 if(list[n1->num]==1) { 51 flag=1;break; 52 } 53 n1=n1->next; 54 } 55 if(flag) break; 56 } 57 } 58 if(flag) printf("No\n"); 59 else printf("Yes\n"); 60 } 61 return 0; 62 }View Code