Codeforces Round #635 (Div. 2) C. Linova and Kingdom（贪心+搜索）

Myth丶恋晨 2023-05-22 04:56 16阅读 0赞

题目地址----> [C. Linova and Kingdom][]

题意：一个n个节点(root=1)的树，让你找k个工厂，其他n-k为旅游地，每个工厂从自身点到根节点经过的旅游地的个数为幸福值，让你求着k个工厂幸福值的最大值。

解题： 每个点的深度-（以该节点为子节点数量+该点的子节点数量）

我们分析每个点，我们从叶子节点往上分析，这样可以保证幸福值最大（显然）。

每个点他的贡献就是：深度-（以该节点为子节点数量+该点的子节点数量）。

我们从叶子节点往上贪心，到达节点i，那么节点i的所有子节点都应该被选作工厂，这样才能保证最大值。

首先对于一条链，  
他的贡献往上是：贡献的是 深度-以该节点为子节点数量（根节点为0，其他为1），不分析根节点的话就是深度-1。因为自己是工厂所以不算幸福值。  
他的贡献往下是：该点既然作为一个工厂，那么这个点对于他的子节点们是有影响的，幸福值会减少该点子节点的数量。

深度我用bfs搜的，每个点的子节点我用dfs搜的。

最后取前k大值就是答案。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    ll ne[maxn],he[maxn],ver[maxn],vis[maxn],vis1[maxn],d[maxn],du[maxn],dd[maxn];
    ll tot=1,num,cnt;
    void add(ll x,ll y)
    { 
    	ver[tot]=y;
    	ne[tot]=he[x];
    	he[x]=tot++;
    }
    queue<ll> q;
    void bfs()
    { 
    	d[1]=1;
    	vis[1]=1;
    	q.push(1);
    	while(!q.empty())
    	{ 
    		num=q.front();
    		q.pop();
    		for(int i=he[num];i;i=ne[i])
    		{ 
    			ll ans=ver[i];
    			if(!vis[ans])
    			{ 	
    				d[ans]=d[num]+1;
    				q.push(ans);
    				vis[ans]=1;
    			}
    			
    		}
    	}
    }
    void dfs(ll k)
    { 
    	du[k]=1;
    	vis1[k]=1;
    	for(int i=he[k];i;i=ne[i])
    	{ 
    		if(!vis1[ver[i]])
    		{ 
    			dfs(ver[i]);
    			du[k]+=du[ver[i]];
    		}
    	}
    }
    int main()
    { 
    	io();
    	ll k,n;
    	cin>>n>>k;
    	for(ll i=1;i<=n;i++) vis[i]=0,du[i]=0;
    	for(ll i=1;i<n;i++)
    	{ 
    		ll x,y;
    		cin>>x>>y;
    		add(y,x);
    		add(x,y);
    	}
    	bfs();
    	dfs(1);
    	for(int i=1;i<=n;i++)
    		du[i]--;
    	for(ll i=1;i<=n;i++)
    	{ 
    		if(i==1) d[i]-=du[i];
    		else d[i]=d[i]-du[i]-1;
    	} 
    	sort(d+1,d+1+n);
    	ll sum=0;
    	for(ll i=n;i>n-k;i--) 
    	{ 
    		sum+=d[i];
    	}
    	cout<<sum<<endl;
    	return 0;
    }

[C. Linova and Kingdom]: http://codeforces.com/contest/1337/problem/C