[题解] [P3557 POI2013]GRA-Tower Defense Game https://www.luogu.org/problemnew/show/P3557
这道题是真的 **
根据题目给的 \(k\), 可以知道, 我们随便放塔, 只要不全放一起, 一定是一种合法的方案.
直接枚举就好了, 脑子都不用, 时间复杂度 \(O(n)\)
- #include<bits/stdc++.h>
- using namespace std;
- #define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)
- #define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)
- #define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)
- #define Max(a,b) ((a)<(b)?(b):(a))
- #define Min(a,b) ((a)<(b)?(a):(b))
- #define endl '\n'
- #define midd register int mid=(l+r)>>1
- #define TMP template <class ccf>
- TMP inline ccf qr(ccf b){
- char c=getchar();
- int q=1;
- ccf x=0;
- while(c<48||c>57)
- q=c==45?-1:q,c=getchar();
- while(c>=48&&c<=57)
- x=x*10+c-48,c=getchar();
- return q==-1?-x:x;
- }
- const int maxn=500005;
- struct E{
- int to,nx;
- }e[maxn<<2];
- int head[maxn];
- int cnt;
- inline void add(int fr,int to,bool f){
- e[++cnt]=(E){to,head[fr]};
- head[fr]=cnt;
- if(f)
- add(to,fr,0);
- }
- int n,m,k;
- bool usd[maxn];
- bool ans[maxn];
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in.in","r",stdin);
- freopen("out.out","w",stdout);
- #endif
- n=qr(1);
- m=qr(1);
- k=qr(1);
- register int t1,t2;
- RP(t,1,m){
- t1=qr(1);
- t2=qr(1);
- add(t1,t2,1);
- }
- RP(t,1,n){
- if(!usd[t]){
- usd[t]=1;
- ans[t]=1;
- ERP(i,t){
- usd[e[i].to]=1;
- ERP(f,e[i].to)
- usd[e[f].to]=1;
- }
- }
- }
- int qaq=0;
- RP(t,1,n)
- if(ans[t])
- qaq++;
- cout<<qaq<<endl;
- RP(t,1,n)
- if(ans[t])
- cout<<t<<' ';
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945665.html