MENU

HUNNU11684 重重叠叠(map + pair)

2018 年 06 月 06 日 • 阅读: 941 • 练习阅读设置

重重叠叠

  • Time Limit: 2000ms
  • Memory Limit:32768KB
  • Total submit users: 31
  • Accepted users: 18

Problem description

图G是(V, E)的二元组,其中V表示顶点的集合,E表示边的集合。每一条边使用一个点对表示。此处仅考虑无向边,即点对的顺序并不重要。
如果一对顶点之间(未必是相异顶点),存在多条边,则称这些边为平行边,平行边的条数称为重数。在一个图中,重数最大的顶点对的重数,称之为图的重数。
给定一个图,求其重数。

Input

输入有多个案例(不超过100个)。每个案例的第一行是2个非负整数N和M,其取值范围均为[0, 10000],分别表示点的数量和边的数量。第二行是2M个数,每个数后面均有一个空格以示分隔,每个数的取值范围均为[1, N]。这2M个数依次形成M个数对,每个数对a和b表示a、b之间存在一条边。

Output

每个案例输出一行,为答案。

Sample Input

3 3
1 2
2 1
1 3

Sample Output

2

Problem Source

湖南师范大学第八届大学生计算机程序设计竞赛


链接

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11684


题意

求无向图中任意一对顶点间的边数的最大值(可能存在自环)。

题解

因为顶点n的范围达到10000,所以没法用邻接矩阵。但是边的数量才到10000。我们可以用pair来表示边,使用map存储。map <pair<int, int>, int> edge;,然后就没有然后了...

代码

  • 1504KB
  • 890ms
  • 592B
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;

map <pair<int, int>, int> edge;

int main()
{
    int n, m, u, v, ans;
    while (~scanf("%d%d", &n, &m))
    {
        ans = 0;
        edge.clear();
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d", &u, &v);
            if (u > v)
                swap(u, v);
            edge[make_pair(u, v)]++;
            ans = max(ans, edge[make_pair(u, v)]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

忘了是多组样例WA了一次...顺便复习一下map和pair。


The end.
2018-06-06 星期三