思路:

首先bfs求出每个空地到每个门的最短距离,注意中间不能经过任何门.好像是原题说过只要经过门就算是退出了.

随后我们二分答案,从原点到每块空地连容量为1的边,从每扇门到汇点连容量为(当前二分的答案)时间的边,对于每块空地和每扇门,若距离不超过时间,则从空地到门连一条容量为1的边.

好像唯一的trick就是从门到汇点的边?不过大家自己YY一下吧.

反正不难.

#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 21
#define M 21
int n,m;
char s[M];
 
int ty[N][M];
 
int d[N][M];
 
static const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct Ins{
    int x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
};
void bfs(int x,int y){
    static queue<Ins>q;
    d[x][y]=0,q.push(Ins(x,y));
    while(!q.empty()){
        Ins tmp=q.front();q.pop();
        for(int k=0;k<4;++k){
            int nx=tmp.x+dx[k],ny=tmp.y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ty[nx][ny]==1&&d[nx][ny]==-1)
                d[nx][ny]=d[tmp.x][tmp.y]+1,q.push(Ins(nx,ny));
        }
    }
}
 
struct MaxflowSolver{
    static const int V=1010,E=200010;
    int head[V],next[E],end[E],flow[E],ind,d[V],inq[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
            if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
        }d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
    }
}Stg;
 
int lab[N][M];
 
int main(){
    scanf("%d%d",&n,&m);register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]=='.')ty[i][j]=1;else if(s[j]=='D')ty[i][j]=2;
    }
     
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j])lab[i][j]=++id;
     
    int L=0,R=1<<30,mid;
    while(L<R){
        mid=(L+R)>>1;
        Stg.reset();
        int cnt=0;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==1)Stg.make(0,lab[i][j],1),++cnt;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2)Stg.make(lab[i][j],n*m+1,mid);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2){
            memset(d,-1,sizeof d),bfs(i,j);
            for(int p=1;p<=n;++p)for(int q=1;q<=m;++q)if(ty[p][q]==1&&d[p][q]!=-1)
                if(d[p][q]<=mid)Stg.make(lab[p][q],lab[i][j],1);
        }
        if(Stg.Maxflow(0,n*m+1)==cnt)R=mid;else L=mid+1;
    }
     
    if(L==1<<30)puts("impossible");else printf("%d",L);
    return 0;
}

思路:

一眼网络流,套一个二分就行了.

关键是如何判断巫妖和精灵之间能否有圆阻挡.

一开始我是进行了复杂的判断:如果线段平行于x轴或者平行于y轴直接特判;

否则求出圆心到直线的距离,如果距离不超过半径,则用一个简单的公式求出圆心到直线最近点的横坐标,利用这个横坐标与线段两个端点的横坐标比较,得出结果.

可是数据跟我想的根本不是一回事啊啊啊!

根本只需要判断距离啊啊啊!!而且相切的情况不算相交啊啊啊!!

什么坑爹数据,我是领教到了.

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

#define N 210
#define M 210
#define P 210

struct MaxflowSolver{
	static const int V=410;
	static const int E=100010;
	int head[V],next[E],end[E],flow[E],ind,d[V];
	inline void reset(){ind=0,memset(head,-1,sizeof head);}
	inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
	inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
	inline bool bfs(int S,int T){
		static int q[V];int fr=0,ta=0;
		memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
		while(fr^ta){
			int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
		}return d[T]!=-1;
	}
	inline int dinic(int p,int T,int Maxflow){
		if(p==T)return Maxflow;
		int last=Maxflow;
		for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
			int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
			if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
		}d[p]=-1;return Maxflow-last;
	}
	inline int Maxflow(int S,int T){
		int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
	}
}Stg;
int x1[N],y1[N],x2[M],y2[M],lim[N],cd[N],ox[P],oy[P],r[P];

int G[N][M];

inline int sqr(int x){return x*x;}



int main(){
	int n,m,p;scanf("%d%d%d",&n,&m,&p);register int i,j,k;
	for(i=1;i<=n;++i)scanf("%d%d%d%d",&x1[i],&y1[i],&lim[i],&cd[i]);
	for(i=1;i<=m;++i)scanf("%d%d",&x2[i],&y2[i]);
	for(i=1;i<=p;++i)scanf("%d%d%d",&ox[i],&oy[i],&r[i]);
	
	int a,b,c;
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(sqr(x1[i]-x2[j])+sqr(y1[i]-y2[j])<=sqr(lim[i])){
		bool ok=1;
		for(k=1;k<=p&&ok;++k){
			a=y1[i]-y2[j],b=x2[j]-x1[i],c=(x1[i]-x2[j])*y1[i]-(y1[i]-y2[j])*x1[i];
			if((LL)(a*ox[k]+b*oy[k]+c)*(a*ox[k]+b*oy[k]+c)<(LL)r[k]*r[k]*(a*a+b*b))ok=0;
		}
		if(ok)G[i][j]=1;
	}
	
	int L=0,R=1<<30,mid;
	while(L<R){
		mid=(L+R)>>1;
		Stg.reset();
		for(i=1;i<=n;++i)Stg.make(0,i,mid/cd[i]+1);
		for(i=1;i<=m;++i)Stg.make(n+i,n+m+1,1);
		for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(G[i][j])Stg.make(i,n+j,1);
		if(Stg.Maxflow(0,n+m+1)==m)R=mid;else L=mid+1;
	}
	
	if(L==1<<30)puts("-1");else printf("%d",L);
	return 0;
}

思路:

我保证这是一种奇葩算法.

我们二分答案,那么问题就转化为若任意两个部落之间的距离\(\leq{l}\),是否能够划分为为\(k\)组.

我们能发现以下性质:若能够划分为\(k'\)组,且满足\(k'>k\),则必定能够划分为\(k\)组.原因是我们可以合并一些块,那么部落之间距离的最小值必然不会减少.

因此我们只需考虑对于一个给定的\(l\),最多能够划分为几组.

考虑两个点,若两点距离\(\leq{l}\),那么必定划分在一组中.那么现在有若干个连通块,不同连通块之间的所有点的距离均\(>l\),显然当前连通块数就是我们要求的最大连通块数.

于是二分+并查集水.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define N 1010
int n,k,x[N],y[N],r[N];
 
inline void init(){for(int i=1;i<=n;++i)r[i]=i;}
inline int find(int x){int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;}
inline void merge(int x,int y){r[find(x)]=find(y);}
typedef double f2;
 
f2 dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
 
 
int main(){
    scanf("%d%d",&n,&k);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
     
    f2 Maxdis=0;
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)Maxdis=max(Maxdis,dis(i,j));
     
    f2 L=0,R=Maxdis,mid;
    while(R-L>1e-4){
        mid=(L+R)*.5;
        init();
        for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(dis(i,j)<=mid)merge(i,j);
         
        int cnt=0;for(i=1;i<=n;++i)cnt+=(i==find(i));
         
        if(cnt>=k)L=mid;else R=mid;
    }
     
    printf("%.2lf",L);
     
    return 0;
}