首页 > ACM题库 > HDU-杭电 > HDU 3512-Perfect matching[解题报告]HOJ
2014
11-05

HDU 3512-Perfect matching[解题报告]HOJ

Perfect matching

问题描述 :

Given the complete bipartite graph. Each part of this graph has N vertices, i.e. the graph is balanced. An integer number (called a weight) assigns to each vertex. The weight of the edge is defined as the product of weights of vertices which connected by this edge.
It is well known, a matching in a graph is a set of edges without common vertices. A matching is perfect, if it covers all vertices of a graph.
Write a program to find a perfect match of the given bipartite graph with the maximal weight of the matching edges minimal.

输入:

The input consists of multiple cases.
For each testcase,there will be exactly three lines;
The first line contains one integer number N (1 ≤ N ≤ 105). The second line consist of N integer numbers, not exceeded 109 by absolute value. The i-th number in line denotes a weight of i-th vertex of first part of a graph. In the third line, weights of vertices of second part are presented.

输出:

The input consists of multiple cases.
For each testcase,there will be exactly three lines;
The first line contains one integer number N (1 ≤ N ≤ 105). The second line consist of N integer numbers, not exceeded 109 by absolute value. The i-th number in line denotes a weight of i-th vertex of first part of a graph. In the third line, weights of vertices of second part are presented.

样例输入:

3
1 2 3
9 10 11

样例输出:

27

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn= 100005;
long long a[maxn],b[maxn];
const long long INF = 1LL<<62;
int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		for(int i = 0;i < n;i ++){
			scanf("%I64d",&a[i]);
		}
		for(int i = 0;i < n;i ++){
			scanf("%I64d",&b[i]);
		}
		sort(a,a + n);
		sort(b,b + n);
		int i1 = lower_bound(a,a + n,0) - a;
		int i2 = lower_bound(b,b + n,0) - b;
		long long ans = -INF;
		int d1 = min(n - i1,i2);
		int i = n - 1,j = d1 - 1;
		for(int cnt = 0;cnt < d1;cnt ++){
			 ans = max(ans,a[i --] * b[j --]);
		}
		int d2 = min(i1,n - i2);
		i = d2 - 1,j = n - 1;
		for(int cnt = 0;cnt < d2;cnt ++){
			ans = max(ans,a[i --] * b[j --]);
		}
		i = n - 1 - d1,j = d1;
		for(int cnt = 0;cnt < n - d1 - d2;cnt ++){
			ans = max(ans,a[i --] * b[j ++]);
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.