这是一道网络流的题目。。。
在巨佬hy学姐&ylm学长的万般帮助下A的，万般感谢orzzzzzz
题面有点长。。。但还是要耐心看下。。。
做法大概就是二分答案，然后跑网络流
-
在二分之前，先对每个人跑一边bfs，算出他从现在的格子跑到其他的格子要多久。（这里的(dis)可以存(int)类型，到后面建图(step3)判断的时候再乘上(t)，这样可以减少$long $ (long)的运算复杂度
但我并没有这样写）：void bfs1(int id){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dis[id][i][j]=INF; dis[id][a[id].x][a[id].y]=0; XDDD now; qd.push((XDDD){a[id].x,a[id].y,0}); while(!qd.empty()){ now=qd.front(); qd.pop(); for(int i=0;i<4;i++){ int xx=now.x+dir[i][0]; int yy=now.y+dir[i][1]; if(xx<1||yy<1||xx>n||yy>m||g[xx][yy]||dis[id][xx][yy]!=INF) continue; dis[id][xx][yy]=now.t+a[id].t; qd.push((XDDD){xx,yy,dis[id][xx][yy]}); } } }
- 二分最短时间的区间：$l=0$，$r=maxt*n*m$
- 网络流的建模比较烦人，很容易出锅。。。
$ss$是源点（编号为0）
$st$是汇点（编号为$2*k+2*n*m+1$）
男生的点的编号从1到$k$
女生的点的编号从$k+1$到$k*2$
把一个格子拆成两个点，坐标为$(x,y)$的点的编号分别为$(x-1)m+y+2k$和$(x-1)m+y+2k+nm$（男生女生的点已经用掉$2k$个啦~所以这里要加上$2k$啊）
$Step 1$：从源点向男生各连一条流量为1的边，从女生各向汇点连一条流量为1的边。大概长这样：
```cpp
for(int i=1;i<=k;i++){
add_edge(ss,i,1);
add_edge(i+k,st,1);
}
```
$Step 2$：把一个格子拆成两个点，连上一条流量为1的边：
```cpp
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
add_edge(turn(i,j),turn(i,j)+n*m,1);
```
$Step 3$：把每个男生和他能在二分时间内到达的格子连一条流量为1边，把每个女生和她能在二分时间内到达的格子连一条流量为1边（之前把每个格子拆成两个点，这里男生女生分别连两个点）：
```cpp
for(int p=1;p<=k;p++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dis[p][i][j]<=tim) add_edge(p,turn(i,j),1);
if(dis[p+k][i][j]<=tim) add_edge(turn(i,j)+n*m,p+k,1);
}
}
}
```
嗯建完了
- 然后就可以跑Dinic了，要注意时间哈
完整代码：
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int N=40,No=1700,M=700000,Da=810,inf=0x7fffffff;
const ll INF=0x7fffffffffffffff;
ll l,r,maxt,ans,dis[Da][N][N];
int n,m,k,ss,st,tot,h[No],vis[No],g[N][N],d[No];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct XDDD{int x,y;ll t;}a[Da];
struct Edge{int to,ne,val;}e[M];
queue<XDDD> qd;
queue<int> q;
inline int turn(int i,int j){return (i-1)*m+j+2*k;}
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
void add_edge(int x,int y,ll c){
e[++tot]=(Edge){y,h[x],c};
h[x]=tot;
e[++tot]=(Edge){x,h[y],0};
h[y]=tot;
}
void bfs1(int id){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dis[id][i][j]=INF;
dis[id][a[id].x][a[id].y]=0;
XDDD now;
qd.push((XDDD){a[id].x,a[id].y,0});
while(!qd.empty()){
now=qd.front();
qd.pop();
for(int i=0;i<4;i++){
int xx=now.x+dir[i][0];
int yy=now.y+dir[i][1];
if(xx<1||yy<1||xx>n||yy>m||g[xx][yy]||dis[id][xx][yy]!=INF) continue;
dis[id][xx][yy]=now.t+a[id].t;
qd.push((XDDD){xx,yy,dis[id][xx][yy]});
}
}
}
void build(ll tim){
tot=-1;
for(int i=0;i<=st+1;i++) h[i]=-1;
for(int i=1;i<=k;i++){
add_edge(ss,i,1);
add_edge(i+k,st,1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
add_edge(turn(i,j),turn(i,j)+n*m,1);
for(int p=1;p<=k;p++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dis[p][i][j]<=tim) add_edge(p,turn(i,j),1);
if(dis[p+k][i][j]<=tim) add_edge(turn(i,j)+n*m,p+k,1);
}
}
}
}
bool bfs(){
while(!q.empty()) q.pop();
for(int i=0;i<=st+1;i++) d[i]=0;
d[ss]=1;
q.push(ss);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=h[u];i!=-1;i=e[i].ne){
if(!d[e[i].to]&&e[i].val){
d[e[i].to]=d[u]+1;
q.push(e[i].to);
if(e[i].to==st) return true;
}
}
}
return false;
}
int dfs(int u,int minn){
if(u==st||!minn) return minn;
int ret=0;
for(int i=h[u];i!=-1;i=e[i].ne){
if(d[e[i].to]==d[u]+1&&e[i].val){
int dd=dfs(e[i].to,min(minn,e[i].val));
if(dd){
ret+=dd;
minn-=dd;
e[i].val-=dd;
e[i^1].val+=dd;
}
if(!minn) break;
}
}
if(!ret) d[u]=-1;
return ret;
}
bool check(ll tim){
int ret=0;
build(tim);
while(bfs())
ret+=dfs(ss,inf);
return ret==k;
}
int main(){
scanf("%d%d%d
",&n,&m,&k);
char ch[25];
for(int i=1;i<=n;i++){
scanf("%s",ch);
for(int j=0;j<m;j++){
g[i][j+1]=(ch[j]=='#');
}
}
for(int i=1;i<=k;i++){
scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].t);
maxt=max(maxt,a[i].t);
}
for(int i=k+1;i<=k+k;i++){
scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].t);
maxt=max(maxt,a[i].t);
}
for(int i=1;i<=k+k;i++) bfs1(i);
ss=0;
st=2*k+2*n*m+1;
l=0;
r=maxt*n*m;
ans=-1;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
printf("%lld",ans);
return 0;
}