2015
09-17

# HDU 4647-Another Graph Game-贪心-[解题报告]HOJ

Problem Description
Alice and Bob are playing a game on an undirected graph with n (n is even) nodes and m edges. Every node i has its own weight Wv, and every edge e has its own weight We.

They take turns to do the following operations. During each operation, either Alice or Bob can take one of the nodes from the graph that haven’t been taken before. Alice goes first.

The scoring rule is: One person can get the bonus attached to a node if he/she have choosen that node before. One person can get the bonus attached to a edge if he/she have choosen both node that induced by the edge before.

You can assume Alice and Bob are intelligent enough and do operations optimally, both Alice and Bob’s target is maximize their score – opponent’s.

What is the final result for Alice – Bob.

Input
Muilticases. The first line have two numbers n and m.(1 <= n <= 105, 0<=m<=105) The next line have n numbers from W1 to Wn which Wi is the weight of node i.(|Wi|<=109)

The next m lines, each line have three numbers u, v, w,(1≤u,v≤n,|w|<=109) the first 2 numbers is the two nodes on the edge, and the last one is the weight on the edge.

Output
One line the final result.

Sample Input
4 0
9 8 6 5

Sample Output
2

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 10007;

int n,m;
double a[N];

int main()
{
int i,j,k,x,y;
double w;
while(~scanf("%d%d",&n,&m))
{
for(i = 1; i<=n; i++)
scanf("%lf",&a[i]);
for(i = 1; i<=m; i++)
{
scanf("%d%d%lf",&x,&y,&w);
w=w/2;
a[x]+=w;
a[y]+=w;
}
sort(a+1,a+1+n);
double sum1=0,sum2=0;
for(i = 1; i<=n; i++)
{
if(i%2==0)
sum1+=a[i];
else
sum2+=a[i];
}
printf("%.0f\n",sum1-sum2);
}

return 0;
}