首页 > ACM题库 > HDU-杭电 > HDU 3138-Coconuts-数学相关-[解题报告]HOJ
2014
03-03

HDU 3138-Coconuts-数学相关-[解题报告]HOJ

Coconuts

问题描述 :

A group of n castle guards are voting to determine whether African swallows can carry coconuts. While each guard has his own personal opinion on the matter, a guard will often vote contrary to his beliefs in order to avoid disagreeing with the votes of his friends.

You are given a list of guards who either do or do not believe in the coconut-carrying capacity of African swallows, and a list of all pairs of guards who are friends. Your task is to determine how each guard must vote in order to minimize the sum of the total number of disagreements between friends and the total number of guards who must vote against their own beliefs.

输入:

The input to this problem will contain multiple test cases. Each test case begins with a single line containing an integer n (where 2 <= n <= 300), the number of guards, and an integer m (where 1 <= m <= n(n-1)/2), the number of pairs of guards who are friends. The second line of the test case contains n integers, where the ith integer is 1 if the ith guard believes in the ability of African swallows to carry coconuts, and 0 otherwise. Finally, the next m lines of the test case each contain two distinct integers i and j (where 1 <= i, j <= n), indicating that guards i and j are friends. Guards within each pair of friends may be listed in any order, but no pair of guards will be repeated. The input is terminated by an invalid test case with n = m = 0, which should not be processed.

输出:

The input to this problem will contain multiple test cases. Each test case begins with a single line containing an integer n (where 2 <= n <= 300), the number of guards, and an integer m (where 1 <= m <= n(n-1)/2), the number of pairs of guards who are friends. The second line of the test case contains n integers, where the ith integer is 1 if the ith guard believes in the ability of African swallows to carry coconuts, and 0 otherwise. Finally, the next m lines of the test case each contain two distinct integers i and j (where 1 <= i, j <= n), indicating that guards i and j are friends. Guards within each pair of friends may be listed in any order, but no pair of guards will be repeated. The input is terminated by an invalid test case with n = m = 0, which should not be processed.

样例输入:

3 3
1 0 0
1 2
1 3
3 2
6 6
1 1 1 0 0 0
1 2
2 3
4 2
3 5
4 5
5 6
0 0

样例输出:

1
2

Hint
Notes: In the first test case, the best result is achieved when all guards vote that African swallows cannot carry coconuts. Here, there is only a penalty of 1 for the first guard voting against his beliefs. In the second test case, the best result is achieved when each guard votes for his beliefs. The penalty of 2 arises from the disagreements between guards 2 and 4, and guards 3 and 5.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int X = 1005;

ll a[X],b[X];
ll ans;
int n;

int main(){
	freopen("ain.txt","r",stdin);
	int ncase;
	cin>>ncase;
	while(ncase--){
		cin >> n;
		ans = 0;
		ll x = 0,y = 0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			x += a[i]*a[i];
		}
		for(int i=1;i<=n;i++){
			scanf("%lld",&b[i]);
			y += b[i]*b[i];
			ans -= a[i]*b[i];
		}
		cout<<-ans*ans+x*y<<endl;
	}
	return 0;
}

参考:http://www.cnblogs.com/yejinru/archive/2013/01/16/2862983.html


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。