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 Wv, and every edge e has its own weight We.
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.
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 <= 105, 0<=m<=105) The next line have n numbers from W1 to Wn which Wi is the weight of node i.(|Wi|<=109)
The next m lines, each line have three numbers u, v, w,(1≤u,v≤n,|w|<=109) the first 2 numbers is the two nodes on the edge, and the last one is the weight on the edge.
The next m lines, each line have three numbers u, v, w,(1≤u,v≤n,|w|<=109) 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
Recommend
zhuyuanchen520
题意： 有N个点，M条边。 点有权值， 边有权值。 Alice, Bob 分别选点。 如果一条边的两个顶点被同一个人选了， 那么能获得该权值。问 Alice - Bob？
思路： 贪心。
对于一条边来说， 如果拿了一个点， 说明已经拿了该边的一半权值。
如果某边的两个的顶点分别是不同的人。 那么差值还是不变的。
如果某边的两个顶点分别是同一个人。 那么和值也不变。 ，所以我们可以把一个边分解到两个顶点上，然后依次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; }