pro:二维平面上,给定N个村庄。M个士兵驻守,把村庄围住,现在我们想留下更多的士兵休息,使得剩下的士兵任然满足围住村庄。N,M<500;
sol:即是要找一个最小的环,环把村庄围住。 由于是环, 最小的点数等价于最小的边数。 所以我们求最小的边数,而士兵之间能有有向边,当且仅当所有的村庄在有向边的左边(逆时针连边)。 然后就是floyd最小环。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=510; const int inf=1e9; const double pi=acos(-1.0); struct point{ int x,y; point(){} point(int xx,int yy):x(xx),y(yy){} }a[maxn],b[maxn]; ll det(point a,point b){ return a.x*b.y-a.y*b.x;} ll dot(point a,point b){ return a.x*b.x+a.y*b.y;} point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y);} point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y);} int dis[maxn][maxn]; int main() { int N,M,ans; while(~scanf("%d",&N)){ rep(i,1,N) scanf("%d%d",&a[i].x,&a[i].y); scanf("%d",&M); rep(i,1,M) scanf("%d%d",&b[i].x,&b[i].y); rep(i,1,M) rep(j,1,M) dis[i][j]=inf; ans=inf; rep(i,1,M) rep(j,1,M){ if(i==j) continue; bool F=1; rep(k,1,N){ if(det(b[j]-b[i],a[k]-b[i])<0){ F=0; break; } } if(F) dis[i][j]=1; } rep(k,1,M) rep(i,1,M) if(dis[i][k]!=inf) //删去后很慢 rep(j,1,M) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); rep(i,1,M) ans=min(ans,dis[i][i]); if(ans==inf) puts("ToT"); else printf("%d\n",M-ans); } return 0; }
HDU - 6080 :度度熊保护村庄 (凸包,floyd最小环)(VJ1900题达成)
原文:https://www.cnblogs.com/hua-dong/p/10746658.html