首页 > 代码库 > XVII Open Cup named after E.V. Pankratiev Grand Prix of Moscow Workshops, Sunday, April 23, 2017 Problem K. Piecemaking

XVII Open Cup named after E.V. Pankratiev Grand Prix of Moscow Workshops, Sunday, April 23, 2017 Problem K. Piecemaking

2024-11-16 22:39:02   203人阅读

题目：Problem K. Piecemaking
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 mebibytes
The civil war in Berland continues for five years already. The United Nation decided to end the bloodshed.
Berland consists of n cities, connected by n - 1 bidirectional roads, forming a tree. The Purple Army
occupies several cities which are listed in the set A, and the Cian Army occupies cities listed in the set
B. The UN Assembly took an unexpected decision to end the war: they decided to destroy some roads
in Berland, so that no city from the set A is connected (directly or undirectly) with a city from the set
B. This way the enemies wouldn’t be able to reach each other, and the fighting would stop. Destroying
a road of length x kilometers requires x dollars.
Find the minimum sum of money neccessary for peacemaking in Berland.
Input
The first line of the input contains a positive integer n (2 ≤ n ≤ 200 000) — the number of cities in
Berland.
Next n - 1 lines contain information about roads in the form ui, vi, wi (1 ≤ ui; vi ≤ n, 1 ≤ wi ≤ 109) —
indices of cities connected by the i-th road, and the length of this road in kilometers.
The next line contains a positive integer m (1 ≤ m ≤ n) — the number of cities occupied by the Purple
Army, and m distinct integers a1; a2; : : : ; am (1 ≤ ai ≤ n) — indices of these cities.
The next line contains a positive integer k (1 ≤ k ≤ n) and k distinct integers b1; b2; : : : ; bk (1 ≤ bi ≤ n) —
the cities, occupied by the Cian army, in the similar format.
It is guaranteed that no city is occupied by both armies.
Output
Print the minimum possible number of dollars required to make it impossible to reach any city in set B
from any city in set A.
Example

standard input standard output
6
1 2 5
2 4 4
2 5 1
1 3 2
3 6 7
1 4
2 5 6		 3


思路：

　　比较简单的树dp：dp[i][s]：表示这个点属于空集合，还是A集合，还是B集合？

　　转移过程略麻烦。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define MP make_pair
 6 #define PB push_back
 7 typedef long long LL;
 8 typedef pair<int,int> PII;
 9 const double eps=1e-8;
10 const double pi=acos(-1.0);
11 const int K=1e6+7;
12 const int mod=1e9+7;
13 
14 vector<PII>mp[K];
15 int n,m,col[K];
16 LL dp[K][3];
17 
18 void dfs(int u,int f)
19 {
20     for(auto v:mp[u])if(v.first!=f) dfs(v.first,u);
21     for(auto v:mp[u])if(v.first!=f)
22     {
23         if(col[u]==0)
24         {
25             if(col[v.first]==0)
26             {
27                 dp[u][0]+=min(dp[v.first][0],min(dp[v.first][1],dp[v.first][2])+v.second);
28                 dp[u][1]+=min(min(dp[v.first][0],dp[v.first][1]),dp[v.first][2]+v.second);
29                 dp[u][2]+=min(min(dp[v.first][0],dp[v.first][2]),dp[v.first][1]+v.second);
30             }
31             else if(col[v.first]==1)
32             {
33                 dp[u][0]+=dp[v.first][1]+v.second;
34                 dp[u][1]+=dp[v.first][1];
35                 dp[u][2]+=dp[v.first][1]+v.second;
36             }
37             else
38             {
39                 dp[u][0]+=dp[v.first][2]+v.second;
40                 dp[u][1]+=dp[v.first][2]+v.second;
41                 dp[u][2]+=dp[v.first][2];
42             }
43         }
44         else if(col[u]==1)
45         {
46             if(col[v.first]==0)
47                 dp[u][1]+=min(min(dp[v.first][0],dp[v.first][1]),dp[v.first][2]+v.second);
48             else if(col[v.first]==1)
49                 dp[u][1]+=dp[v.first][1];
50             else
51                 dp[u][1]+=dp[v.first][2]+v.second;
52         }
53         else
54         {
55             if(col[v.first]==0)
56                 dp[u][2]+=min(min(dp[v.first][0],dp[v.first][2]),dp[v.first][1]+v.second);
57             else if(col[v.first]==1)
58                 dp[u][2]+=dp[v.first][1]+v.second;
59             else
60                 dp[u][2]+=dp[v.first][2];
61         }
62     }
63     if(col[u]==1) dp[u][0]=dp[u][2]=2e14;
64     else if(col[u]==2) dp[u][0]=dp[u][1]=2e14;
65     //printf("%d==%lld %lld %lld\n",u,dp[u][0],dp[u][1],dp[u][2]);
66 }
67 int main(void)
68 {
69     scanf("%d",&n);
70     for(int i=1,x,y,z;i<n;i++)
71         scanf("%d%d%d",&x,&y,&z),mp[x].PB(MP(y,z)),mp[y].PB(MP(x,z));
72     scanf("%d",&m);
73     for(int i=1,x;i<=m;i++) scanf("%d",&x),col[x]=1;
74     scanf("%d",&m);
75     for(int i=1,x;i<=m;i++) scanf("%d",&x),col[x]=2;
76     dfs(1,0);
77     printf("%lld\n",min(min(dp[1][0],dp[1][1]),dp[1][2]));
78     return 0;
79 }

 

XVII Open Cup named after E.V. Pankratiev Grand Prix of Moscow Workshops, Sunday, April 23, 2017 Problem K. Piecemaking


联系
我们