地址：3107：http://poj.org/problem?id=3107
2378：http://poj.org/problem?id=2378
1655：http://poj.org/problem?id=1655
这三道题比较相似，我就写在一起了。
3107：Godfather
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 4636 | Accepted: 1575 |
Description
Last years Chicago was full of gangster fights and strange murders. The chief of the police got really tired of all these crimes, and decided to arrest the mafia leaders.
Unfortunately, the structure of Chicago mafia is rather complicated. There are n persons known to be related to mafia. The police have traced their activity for some time, and know that some of them are communicating with each other. Based on the
data collected, the chief of the police suggests that the mafia hierarchy can be represented as a tree. The head of the mafia, Godfather, is the root of the tree, and if some person is represented by a node in the tree, its direct subordinates are represented
by the children of that node. For the purpose of conspiracy the gangsters only communicate with their direct subordinates and their direct master.
Unfortunately, though the police know gangsters’ communications, they do not know who is a master in any pair of communicating persons. Thus they only have an undirected tree of communications, and do not know who Godfather is.
Based on the idea that Godfather wants to have the most possible control over mafia, the chief of the police has made a suggestion that Godfather is such a person that after deleting it from the communications tree the size of the largest remaining connected
component is as small as possible. Help the police to find all potential Godfathers and they will arrest them.
Input
The first line of the input file contains n — the number of persons suspected to belong to mafia (2 ≤ n ≤ 50 000). Let them be numbered from 1 to n.
The following n − 1 lines contain two integer numbers each. The pair ai, bi means that the gangster ai has communicated with the gangster bi. It is guaranteed that the
gangsters’ communications form a tree.
Output
Print the numbers of all persons that are suspected to be Godfather. The numbers must be printed in the increasing order, separated by spaces.
Sample Input
6 1 2 2 3 2 5 3 4 3 6
Sample Output
2 3
题意：删除某个点，使得剩下分块中最大节点数最少，输出该点（若答案有多个点，按顺序输出）。
思路：两遍搜索。第一遍以其中一个点为根节点，将所有点的子节点个数求出。第二遍搜索根据记录的子节点情况求出删除该点后所剩部分中最大的一块含有的点数。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define Ma 50010
struct node{
int to,next;
}tree[Ma*2];
int n,kk=0,head[Ma*2],f[Ma],ans[Ma];
void add(int fa,int son){
tree[kk].to=son;
tree[kk].next=head[fa];
head[fa]=kk++;
}
void dfs(int son,int fa){ //第一遍搜索
int to;
for(int i=head[son];i!=-1;i=tree[i].next){
to=tree[i].to;
if(to!=fa){
dfs(to,son);
f[son]+=f[to];
}
}
}
void dfsans(int son,int fa){ //第二遍搜索
int to,a,b;
for(int i=head[son];i!=-1;i=tree[i].next){
to=tree[i].to;
ans[son]=max(f[to],ans[son]);
if(to!=fa){ //根据子节点个数求最大块的点数
a=f[son];
b=f[to];
f[son]=a-b;
f[to]=a;
dfsans(to,son);
f[son]=a;
f[to]=b;
}
}
}
int main(){
scanf("%d",&n);
int fa,son;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
scanf("%d%d",&fa,&son);
add(fa,son);
add(son,fa);
f[i]=1;
}
f[n]=1;
dfs(1,-1);
dfsans(1,-1);
int minn=Ma,ss=0;
for(int i=1;i<=n;i++)
minn=min(minn,ans[i]);
for(int i=1;i<=n;i++)
if(ans[i]==minn){
if(ss) printf(" %d",i);
else{
printf("%d",i);
ss=1;
}
}
puts("");
return 0;
}
1655：Balancing Act
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8687 | Accepted: 3584 |
Description
from T.
For example, consider the tree:
Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these
trees has two nodes, so the balance of node 1 is two.
For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.
Input
that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.
Output
Sample Input
1 7 2 6 1 2 1 4 4 5 3 7 3 1
Sample Output
1 2
题意：删除某个点，使得剩下最大节点数最少，输出该点以及删掉该点后的最大节点数（若有多个点，输出序号最小的那个）。
思路：同上，注意N的最大值以及赋初值。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define Ma 20010
struct node
{
int to,next;
} tree[Ma*2];
int n,kk,head[Ma*2],f[Ma],ans[Ma];
void add(int fa,int son)
{
tree[kk].to=son;
tree[kk].next=head[fa];
head[fa]=kk++;
}
void dfs(int son,int fa)
{
int to;
for(int i=head[son]; i!=-1; i=tree[i].next)
{
to=tree[i].to;
if(to!=fa)
{
dfs(to,son);
f[son]+=f[to];
}
}
}
void dfsans(int son,int fa)
{
int to,a,b;
for(int i=head[son]; i!=-1; i=tree[i].next)
{
to=tree[i].to;
ans[son]=max(f[to],ans[son]);
if(to!=fa)
{
a=f[son];
b=f[to];
f[son]=a-b;
f[to]=a;
dfsans(to,son);
f[son]=a;
f[to]=b;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int fa,son;
kk=0; //注意赋初值
memset(head,-1,sizeof(head));
memset(ans,0,sizeof(ans));
for(int i=1; i<n; i++)
{
scanf("%d%d",&fa,&son);
add(fa,son);
add(son,fa);
f[i]=1;
}
f[n]=1;
dfs(1,-1);
dfsans(1,-1);
int minn=Ma,ss=0;
for(int i=1; i<=n; i++)
{
if(minn>ans[i])
{
minn=ans[i];
ss=i;
}
}
printf("%d %d\n",ss,minn);
}
return 0;
}
2378：Tree Cutting
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3627 | Accepted: 2152 |
Description
Bessie, feeling vindictive, decided to sabotage Farmer John's network by cutting power to one of the barns (thereby disrupting all the connections involving that barn). When Bessie does this, it breaks the network into smaller pieces, each of which retains
full connectivity within itself. In order to be as disruptive as possible, Bessie wants to make sure that each of these pieces connects together no more than half the barns on FJ.
Please help Bessie determine all of the barns that would be suitable to disconnect.
Input
* Lines 2..N: Each line contains two integers X and Y and represents a connection between barns X and Y.
Output
barns, the output should be a single line containing the word "NONE".
Sample Input
10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8
Sample Output
3 8
Hint
The set of connections in the input describes a "tree": it connects all the barns together and contains no cycles.
OUTPUT DETAILS:
If barn 3 or barn 8 is removed, then the remaining network will have one piece consisting of 5 barns and two pieces containing 2 barns. If any other barn is removed then at least one of the remaining pieces has size at least 6 (which is more than half of the
original number of barns, 5).
题意：删除某个点，使剩下的最大节点数少于总结点数的一半，问有多少情况。
思路：同上，先求出所有点的删除后的最大节点数，在顺序输出该值小于总结点数一半的点的标号。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define Ma 10010
struct node{
int to,next;
}tree[Ma*2];
int n,kk=0,head[Ma*2],f[Ma],ans[Ma];
void add(int fa,int son){
tree[kk].to=son;
tree[kk].next=head[fa];
head[fa]=kk++;
}
void dfs(int son,int fa){
int to;
for(int i=head[son];i!=-1;i=tree[i].next){
to=tree[i].to;
if(to!=fa){
dfs(to,son);
f[son]+=f[to];
}
}
}
void dfsans(int son,int fa){
int to,a,b;
for(int i=head[son];i!=-1;i=tree[i].next){
to=tree[i].to;
ans[son]=max(f[to],ans[son]);
if(to!=fa){
a=f[son];
b=f[to];
f[son]=a-b;
f[to]=a;
dfsans(to,son);
f[son]=a;
f[to]=b;
}
}
}
int main(){
scanf("%d",&n);
int fa,son;
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
scanf("%d%d",&fa,&son);
add(fa,son);
add(son,fa);
f[i]=1;
}
f[n]=1;
dfs(1,-1);
dfsans(1,-1);
int minn=Ma,ss=0;
for(int i=1;i<=n;i++)
if(ans[i]<=n/2) printf("%d\n",i);
puts("");
return 0;
}