poj 3107 删点最大分支最小
2024-09-04 16:39:19
http://poj.org/problem?id=3107
这实际上就是找重心,在之前有做过:http://www.cnblogs.com/qlky/p/5780933.html
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 110000+5
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<]; int head[MAXN],vis[MAXN],ptr=,dp[MAXN],num[MAXN],ans,tot,a[MAXN]; void init()
{
mem(head,-);
mem(vis,);
mem(dp,);
ans =INF;
tot = ;
ptr=;
}
void add(int x,int y)
{
tree[ptr].y = y;
tree[ptr].next = head[x];
head[x] = ptr++;
} void dfs(int rt)
{
num[rt]=vis[rt]=;
int tmp = ;
//pf("rt%d\n",rt);
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis[y]) continue;
dfs(y);
num[rt]+=num[y];
tmp = max(tmp,num[y]);
//pf("y%d %d\n",y,tmp);
}
tmp = max(tmp,n-num[rt]);
//pf("t%d %d %d\n",rt,tmp,ans);
if(tmp<ans)
{
ans = tmp;
tot = ;
a[tot++] = rt;
}
else if(tmp == ans) a[tot++] = rt;
} int main()
{
int i,j,k,t;
while(~sf("%d",&n))
{
init();
for(i=;i<n;i++)
{
int x,y;
sf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs();
sort(a,a+tot);
pf("%d",a[]);
for(i=;i<tot;i++) pf(" %d",a[i]);
blank;
}
}
最新文章
- Lind.DDD.RedisClient~对StackExchange.Redis调用者的封装及多路复用技术
- Spring + SpringMVC + Druid + JPA(Hibernate impl) 给你一个稳妥的后端解决方案
- 引用外部css文件
- 改写libsvmread读取多标记数据集
- [moka同学笔记]一、Yii2.0课程笔记(魏曦老师教程)
- WKWebView API精讲(OC)
- 自动档车的P档和N档的区别
- Java BIO、NIO、AIO-------转载
- oracle表导入导出
- Linux系统中如何添加自己的库文件路径
- mac os 安装PIP 及异常“”Can&#39;t install python module: PyCharm Error: “byte-compiling is disabled, skipping”“”的解决方案
- (jzoj snow的追寻)线段树维护树的直径
- BeautifulSoup4库
- 1.5 A better alternative thing: React Native
- css加载动画...
- JSON Web Token(JWT)原理和用法介绍
- 1、话说linux内核
- Linux内核分析 读书笔记 (第五章)
- MySQL索引的使用方式和缺点
- Keepalived详解之 - LVS(IPVS)管理工具ipvsadm使用指南