HDU 4647 Another Graph Game

Another Graph Game
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 660    Accepted Submission(s): 235
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 W
v, and every edge e has its own weight W
e.
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 <= 10
5, 0<=m<=10
5) The next line have n numbers from W
1 to W
n which W
i is the weight of node i.(|W
i|<=10
9)
The next m lines, each line have three numbers u, v, w,(1≤u,v≤n,|w|<=10
9) 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
 
 
Source
2013 Multi-University Training Contest 5
 
 
Recommend
zhuyuanchen520
 
 
标题:N点、M辺あり.ポイントには重みがあり、エッジには重みがあります.Alice、Bobはそれぞれポイントを選びます.1つのエッジの2つの頂点が同じ人によって選択されている場合、この重み値が得られます.Alice-Bob?
 
考え方:欲張り.
1つのエッジについて、ポイントを1つ持っていれば、そのエッジの半分の重み値を持っていることを示します.
もしある辺の2つの頂点がそれぞれ異なる人だったら. では、差は変わらない. 
エッジの2つの頂点がそれぞれ同じ人である場合.では、和の値も変わりません.                 ,だから私たちは1つの辺を2つの頂点に分解して、それから順次Aliceが最大を取って、Bobが次を大きくすることができます.彼らはみな頭がいいからだ.
 

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

using namespace std;

const int N=100010;

int n,m;
double a[N];

int cmp(double x,double y){
    return x>y;
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
            scanf("%lf",&a[i]);
        int u,v,w;
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            a[u]+=1.0*w/2;
            a[v]+=1.0*w/2;
        }
        double t1=0,t2=0;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)
            if(i&1)
                t1+=a[i];
            else
                t2+=a[i];
        printf("%.0lf
",t1-t2);
    }
    return 0;
}