怎么用目录建wordpress站点,北京通州网站建设公司,莱芜网站设计,仪征市企业网站建设公司正题
题目链接:https://www.luogu.org/problemnew/show/P3441 题目大意
求III条路径最多可以覆盖树上多少个点。 解题思路
我们先只考虑叶子节点#xff0c;显然可以覆盖min{num叶,I∗2}min\{num_叶,I*2\}min{num叶,I∗2}。 然后网上递推#xff0c;发现依旧是min{numi,…正题
题目链接:https://www.luogu.org/problemnew/show/P3441 题目大意
求III条路径最多可以覆盖树上多少个点。 解题思路
我们先只考虑叶子节点显然可以覆盖min{num叶,I∗2}min\{num_叶,I*2\}min{num叶,I∗2}。 然后网上递推发现依旧是min{numi,I∗2}min\{num_i,I*2\}min{numi,I∗2} 拓扑求出每个numnumnum codecodecode
#includecstdio
#includealgorithm
#includequeue
using namespace std;
const int N1e610;
int n,m,f[N],death,ls[N],tot,ans,dep[N],in[N];
queueint q;
struct edge{int to,next;
}a[2*N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;in[y];
}
void topsort()
{for(int i1;in;i)if(in[i]1){dep[i]1;f[1];q.push(i);}while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]) continue;if((--in[y])1){dep[y]dep[x]1;q.push(y);f[dep[y]];deathmax(death,dep[y]);}}}
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}topsort();for(int i1;ideath;i)ansmin(2*m,f[i]);printf(%d,ans);
}
