HUNNU11684 重重叠叠（map + pair）

重重叠叠

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

Sample Output

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 星期三