首页 > 代码库 > bzoj3391 [Usaco2004 Dec]Tree Cutting网络破坏
bzoj3391 [Usaco2004 Dec]Tree Cutting网络破坏
Description
约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了．贝茜很愤怒，打算狠狠报
复．她打算破坏刚建成的约翰的网络． 约翰的网络是树形的，连接着N(1≤N≤10000)个牛棚．她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断．之后，就会存在若干子网络．为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？
Input
第1行：一个整数N.
第2到N+1行：每行输入两个整数，表示一条电缆的两个端点．
Output
按从小到大的顺序，输出所有值得破坏的牛棚．如果没有一个值得破坏，就输出“NONE”．
Sample Input
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
Sample Output
3
8
如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的．
8
如果牛棚3或牛棚8被破坏，剩下的三个子网节点数将是5，2，2，没有超过5的．
又是刷水……
dfs无根树转有根树完维护子树的节点数+乱搞
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;struct edge{ int to,next;}e[100010];int head[10010];int fa[10010];int sum[10010];bool mrk[10010];bool exist;int n,cnt;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void ins(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v){ ins(u,v); ins(v,u);}inline void dfs(int x){ if (mrk[x])return; mrk[x]=1;sum[x]=1; for (int i=head[x];i;i=e[i].next) if (!mrk[e[i].to]) { fa[e[i].to]=x; dfs(e[i].to); sum[x]+=sum[e[i].to]; }}int main(){ n=read(); for (int i=1;i<n;i++) { int x=read(),y=read(); insert(x,y); } dfs(1); for (int i=1;i<=n;i++) { bool mrk=0; if (n-sum[i]>n/2)mrk=1; for (int j=head[i];j;j=e[j].next) if (e[j].to!=fa[i]&&sum[e[j].to]>n/2)mrk=1; if (!mrk) { exist=1; printf("%d\n",i); } } if (!exist)printf("NONE");}
bzoj3391 [Usaco2004 Dec]Tree Cutting网络破坏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。