<address id="hfplr"></address>
        <sub id="hfplr"></sub><address id="hfplr"></address>

          <address id="hfplr"></address>

          PTA 甲级 1139

          https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312

          其实这道题目不难,但是有很多坑点!

          首先数据是性别+id,id不是数字!

          输出的时候必须前面补0,

          另外什么自己和自己连边,重复的边都要注意,

          更注意的是 -0000,这个数据,不能用int来读,我艹

          #include <iostream>
          #include <map>
          #include <algorithm>
          #include <stdio.h>
          #include <stdlib.h>
          #include <math.h>
          #include <string>
          #include <string.h>
          
          using namespace std;
          int n;
          int m;
          
          struct Node
          {
              int value;
              int next;
          
          }edge[200005];
          
          struct Answer
          {
              int a;
              int b;
          
          }res[200005];
          
          int Compare(Answer a,Answer b)
          {
              if(a.a == b.a)
                  return a.b < b.b;
              return a.a < b.a;
          }
          
          map<pair<int,int>,int> dic;
          map<pair<int,int>,int> dic2;
          
          int pos;
          int head[10005];
          
          int gender[10005];
          
          void Add(int x,int y)
          {
              edge[pos].value = y;
              edge[pos].next = head[x];
              head[x] = pos++;
          }
          
          int tag;
          
          void fun(int x,int y)
          {
              tag=0;
          
              dic2.clear();
          
              int i = head[x];
          
              int a[305];
              int j=0;
          
              while(i != -1)
              {
                  if(gender[edge[i].value] == gender[x]
                   && edge[i].value != y && edge[i].value!=x) {
                      a[j++] = edge[i].value;
                  }
          
                  i = edge[i].next;
              }
          
          
              i = head[y];
              int b[305];
              int k=0;
          
              while(i!=-1)
              {
                  if(gender[edge[i].value] == gender[y]
                     && edge[i].value != x && edge[i].value!=y) {
                      b[k++] = edge[i].value;
                  }
          
                  i = edge[i].next;
              }
          
              for(int p=0;p<j;p++)
              {
                  for(int q=0;q<k;q++)
                  {
                      if(a[p]==b[q])
                          continue;
          
                      if(dic[make_pair(a[p],b[q])]==1)
                      {
                          Answer s;
                          s.a = a[p];
                          s.b = b[q];
                          res[tag++] = s;
                      }
                  }
              }
          
              sort(res,res+tag,Compare);
          
              printf("%d\n",tag);
          
              for(int i=0;i<tag;i++)
              {
          
                  printf("%04d %04d\n",res[i].a,res[i].b);
              }
          
          }
          
          
          int main()
          {
              scanf("%d%d",&n,&m);
          
              memset(head,-1,sizeof(head));
              pos=0;
          
              string xx,yy;
              int x;
              int y;
              for(int i=0;i<m;i++)
              {
                  cin>>xx>>yy;
          
          
                   x = atoi(xx.c_str());
                   y = atoi(yy.c_str());
          
          
                  if(x<0 || xx[0]=='-')
                      gender[abs(x)]=-1;
                  else
                      gender[x]=1;
          
                  if(y<0 || yy[0]=='-')
                      gender[abs(y)]=-1;
                  else
                      gender[y]=1;
          
                  x = abs(x);
                  y = abs(y);
          
          
                  if(dic[make_pair(x,y)]==1)
                      continue;
          
                  Add(x,y);
                  Add(y,x);
          
          
                  dic[make_pair(x,y)]=1;
                  dic[make_pair(y,x)]=1;
              }
          
              int k;
              scanf("%d",&k);
          
          
              for(int i=0;i<k;i++)
              {
                  scanf("%d%d",&x,&y);
          
                  x = abs(x);
                  y = abs(y);
          
                  fun(x,y);
              }
              return 0;
          }
          相关文章
          相关标签/搜索
          王中王今晚开什么生肖