阿狸和桃子的游戏

这题用到了巧妙的转化，还有贪心 (我现在缺的就是思维，还有代码能力...说是缺思维，其实就是缺，我自己打了堆来取...)

(1) 考虑每一个点

选了桃子与阿狸的差距+w，不选-w

(2) 考虑每一条边

一个端点不选差距-c

选了一个端点 0

两个都选差距+c

那我们一开始假设都没选

然后桃子每次选最大就行了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define dd double
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{char q=getchar();int ans=0,flag=1;while(q<'0'||q>'9'){if(q=='-')flag=-1;q=getchar();}while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();}return ans*flag;
}
const int N=100006;
struct BIIANANANA__
{int v,next,w;
}a1[N*3];
int first[N*3],e;
void addbian(int u,int v,int w)
{a1[e].v=v;a1[e].w=w;a1[e].next=first[u];first[u]=e++;
}bool cmp(int a,int b)
{return a>b;
}int n,m;
int w[N];
int sum;int work()
{for(int i=1;i<=n;++i){w[i]*=2;for(int j=first[i];j!=-1;j=a1[j].next)w[i]+=a1[j].w;}sort(w+1,w+1+n,cmp);for(int i=1;i<=n;++i){if(i&1)sum+=w[i];//else//    sum+=w[i];}return sum;
}int main(){//freopen("in.in","r",stdin);mem(first,-1);n=read();m=read();for(int i=1;i<=n;++i){w[i]=read();sum-=w[i];}int tin1,tin2,tin3;for(int i=1;i<=m;++i){tin1=read();tin2=read();tin3=read();addbian(tin1,tin2,tin3);addbian(tin2,tin1,tin3);sum-=tin3;}cout<

转载于:https://www.cnblogs.com/A-LEAF/p/7651812.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！