sgu 321 The Spy Network (dfs+贪心)

321. The Spy Network

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard




The network of spies consists of N intelligence officers. They are numbered with the code numbers from 1 to N so that nobody could discover them. The number 1 belongs to the radiowoman Kat. There is exactly N - 1 communication channels between the spies. It is known that a message from any spy to Kat can reach her. All channels are unidirectional.

A channel can have one of two types: protected and almost protected. It is known that a message will not be intercepted almost surely by the hostile security service if at least half of the channels along the path to radiowoman Kat are protected. What is the minimum number of channels to be made protected from almost protected, so that any message from any spy will not be intercepted almost surely ? What are those channels?

Input

The first line of the input contains the integer number N (1 ≤ N ≤ 200000). The following N - 1 lines contain the description of the communication channels. Each channel is described by a pair of the code numbers of spies (the direction of the channel is from the first spy to the second one) and the parameter pi. If pi = 

protected

, the channel is protected and if pi = 

almost protected

, the channel is almost protected.

Output

Write the number of channels to be converted to protected to the first line of the output. To the next line write numbers of channels to be made protected. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
5
5 1 almost protected
3 1 almost protected
2 3 protected
4 3 almost protected
2
1 2

 

 

题意:一棵结点数为n的树,给出n-1条边,每条边有一个属性,0(almost protect)和1(protect),修改某些边的属性使得满足树上每一个结点到根节点的路径上,属性为1的边的数量大于等于属性为0的边的数量,求最小操作数

 

思路:首先要修改的边,应该离根节点越近越好,越近的话,对其他结点的贡献越多。所以用dfs(u)表示u的所有子节点中最多需要的1的边的数量,当这个数量大于u的深度的时候,就表示u前面全部修改了也不够满足条件,这时候就看u和下一个结点连接的边的属性是1还是0,是0的话,就要修改这条边,加进答案里面。dfs扫一遍就行了

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <utility>
#include <queue>
#include <stack>
using namespace std;
const int INF=1<<30;
const double eps=1e-6;
const int N = 200010;

struct _edge{
    int u,v,next;
    bool w;
};
_edge e[N];
int first[N],n;
vector<int> ans;

int dfs(int u,int dep)
{
    int res = (dep+1)/2;
    for(int i=first[u];i!=-1;i=e[i].next)
    {
        int v = e[i].v;
        int tmp = dfs(v,dep+1);
        if(e[i].w) tmp--;
        else if(tmp>dep)
        {
            ans.push_back(i);
            tmp--;
        }
        res = max(res,tmp);
    }
    return res;
}

void run()
{
    int u,v;
    char s[20];
    memset(first,-1,sizeof(first));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&v,&u);
        e[i].u = u;
        e[i].v = v;
        scanf("%s",s);
        if(s[0]==a)
            e[i].w=0,scanf("%s",s);
        else
            e[i].w=1;
        e[i].next = first[u];
        first[u] = i;
    }
//    for(int i=1;i<n;i++)
//        cout<<e[i].u << ‘ ‘ << e[i].v << ‘ ‘ << e[i].w<<endl;
    ans.clear();
    dfs(1,0);
    printf("%d\n",ans.size());
    if(!ans.empty()) printf("%d",ans[0]);
    for(int i=1;i<ans.size();i++)
        printf(" %d",ans[i]);
    puts("");
}

int main()
{
    freopen("case.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
        run();
    return 0;
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。