2020-08-11
http://icpc.upc.edu.cn/problem.php?id=14881
题目¶
14881: 会议
题目描述¶
有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
输入¶
第一行。一个数n，表示有n个村民。 接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。
输出¶
一行输出两个数字x和y x表示村长将会在哪个村民家中举办会议 y表示距离之和的最小值
样例输入¶
样例输出¶
提示¶
70%数据n<=1000 100%数据n<=50000
#include <bits/stdc++.h>
using namespace std;
struct node
{
int to;
int next;
};
node e[100500]={0};
int cnt=0;
int head[100500]={0};
int size1[100500]={0};
int dis[100500]={0};
int f[100500]={0};
int n;
int add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
int dfs1(int now)
{
size1[now]=1;
for(int i=head[now];i;i=e[i].next)
{
int to=e[i].to;
if(dis[to])
continue;
dis[to]=dis[now]+1;
dfs1(to);
size1[now]+=size1[to];
}
}
int dfs(int now,int fa)
{
f[now]=f[fa]+n-2*size1[now];
for(int i=head[now];i;i=e[i].next)
{
int to=e[i].to;
if(to==fa)
continue;
dfs(to,now);
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dis[1]=1;
dfs1(1);
int maxn=0;
for(int i=1;i<=n;i++)
{
maxn+=dis[i];
}
maxn-=*n; ///每一个点到1的距离都是从1开始计算，须减去
f[1]=maxn;
for(int i=head[1];i;i=e[i].next)
{
int to=e[i].to;
dfs(to,1);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(f[i]<maxn)
maxn=f[i],ans=i;
}
printf("%d %d\n",ans,maxn);
return 0;
}
题目¶
14539: Ki
题目描述¶
Given is a rooted tree with N vertices numbered 1 to N. The root is Vertex 1, and the i-th edge ( 1≤i≤N−1) connects Vertex ai and bi. Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0. Now, the following Q operations will be performed: Operation j (1≤j≤Q): Increment by xj the counter on every vertex contained in the subtree rooted at Vertex pj. Find the value of the counter on each vertex after all operations.
Constraints ·2≤N≤2×105 ·1≤Q≤2×105 ·1≤ai<bi≤N ·1≤pj≤N ·1≤xj≤104 ·The given graph is a tree. ·All values in input are integers.
输入¶
Input is given from Standard Input in the following format:
N Q a1 b1 : aN−1 bN−1 p1 x1 : pQ xQ
输出¶
Print the values of the counters on Vertex 1,2,…,N after all operations, in this order, with spaces in between.
样例输入¶
【样例1】 4 3 1 2 2 3 2 4 2 10 1 100 3 1 【样例2】 6 2 1 2 1 3 2 4 3 6 2 5 1 10 1 10
样例输出¶
【样例1】 100 110 111 110 【样例2】 20 20 20 20 20 20
提示¶
样例1解释
The tree in this input is as follows:
Each operation changes the values of the counters on the vertices as follows: ·Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2,3,4. The values of the counters on Vertex 1,2,3,4 are now 0,10,10,10, respectively. ·Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1,2,3,4. The values of the counters on Vertex 1,2,3,4 are now 100,110,110,110, respectively. ·Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1,2,3,4 are now 100,110,111,110, respectively.
DFS+前缀和
#include <bits/stdc++.h>
using namespace std;
struct node
{
int to;
int next;
};
node e[500500]={0};
int cnt=0;
int head[500500]={0};
int dis[500500]={0};
int n;
int add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
int dfs(int now,int fa)
{
dis[now]+=dis[fa];
for(int i=head[now];i;i=e[i].next)
{
int to=e[i].to;
if(to==fa)
continue;
dfs(to,now);
}
}
int main()
{
int q;
scanf("%d%d",&n,&q);
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
dis[x]+=y;
}
for(int i=head[1];i;i=e[i].next)
{
int to=e[i].to;
dfs(to,1);
}
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}
题目¶
15047: 胖虎的菜品
题目描述¶
胖虎惊喜地发现了有N个窗口有他最喜欢吃的菜（其实都喜欢？），但是他想在移动最短距离（毕竟走多了也是会累的）的情况下吃到所有他喜欢吃的菜品，饥饿的他已经没有力气写出代码来计算自己的最佳方法了，所以他找到了你，来帮他解决这个问题。现在给你N个窗口及窗口的坐标，请输出胖虎所要移动的最小距离总和。 胖虎一开始在(0,0)点处。
输入¶
第一行一个正整数n（1≤n≤13） 。 接下来每行2个实数，表示第i块窗口的坐标。 两点之间的距离公式为
输出¶
一个数，表示要跑的最少距离，保留2位小数。
样例输入¶
样例输出¶
状压DP#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
double dp[1<<14][20]={0};
struct node
{
double x;
double y;
};
node a[20]={0};
double q(int i,int j)
{
double sum=sqrt((double)((a[i].x-a[j].x)*(a[i].x-a[j].x)*1.0+(a[i].y-a[j].y)*(a[i].y-a[j].y)*1.0));
return sum;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
}
for(int i=0;i<(1<<(n+1));i++)
{
for(int j=0;j<=n;j++)
{
dp[i][j]=999999999;
}
}
dp[1][0]=0;
for(int i=0;i<(1<<(n+1));i+=1)
{
for(int j=0;j<=n;j++)
{
if(!(i>>j)&1)
continue;
for(int k=0;k<=n;k++)
{
if(j==k)
continue;
if(!(i>>k)&1)
continue;
dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+q(k,j));
}
}
}
double min1=99999999;
int k=(1<<(n+1))-1;
for(int i=1;i<=n;i++)
{
min1=min(min1,dp[k][i]);
}
printf("%.2f\n",min1);
return 0;
}