锐客网

  1. 首页 > it技术 > >

[POI2013]Tower|[POI2013]Tower Defense Game

题目大意：
一个$n(n\le5\times10^5)$个点$m(m\le10^6)$条边的无向图，边权全为$1$，满足若一个标记点能覆盖与其距离不超过$1$的点，从中选取不超过$k$个点能将整张图覆盖。问若一个标记点能覆盖与其距离不超过$2$的点，求构造一种选取点数不超过$k$的方案将整张图覆盖。
思路：
贪心，每次选取没有覆盖的点作为标记点，并更新覆盖点的和。选取一个点后增加的覆盖范围一定完全包含原来覆盖这个点的标记点的覆盖范围，因此方案一定更优。

1 #include 2 #include 3 inline int getint() { 4register char ch; 5while(!isdigit(ch=getchar())); 6register int x=ch^'0'; 7while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 8return x; 9 } 10 const int N=5e5+1,M=2e6+1; 11 bool b[N],vis[N]; 12 int h[N],ans[N]; 13 struct Edge { 14int to,next; 15 }; 16 Edge e[M]; 17 inline void add_edge(const int &u,const int &v) { 18e[++h[0]]=(Edge){v,h[u]}; h[u]=h[0]; 19e[++h[0]]=(Edge){u,h[v]}; h[v]=h[0]; 20 } 21 int main() { 22const int n=getint(),m=getint(),k=getint(); 23for(register int i=0; i

【[POI2013]Tower|[POI2013]Tower Defense Game】转载于:https://www.cnblogs.com/skylee03/p/8676472.html

    推荐阅读


    上一篇：我的560天

    下一篇：这是我见过的最酷的喝水照，辛苦了！