題意：
給你N個(gè)lich，M個(gè)wizard，K個(gè)半徑為Ri的wood (N,M,K<=200)
第i個(gè)lich每Ti秒能殺死一個(gè)在Ri范圍的wizard，但前提是lich跟wizard的連線與任何一個(gè)wood沒有交
求最少多少時(shí)間lich能殺死所有wizard 或者判無解
做法：
首先可以想到 如果固定一個(gè)時(shí)間 那么每個(gè)lich能殺的個(gè)數(shù)是固定的
所以先二分答案
預(yù)處理每個(gè)lich可以到達(dá)的wizard
然后可以用網(wǎng)絡(luò)流求解了 S向第i個(gè)lich連容量N/Ti+1，lich向能打到的wizard連容量1，wizard向T連容量1。
（難點(diǎn)不在于建圖，在于計(jì)算幾何預(yù)處理！）
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 #define n 1005
6 #define m 200005
7 struct TElement
8 {
9 int x,y,r,t;
10 } lich[n],wizard[n],wood[n];
11 int vtx[m],ne[m],f[m],tot;
12 int L[n],d[n],pre[n],q[n];
13 int N,M,K,S,T,now,ret;
14 bool G[n][n];
15
16 inline int SQRdis(int x1,int y1,int x2,int y2)
17 {
18 return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
19 }
20 inline bool Inside(int x,int y)
21 {
22 for (int i=1;i<=K;++i)
23 if (SQRdis(x,y,wood[i].x,wood[i].y)<wood[i].r*wood[i].r) return 1;
24 return 0;
25 }
26 inline bool Block(int i,int j)
27 {
28 int b=SQRdis(lich[i].x,lich[i].y,wizard[j].x,wizard[j].y);
29 for (int k=1;k<=K;++k)
30 {
31 int a=SQRdis(lich[i].x,lich[i].y,wood[k].x,wood[k].y);
32 int c=SQRdis(wizard[j].x,wizard[j].y,wood[k].x,wood[k].y);
33 if (a+b<c||c+b<a) continue;
34 double y=c-(b+c-a)*(long long)(b+c-a)/(4.0*b);
35 if (y<=wood[k].r*wood[k].r) return 1;
36 }
37 return 0;
38 }
39 inline void Ins(int u,int v,int fl)
40 {
41 vtx[++tot]=v;f[tot]=fl;ne[tot]=L[u];L[u]=tot;
42 vtx[++tot]=u;f[tot]=0;ne[tot]=L[v];L[v]=tot;
43 }
44 inline void push()
45 {
46 int fl=1<<30;
47 for (int i=T;i!=S;i=vtx[pre[i]^1])
48 fl=min(fl,f[pre[i]]);
49 ret+=fl;
50 for (int i=T;i!=S;i=vtx[pre[i]^1])
51 {
52 f[pre[i]]-=fl,f[pre[i]^1]+=fl;
53 if (!f[pre[i]]) now=vtx[pre[i]^1];
54 }
55 }
56 inline void dinic(int u)
57 {
58 if (u==T) push();
59 else
60 {
61 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
62 if (f[p]&&d[u]+1==d[v])
63 {
64 pre[v]=p,dinic(v);
65 if (d[now]<d[u]) return;
66 now=T;
67 }
68 d[u]=-1;
69 }
70 }
71 inline bool extend()
72 {
73 memset(d,63,sizeof(d));
74 d[q[1]=S]=0,now=T;
75 for (int h=1,t=1,u=q[h];h<=t;u=q[++h])
76 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
77 if (f[p]&&d[v]>(1<<29))
78 {
79 d[v]=d[u]+1;
80 if (v==T) return 1;
81 q[++t]=v;
82 }
83 return 0;
84 }
85 inline bool check(int Time)
86 {
87 memset(L,0,sizeof(L));
88 tot=1,ret=0;
89 for (int i=1;i<=N;++i)
90 if (lich[i].t) Ins(S,i,1+Time/lich[i].t);
91 else Ins(S,i,1<<30);
92 for (int i=1;i<=N;++i)
93 for (int j=1;j<=M;++j)
94 if (G[i][j]) Ins(i,j+N,1);
95 for (int j=1;j<=M;++j)
96 Ins(j+N,T,1);
97 for (;extend();dinic(S));
98 return ret==M;
99 }
100 int main()
101 {
102 scanf("%d%d%d",&N,&M,&K);
103 for (int i=1;i<=N;++i)
104 scanf("%d%d%d%d",&lich[i].x,&lich[i].y,&lich[i].r,&lich[i].t);
105 for (int i=1;i<=M;++i)
106 scanf("%d%d",&wizard[i].x,&wizard[i].y);
107 for (int i=1;i<=K;++i)
108 scanf("%d%d%d",&wood[i].x,&wood[i].y,&wood[i].r);
109 for (int i=1;i<=N;++i)
110 {
111 if (Inside(lich[i].x,lich[i].y)) continue;
112 for (int j=1;j<=M;++j)
113 {
114 if (Inside(wizard[j].x,wizard[j].y)) continue;
115 if (SQRdis(lich[i].x,lich[i].y,wizard[j].x,wizard[j].y)<=lich[i].r*lich[i].r)
116 if (!Block(i,j)) G[i][j]=1;
117 }
118 }
119 S=N+M+1,T=S+1;
120 int l=0,r=2000000000,mid;
121 if (!check(r)) return puts("-1"),0;
122 if (check(l)) return puts("0"),0;
123 for (;l+1<r;)
124 if (mid=(l+r)>>1,check(mid)) r=mid;
125 else l=mid;
126 printf("%d\n",r);
127 return 0;
128 }
129