hdu 4647 Another Graph Game,想到了就是水題了。。

題目是給一個無向圖，其中每個節點都有點權，邊也有邊權，然後就有2個小朋友開始做游戲了ALICE &BOB 游戲規定ALICE 先行動然後是BOB，然後依次輪流行動，行動時可以任意選取一個節點並獲得節點的點權，如果他已經把一條邊的2個端點都取了，那麼他可以獲得那邊的邊權，如果一條邊的二個端點不同的人取了，那麼誰也得不到那條變得邊權了。 問游戲結束後怎樣可以使ALICE得到的權值和減去BOB 的權值和最大，當然二個人都一樣足夠聰明，即每次行動都會采取最優的策略

解法:若沒有邊權，則對點權從大到小排序即可。。考慮邊，將邊權拆成兩半加到它所關聯的兩個點的點權中即可。。。因為當兩個人分別選擇不同的點時，這一權值將互相抵消。

想想很好理解的，因為最後求的是差值。。。

需要注意的就是要用long long 別的就沒什麼了，為了避免拆邊時出現分數，可以算結果的2倍最後輸出的時候再除以2就行

下面是代碼：

#include<cstdio>
#include<algorithm>
bool inline cmp(long long a,long long b){return a>b;}//遞減排序的cmp函數
long long node[100005],ans;
int N,M;
int read()
{
	if(scanf("%d%d",&N,&M)!=2) return 0;
	for(int i=1;i<=N;i++)
	{
		scanf("%I64d",&node[i]);
		node[i]*=2;//存2倍的點權
	}
	for(int a,b,c,i=0;i<M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		node[a]+=c,node[b]+=c;//拆邊就不用除以2了
	}
	std::sort(node+1,node+N+1,cmp);//遞減排序
	ans=0;
	for(int i=0;i<N/2;i++)
		 ans+=node[2*i+1]-node[2*i+2];//算結果
	printf("%I64d\n",ans/2);//輸出的結果要除以二
	return 1;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(read());
	return 0;
}