时间限制: 1 Sec 内存限制: 1024 MB
题目描述
Alice and Bob play a game on a tree. Initially, all nodes are white.
Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In each turn, a player moves the chip from the current position to an ancestor or descendant node, as long as the node is not black. This node also becomes black. The player who cannot move the chip looses.
Who wins the game?
An ancestor of a node v in a rooted tree is any node on the path between v and the root of the tree.
A descendant of a node v in a rooted tree is any node w such that node v is located on the path between w and the root of the tree.
We consider that the root of the tree is 1.
输入
The first line contains one integer n (1 ≤ n ≤ 100 000) — the number of nodes.
Each of the next n − 1 lines contains two integers u and v (1 ≤ u, v ≤ n) — the edges of the tree. It is guaranteed that they form a tree.
输出
In a single line, print “Alice” (without quotes), if Alice wins. Otherwise, print “Bob”.
样例输入
【样例1】
4 1 2 2 3 3 4
【样例2】
7 2 1 2 6 1 3 2 5 7 2 2 4
样例输出
【样例1】
Bob
【样例2】
Alice
提示
样例解释：
In the first test case, the tree is a straight line and has 4 nodes, so Bob always can choose the last white node.
In the second test case, the optimal strategy for Alice is to place the chip on 3. This node will become black. Bob has to choose the node 1. Alice can choose any of 4, 5, 6, or 7. Bob can only choose 2. Alice chooses any of the white sons of 2, and Bob cannot make a move.
题目大意：
先手可以随意选一个节点并将节点涂黑，然后另一个人只能够在刚刚涂黑的节点的基础上选择这个节点的父节点或者是子节点再将其涂黑，注意，选择的时候不能够选择已经被涂黑的节点，当没有办法操作的时候，对应的人输掉比赛，最后输出赢家是哪一位
当然，Alice是先手
int n; int dp[maxn]; struct node{ int u; int v; int next; }a[maxn]; int cnt; int head[maxn]; void _Init(){ cnt = 0; for(int i=0;i<maxn;i++) head[i] = -1; } void _Add(int u,int v){ a[cnt].u = u; a[cnt].v = v; a[cnt].next = head[u]; head[u] = cnt ++; } void Work(int u,int p){ dp[u] = 0; for(int i=head[u];~i;i = a[i].next){ int v = a[i].v; if(p == v) continue; Work(v,u); dp[u] += dp[v]; } if(dp[u] == 0) dp[u] = 1; else dp[u] -- ; } int main() { _Init(); n=read; for(int i=1;i<n;i++){ int u=read,v=read; _Add(u,v); _Add(v,u); } Work(1,1); if(dp[1] == 0) puts("Bob"); else puts("Alice"); return 0; }
时间限制: 1 Sec 内存限制: 128 MB
题目描述
There is an undirected weighted complete graph of n vertices where n is odd.
Let’s define a cycle-array of size k as an array of edges [e1,e2,…,ek] that has the following properties:
·k is greater than 1.
·For any i from 1 to k, an edge ei has exactly one common vertex with edge ei−1 and exactly one common vertex with edge ei+1 and these vertices are distinct (consider e0=ek, ek+1=e1).
It is obvious that edges in a cycle-array form a cycle.
Let’s define f(e1,e2) as a function that takes edges e1 and e2 as parameters and returns the maximum between the weights of e1 and e2.
Let’s say that we have a cycle-array C=[e1,e2,…,ek]. Let’s define the price of a cycle-array as the sum of f(ei,ei+1) for all i from 1 to k (consider ek+1=e1).
Let’s define a cycle-split of a graph as a set of non-intersecting cycle-arrays, such that the union of them contains all of the edges of the graph. Let’s define the price of a cycle-split as the sum of prices of the arrays that belong to it.
There might be many possible cycle-splits of a graph. Given a graph, your task is to find the cycle-split with the minimum price and print the price of it.
输入
The first line contains one integer n (3≤n≤999, n is odd) — the number of nodes in the graph.
Each of the following n⋅(n−1)/2 lines contain three space-separated integers u, v and w (1≤u,v≤n,u≠v,1≤w≤109), meaning that there is an edge between the nodes u and v that has weight w.
输出
Print one integer — the minimum possible price of a cycle-split of the graph.
样例输入
【样例1】
3 1 2 1 2 3 1 3 1 1
【样例2】
5 4 5 4 1 3 4 1 2 4 3 2 3 3 5 2 1 4 3 4 2 2 1 5 4 5 2 4 3 4 2
样例输出
【样例1】 3 【样例2】 35
提示
Let’s enumerate each edge in the same way as they appear in the input. I will use ei to represent the edge that appears i-th in the input.
The only possible cycle-split in the first sample is S = {[e1, e2, e3]}. f(e1, e2)+f(e2, e3)+f(e3, e1) = 1+1+1 = 3.
The optimal cycle-split in the second sample is S = {[e3, e8, e9], [e2, e4, e7, e10, e5, e1, e6]}. The price of [e3, e8, e9] is equal to 12, the price of [e2, e4, e7, e10, e5, e1, e6] is equal to 23, thus the price of the split is equal to 35.
官方题解：
分享一个博主的做法
一种比较不靠谱的方法
vector <int> vet[maxn]; int main() { int n=read; int u,v,w; while(cin>>u>>v>>w){ vet[u].push_back(w); vet[v].push_back(w); } ll ans = 0; for(int i=1;i<=n;i++){ sort(vet[i].begin(),vet[i].end()); for(int j=1;j<=n-1;j++) ans += vet[i][j],j++; } cout << ans <<endl; return 0; }
另一种方法：
和上面的方法很相似，但是需要先对输入的节点进行排序（按照边权的大小进行排序），然后再对图进行建边操作，然后遍历所有的节点，将与该节点相邻的节点的边进行类似上面方法的操作进行相加求和，最后输出最终的答案即可
代码如下：
struct node{ int u; int v; int w; }a[maxn]; bool cmp(node x,node y){ return x.w < y.w; } int head[maxn]; struct Node{ ///int u; int v; int next; int w; }b[maxn]; int cnt; void _Add(int u,int v,int w){ ///b[cnt].u = u; b[cnt].v = v; b[cnt].w = w; b[cnt].next = head[u]; head[u] = cnt ++; } void _Init(){ for(int i=0;i<maxn;i++){ head[i] = -1; } } int main() { ll n=read; _Init(); ll lim = (n - 1) * n >> 1; for(int i=1;i<=lim;i++){ a[i].u = read; a[i].v = read; a[i].w = read; } sort(a+1,a+1+lim,cmp); for(int i=1;i<=lim;i++){ _Add(a[i].u,a[i].v,a[i].w); _Add(a[i].v,a[i].u,a[i].w); } ll ans = 0; for(int i=1;i<=n;i++){ for(int j=head[i];~j;j = b[j].next){ ans += b[j].w; j = b[j].next; } } cout<< ans <<endl; return 0; }
