题解 P2538 【[SCOI2008]城堡】

好吧蒟蒻我又来发一篇题解了 虽然标签写着是动归，但是~~由于本人太弱~~，想了半个小时都没想到状态转移方程，但是十分凑巧的想到了一个非常暴力的做法 做法一：依次枚举放置的城堡，然后再统计最长边的长度，但是这样就要枚举城堡的个数和放置城堡的点，复杂度过高，不能接受 做法二：从每个有城堡的点出发，扩展到无法扩展时放置一个城堡然后继续扩展，但是这种做法会丢失放置城堡的最优性，虽然便利于处理路径长度，但是丢失了正确性 ~~正解~~，枚举长度判断是否满足，毕竟观察一下题目是不超过k个城堡，意思就是城堡个数只是一个限制条件，并不一定要全部放置，所以可以把这个条件放在一边 然后接下来二分长度，开始~~暴力~~二分判断长度，然后就AC了 代码 ``` #include<bits/stdc++.h> using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } int d[55][55],n,m,k,a[55],p[55]; int l=0,r=0,ans; bool v[55]; int t[55]; void search(int x) { memset(t,0,sizeof(t)); for(int i=0;i<n;++i) if(!v[i]) for(int j=0;j<n;++j) if(d[i][j]<=x) ++t[j]; int p=0; for(int i=0;i<n;++i) if(t[i]>=t[p]) p=i; for(int i=0;i<n;++i) if(d[p][i]<=x) v[i]=1; } bool check(int x) { memset(v,0,sizeof(v)); //判断该点是否满足条件（被覆盖） for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(d[p[i]][j]<=x) v[j]=1; for(int i=0;i<k;++i) search(x); for(int i=0;i<n;++i) if(!v[i]) return 0; return 1; } int main() { memset(d,0x3f,sizeof(d)); n=read(),m=read(),k=read(); for(int i=0;i<n;++i) a[i]=read();//存边 for(int i=0;i<n;++i) { d[i][i]=0; int x=read(); r+=x;//二分上界 d[i][a[i]]=d[a[i]][i]=min(d[i][a[i]],x); //有重边啊，这是一个坑点 } for(int k=0;k<n;++k) for(int i=0;i<n;++i) for(int j=0;j<n;++j) d[i][j]=min(d[i][k]+d[k][j],d[i][j]); //欺负图小，直接Floyd for(int i=0;i<m;++i) p[i]=read(); while(l<=r) { int mid=(l+r)>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; //memset(v,0,sizeof(v)); // memset(t,0,sizeof(t)); //不知道为什么如果放在这里会爆WA } //二分答案 printf("%d\n",ans); } ``` 好吧发现和题解代码差不多，其实这题是机房大佬给我讲过思路的。我就这里无耻的替他发题解吧233