貪心好題，表示不會做然后膜拜了一下PoPoQQQ的題解http://blog.csdn.net/popoqqq/article/details/44495319。

考慮每個點選對答案的貢獻為w，不選的貢獻為-w，每一條邊兩個端點都不選的貢獻為-c，選一個端點的貢獻為0，選兩個端點的貢獻為c，于是我們計算ans的時候先全部都減去，然后就變成了，一個點選的貢獻為2w，不選的貢獻為0，一條邊兩個端點都不選的貢獻為0，選一個端點的貢獻為c，選兩個端點的貢獻為2c，每個點的權值就等于2*w+c，于是每次選最大的就好了。

其實還有一種做法，可以把邊權平分到兩個端點，因為每條邊要么屬于一個人，要么屬于兩個人，而且答案要求差值，所以是正確的。

#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #define maxn 10010using namespace std;long long a[maxn]; long long ans; int n,m;bool cmp(long long a,long long b) {return a>b; }int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){int x;scanf("%d",&x);ans-=x;a[i]+=2*x;}for (int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);ans-=z;a[x]+=z;a[y]+=z;}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i+=2) ans+=a[i];printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的【bzoj2563】 阿狸和桃子的游戏 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。