题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=12756

Social Holidaying

Time Limit: 3000ms

Memory Limit: 131072KB

This problem will be judged on UVALive. Original ID: 5874
64-bit integer IO format: %lld Java class name: Main

Prev Submit Status Statistics Discuss Next

Font Size: + -

Type:
None

Graph Theory

2-SAT

Articulation/Bridge/Biconnected Component

Cycles/Topological Sorting/Strongly Connected Component

Shortest Path

Bellman Ford

Dijkstra/Floyd Warshall

Euler Trail/Circuit

Heavy-Light Decomposition

Minimum Spanning Tree

Stable Marriage Problem

Trees

Directed Minimum Spanning Tree

Flow/Matching

Graph Matching

Bipartite Matching

Hopcroft–Karp Bipartite Matching

Weighted Bipartite Matching/Hungarian Algorithm

Flow

Max Flow/Min Cut

Min Cost Max Flow

DFS-like

Backtracking with Pruning/Branch and Bound

Basic Recursion

IDA* Search

Parsing/Grammar

Breadth First Search/Depth First Search

Advanced Search Techniques

Binary Search/Bisection

Ternary Search

Geometry

Basic Geometry

Computational Geometry

Convex Hull

Pick's Theorem

Game Theory

Green Hackenbush/Colon Principle/Fusion Principle

Nim

Sprague-Grundy Number

Matrix

Gaussian Elimination

Matrix Exponentiation

Data Structures

Basic Data Structures

Binary Indexed Tree

Binary Search Tree

Hashing

Orthogonal Range Search

Range Minimum Query/Lowest Common Ancestor

Segment Tree/Interval Tree

Trie Tree

Sorting

Disjoint Set

String

Aho Corasick

Knuth-Morris-Pratt

Suffix Array/Suffix Tree

Math

Basic Math

Big Integer Arithmetic

Number Theory

Chinese Remainder Theorem

Extended Euclid

Inclusion/Exclusion

Modular Arithmetic

Combinatorics

Group Theory/Burnside's lemma

Counting

Probability/Expected Value

Others

Tricky

Hardest

Unusual

Brute Force

Implementation

Constructive Algorithms

Two Pointer

Bitmask

Beginner

Discrete Logarithm/Shank's Baby-step Giant-step Algorithm

Greedy

Divide and Conquer

Dynamic Programming

Tag it!

Source

Regionals 2011, Asia - Kuala Lumpur

题目大意：先输入一个P表示有几组测试数据，再输入一个n，m分别表示A、B集合中分别有多少元素。在A集合中找到多少对数相加=B集合中的元素。A集合中的数不可以重复，但是B集合中的数字可以重复出现。

解题思路：二分匹配。先将A集合中的和的所有可能情况列出来，然后在B集合中搜索即可。

详见代码。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int ss[],Map[][];

 int ok[],vis[];

 int a[],b[];

 int n,m;

 bool Find(int x)

 {

     for (int i=; i<=n; i++)

     {

         if (!vis[i]&&Map[x][i]==)

         {

             vis[i]=;

             if (!ok[i])

             {

                 ok[i]=x;

                 return true;

             }

             else

             {

                 if (Find(ok[i]))

                 {

                     ok[i]=x;

                     return true;

                 }

             }

         }

     }

     return false;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while (t--)

     {

         scanf("%d%d",&n,&m);

         int ans=;

         memset(vis,,sizeof(vis));

         memset(Map,,sizeof(Map));

         memset(ok,,sizeof(ok));

         memset(ss,,sizeof(ss));

         for (int i=; i<=n; i++)

         {

             scanf("%d",&a[i]);

         }

         for (int i=; i<=m; i++)

         {

             scanf("%d",&b[i]);

             ss[b[i]]=;

         }

         for (int i=; i<=n; i++)

         {

             for (int j=i+; j<=n; j++)

             {

                 if (ss[a[i]+a[j]]==)

                     Map[i][j]=Map[j][i]=;

             }

         }

         for (int i=; i<=n; i++)

         {

             memset(vis,,sizeof(vis));

             if (Find(i))

                 ans++;

         }

         printf ("%d\n",ans/);

     }

     return ;

 }

BNUOJ 12756 Social Holidaying（二分匹配）-LMLPHP