「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的．
来源信息
题解
为何我写成了tarjan。。。算了当做练习吧。。。
这样成功转化为了模板题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int 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; } int n,cnt,ind,ans; int dfn[10005],low[10005],last[10005],size[10005]; bool mark[10005]; struct edge{int to,next;}e[20005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void tarjan(int x) { dfn[x]=low[x]=++ind; size[x]=1; int t=0,res=n-1; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) { tarjan(e[i].to); size[x]+=size[e[i].to]; low[x]=min(low[x],low[e[i].to]); if(low[e[i].to]>=dfn[x]) { t=max(t,size[e[i].to]); res-=size[e[i].to]; } } else low[x]=min(low[x],dfn[e[i].to]); t=max(t,res); if(t<=n/2) { ans++; mark[x]=1; } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); if(!ans)puts("NONE"); else for(int i=1;i<=n;i++) if(mark[i])printf("%d\n",i); return 0; } |
Subscribe
计数器 9787649
OI 课件=>
OI 课件=>