当前位置 : 主页 > 网页制作 > HTTP/TCP >

PTA 甲级 1139

来源:互联网 收集:自由互联 发布时间:2021-06-16
https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312 其实这道题目不难,但是有很多坑点! 首先数据是性别+id,id不是数字! 输出的时候必须前面补0, 另外什么自己和自己连边

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;
}
网友评论