BZOJ 1822 [JSOI2010]Frozen Nova 冷凍波

很明顯的一道最大流，利用計算幾何判斷是否被攻擊的關系。二分時間以判斷攻擊次數，每次重建立圖。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack> 
#include<cmath>
using namespace std;
const int maxn = ;
const int inf = ;
struct edge
{
    int u,v,cap,flow;
};
struct P
{
    int x,y,r,t;
};
struct L{
    P a,b;
};
P w[maxn],s[maxn],t[maxn];
vector<int> G[maxn];
vector<edge> f;
void add_edge(int u,int v,int cap)
{
    f.push_back((edge){u,v,cap,});
    f.push_back((edge){v,u,,});
    int m=f.size();
    G[u].push_back(m-);
    G[v].push_back(m-);
}
int d[maxn],cur[maxn],mx,x,y,z,n,m,S,T,l,r,k;
bool vis[maxn],map[][];
bool bfs()
{
    memset(vis,false,sizeof(vis));
    queue<int> Q;
    Q.push(S);
    vis[S]=true;d[S]=;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=;i<G[u].size();i++)
        {
            edge& e=f[G[u][i]];
            if(e.cap>e.flow&&!vis[e.v])
            {
                d[e.v]=d[u]+;
                vis[e.v]=true;
                Q.push(e.v);
            }
        }
    }
    return vis[T];
}
int dfs(int u,int a)
{
    int flow=,h;
    if(u==T||a==) return a;
    for(int &i=cur[u];i<G[u].size();i++)
    {
        edge& e=f[G[u][i]];
        if(d[e.v]==d[u]+&&(h=dfs(e.v,min(e.cap-e.flow,a)))>)
        {
            flow+=h;
            f[G[u][i]^].flow-=h;
            e.flow+=h;
            a-=h;
            if(a==) break; 
        }
    }
    return flow;
}
int Dinic(int s,int t)
{
    int flow=;
    while(bfs()) {
        memset(cur,,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
inline P operator-(P a,P b)
{
    P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;
}
inline double operator*(P a,P b)
{
    return a.x*b.y-a.y*b.x;
}
inline double dis(P a,P b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double dot(P a,P b)
{
    return a.x*b.x+a.y*b.y;
}
inline double dis(L l,P p)
{
    if(dot(l.a-p,l.b-p)>)
        return min(dis(l.a,p),dis(l.b,p));
    return abs((p-l.a)*(l.b-l.a)/dis(l.a,l.b));
}
bool jud(int x,int y)
{
    if(dis(w[x],s[y])>w[x].r)return ;
    for(int i=;i<=k;i++)
        if(dis((L){w[x],s[y]},t[i])<t[i].r)return ;
    return ;
}
void build(int x)
{
    f.clear();T=n+m+; 
    for(int i=;i<=T;i++) G[i].clear();
    for(int i=;i<=n;i++) add_edge(,i,x/w[i].t+);
    for(int i=;i<=m;i++) add_edge(i+n,T,);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
            if(map[i][j]) add_edge(i,j+n,);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=;i<=n;i++) scanf("%d%d%d%d",&w[i].x,&w[i].y,&w[i].r,&w[i].t),mx=max(mx,w[i].t);
    for(int i=;i<=m;i++) scanf("%d%d",&s[i].x,&s[i].y);
    for(int i=;i<=k;i++) scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].r);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            map[i][j]=jud(i,j);
            if(map[i][j]) d[j]=;           
        }
    for(int i=;i<=m;i++)
    {
        if(!d[i]){
            puts("-1");return ;
        }
    }
    l=,r=mx*m;int mid;
    while(l<=r)
    {
        mid=(l+r)>>;
        build(mid);
        int ans=Dinic(S,T);
        if(ans==m) r=mid-;
        else l=mid+;
    }
    printf("%d\n",l);
    return ;   
}