HDU4647+贪心

 1 /*
 2 贪心。
 3 题意：给定一些点 一些边 点和边都有价值。现在A B 选点。求A-B的maxVal
 4 思路：分割边。边的1/2分给两个端点。
 5     如果这两个点被同一个人取，则ok；否则 做减法也行，对题意无影响。
 6 */
 7 #include<stdio.h>
 8 #include<string.h>
 9 #include<stdlib.h>
10 #include<algorithm>
11 #include<iostream>
12 #include<queue>
13 #include<map>
14 #include<stack>
15 #include<set>
16 #include<math.h>
17 using namespace std;
18 typedef long long int64;
19 //typedef __int64 int64;
20 typedef pair<int64,int64> PII;
21 #define MP(a,b) make_pair((a),(b)) 
22 const int maxn = 100015;
23 const int inf = 0x7fffffff;
24 const double pi=acos(-1.0);
25 const double eps = 1e-8;
26 double NodeVal[ maxn ],EdgeVal[ maxn ];
27 bool cmp( double a,double b ){
28     return a>b;
29 }
30 int main(){
31     int n,m;
32     while( scanf("%d%d",&n,&m)==2 ){
33         for( int i=0;i<n;i++ ){
34             scanf("%lf",&NodeVal[i]);
35         }
36         int u,v;
37         for( int i=0;i<m;i++ ){
38             scanf("%d%d%lf",&u,&v,&EdgeVal[i]);
39             NodeVal[ u-1 ] += 1.0*EdgeVal[i]/2.0;
40             NodeVal[ v-1 ] += 1.0*EdgeVal[i]/2.0;
41         }
42         double A,B;
43         A = B = 0;
44         sort( NodeVal,NodeVal+n,cmp );
45         //NodeVal[ n ] = 0;
46         for( int i=0;i<n;i++ ){
47             if( i%2==0 ) A += NodeVal[i];
48             else B += NodeVal[i];
49         }
50         //printf("A = %d, B = %d
",A,B);
51         printf("%.0lf
",A-B);
52     }
53     return 0;
54 }
View Code
keep moving...