Vasya is a schoolboy who rides a trolley bus and then a bus to get to school. He’s
always very happy to get a “lucky ticket,” which means the total of the first three
digits in the ticket number equals the total of the last three digits. However, Vasya has
been down on his luck ever since the beginning of the new school year – over the past
month, he hardly had any lucky tickets at all.
Vasya thought this over and decided to take control of the situation. Upon reviewing
his recent tickets, he realized he can produce several lucky numbers by combining
trolley bus tickets with bus tickets. To that end, the schoolboy had to take two tickets,
fold them in half along the vertical axis and join halves of different tickets together.
The first three digits of the new “super lucky ticket” are the three digits on the lefthand side of the ticket for one mode of transport, and the last three digits are the three
digits on the right-hand side of the ticket for the other mode of transport.
Example: let us assume that Vasya has a trolley bus ticket with the number 123456
and a bus ticket with the number 789222. They can be combined either as 123222 or
as 789456. The first one of these two combinations is super lucky.
Your task is to write a program that will help produce the maximum number of super
lucky combinations from the tickets available, assuming each ticket can only be used
in one combination.
Limitations
1 ≤ n, m ≤ 100.
Input
The first line of the input file contains two integer numbers n and m separated by a
space. The second line of the input file contains n six-digit integer numbers separated
by a space, representing numbers of bus tickets. The third line of the input file
contains m six-digit integer numbers separated by a space, representing numbers of
trolley bus tickets.
Output
The first line of the output file must contain integer number k – the maximum
possible number of super lucky combinations. The following k lines must contain
these super lucky combinations. Each line with a super lucky combination must start
with the Latin letters “AT” if the combination begins with numbers from a bus ticket
and ends with numbers from a trolley bus ticket; otherwise the line must start with the
letters “TA.” The letters must be followed by two six-digit numbers separated by a
space, representing the numbers of the relevant tickets.
12
12
2016-2017 ACM Central Region of Russia Quarterfinal Programming Contest
Examples
Input.txt Output.txt
2 2
123456 111222
141204 555000
2
TA 555000 123456
TA 141204 111222
题目：https://vjudge.net/contest/388418#problem/J
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
int n,m,flag;
int ma[250][250];
bool book[250];
int match[250];
bool find(int u) //二分图套路
{for(int i=1; i<=m; i++){if(ma[u][i]&&book[i]==0) //这里的遍历都是u集合到v集合，所以如果开始俩个集合都是{ //完全不同的，那么，建图的时候，就只ma[i][j]建边就行book[i]=1;if(match[i]==0||find(match[i])){match[i]=u;return 1;}}}return 0;
}
int he(int s) //取三位和
{int sum=0;for(int i=1; i<=3; i++){sum=sum+s%10;s=s/10;}return sum;
}
int main()
{ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);int a[120],b[120];while(cin>>n>>m){int s=0;memset(ma,0,sizeof(ma));memset(match,0,sizeof(match));for(int i=1; i<=n; i++){cin>>a[i];}for(int i=1; i<=m; i++){cin>>b[i];}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(he(a[i]/1000)==he(b[j])) //a的前三位和b的后三位相同{ma[i][j]=1; //因为a和b是完全独立的，而上面遍历也都是i到j，所以这里都是i到j}if(he(a[i])==he(b[j]/1000))//a的后三位和b的前三位相同{ma[i][j]=2;}}}for(int i=1; i<=n; i++){memset(book,0,sizeof(book));if(find(i))s++;}printf("%d\n",s);for(int i=1; i<=m; i++){if(match[i]) //存在，说明i和match[i]之前有线{if(ma[match[i]][i]==1) //如果是1说明是a在前{printf("AT %d %d\n",a[match[i]],b[i]);}else //不然b在前{printf("TA %d %d\n",b[i],a[match[i]]);}}}}return 0;
}