[CF 513F] Scaygerboss

作法：

首先做個顯然的簡化，把問題化為$k$男$k$女的問題。因此現在問題變成，要安排$k$個位子，讓每個位子都放進一男一女，並且使得最大走路時間最少。而這顯然可以二分搜，因此現在問題變成給定一個時間上限 T，判斷是否可以完成要求。建立最大流模型，假設總共有$num$個空格，那麼考慮由$k$男$k$女，還有$num$個格子和$num$個虛擬節點，還有源點匯點構成的圖，如果 $i$ 女可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從 $i$ 女建到第 $j$ 個虛擬節點的邊，容量為$1$。並且對第 $i$ 個虛擬節點建到第 $i$ 個空格的容量為$1$的邊，還有如果 $i$ 男可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從第 $j$ 個空格建到 $i$ 男的邊，容量也是$1$。最後讓源點連往所有女生，所有男生連往匯點，容量也都是$1$。那麼從源點到匯點的最大流$=k$若且唯若存在一組解。這樣因為節點的總數為$O(n^2)$，邊的總數為$O(n^4)$，而 Dinic 算法據說在所有邊容量都為$1$的圖中的複雜度為$O(min(E^{\frac{3}{2}},EV^{\frac{2}{3}}))$，其中$E,V$分別為圖的邊數和點數（這篇comment講的），因此再加上二分搜可以得到總複雜度為$O(n^6logn)$（二分搜時每次都重建圖），對於$n=22$來說還是很大，不過應該是常數小所以很驚險的用 2683ms AC了。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 1000000000
using namespace std;
const int maxn=2000 ;
 
struct P{int from,to,flow,cap;};
struct Dinic
{
    vector<P> edge ;
    vector<int> v[maxn] ;
    int n,st,ed ;
 
    void init(int Max)
    {
        n=Max ;
        for(int i=0;i<=n;i++) v[i].clear() ;
        edge.clear() ;
    }
 
    void add_edge(int from,int to,int cap)
    {
        edge.push_back((P){from,to,0,cap}) ;
        edge.push_back((P){to,from,0,0}) ;
        int m=edge.size() ;
        v[from].push_back(m-2) ;
        v[to].push_back(m-1) ;
    }
 
    bool vis[maxn] ;
    int d[maxn] ;
    bool BFS()
    {
        fill(vis,vis+n+1,0) ;
        queue<int> q ;
        d[st]=0 ; q.push(st) ; vis[st]=1 ;
        while(!q.empty())
        {
            int u=q.front() ; q.pop() ;
            for(auto i:v[u])
            {
                P &e=edge[i] ;
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=1 ;
                    d[e.to]=d[u]+1 ;
                    q.push(e.to) ;
                }
            }
        }
        return vis[ed] ;
    }
 
    int cur[maxn] ;
    int DFS(int x,int a)
    {
        if(x==ed || a==0) return a ;
        int Flow=0 , f ;
        for(int &i=cur[x];i<v[x].size();i++)
        {
            P &e=edge[v[x][i]] ;
            if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                Flow+=f ;
                e.flow+=f ;
                edge[v[x][i]^1].flow-=f ;
                a-=f ;
                if(a==0) break ;
            }
        }
        return Flow ;
    }
 
    int MaxFlow(int st,int ed)
    {
        this->st = st ;
        this->ed = ed ;
        int Flow=0 ;
        while(BFS())
        {
            fill(cur,cur+n+1,0) ;
            Flow+=DFS(st,INF) ;
        }
        return Flow ;
    }
}dinic;
 
struct Scay
{
    int x,y,t ;
    void scan(){scanf("%d%d%d",&x,&y,&t); x-- ; y-- ;}
}a[maxn],b[maxn];
 
char G[25][25] ;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
int n,m ;
void BFS(int st,int *d)
{
    fill(d,d+n*m,INF) ;
    queue<int> q ; q.push(st) ; d[st]=0 ;
    while(!q.empty())
    {
        int u=q.front() , x=u/m , y=u%m ; q.pop() ;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i] , ny=y+dy[i] ;
            if(nx<0||nx>=n||ny<0||ny>=m) continue ;
            if(G[nx][ny]=='#'||d[nx*m+ny]!=INF) continue ;
            d[nx*m+ny]=d[u]+1 ; q.push(nx*m+ny) ;
        }
    }
}
 
struct Q
{
    int x,y ; LL val ;
    bool operator < (const Q &rhs) const
    {
        return val<rhs.val ;
    }
};
vector<Q> E ;
 
int d[maxn][maxn] ;
int gx[maxn],gy[maxn] ;
main()
{
    int p,q ; scanf("%d%d%d%d",&n,&m,&p,&q) ;
    if(p!=q+1 && q!=p+1){printf("-1\n") ; return 0 ;}
    for(int i=0;i<n;i++) scanf("%s",G[i]) ;
    int k=max(p,q) ;
    for(int i=1;i<=k;i++) a[i].scan() ;
    for(int i=1;i<=k;i++) b[i].scan() ;
    if(p>q) swap(a[1],b[1]) ;
 
    int num=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(G[i][j]=='.')
        num++ , gx[num]=i , gy[num]=j , BFS(i*m+j,d[i*m+j]) ;
 
    int source=2*k+2*num+1 , sink=2*k+2*num+2 ;
    for(int i=1;i<=num;i++) E.push_back((Q){k+i,k+num+i,-1}) ;
    for(int i=1;i<=k;i++)
        E.push_back((Q){source,i,-1}) , E.push_back((Q){k+2*num+i,sink,-1}) ;
 
    for(int i=1;i<=k;i++) for(int j=1;j<=num;j++)
    {
        int x=m*a[i].x+a[i].y , y=m*gx[j]+gy[j] ;
        if(d[x][y]!=INF) E.push_back((Q){i,k+j,(LL)d[x][y]*a[i].t}) ;
        x=m*b[i].x+b[i].y ;
        if(d[x][y]!=INF) E.push_back((Q){k+num+j,k+2*num+i,(LL)d[x][y]*b[i].t}) ;
    }
 
    sort(E.begin(),E.end()) ;
    int l=num+2*k-2 , r=E.size() ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        dinic.init(2*k+2*num+2) ;
        for(int i=0;i<=mid;i++) dinic.add_edge(E[i].x,E[i].y,1) ;
        if(dinic.MaxFlow(source,sink)==k) r=mid ;
        else l=mid ;
    }
    printf("%I64d\n",r==E.size()?-1:E[r].val) ;
}