【CF 513F2】

Description

神犇ddddddpppppp勤奋好学，经常会找Fanvree大神问问题。 终于有一天，Fanvree忍无可忍（因为dp问的问题在他看来太无聊），他决定躲在某个机房让dp无法找到他。 所有的机房在一个二维平面上，可以视为一个网格图，每个网格就代表一个机房或者是杂物房。 为了不被dp发现，Fanvree找来了小伙伴帮助他。其中有A个男生，B个女生，和小标。如果每一个男生都有一个女生和他在同一个机房，且每一个女生都有一个男生和她在同一个机房，那么dp就不能找到Fanvree。由于小标CJ资料上填写的是”decline to aswer”，所以她既能和男生一对，也能和女生一对。需要注意的是：最终每一个机房最多只能有一对人，而且小标也一定要配对。每个人可以同时在四相邻的机房间移动（不能移动到杂物房），因此只要一男一女在同一个机房，他们就算是一对了。 现在Fanvree知道每一个人初始的位置和移动速度（即移动到相邻机房所需要的时间，下同）。请你帮Fanvree计算一下，在使得所有人都有人和他（她）配对的情况下，最后完成配对的时间最少是多少。

Solution

明显的网络流

两两匹配，很经典的网络流模型。 男的放左边，女的放右边。 每个教室仅限一个男的，那么把教室代表的点拆成两个点，变成容量为1的边就行了。

要求最小步数——二分

二分出步数限制mid。 每个男的向在mid步中能走到的点连容量为1的边，每个女的被在mid步中能走到的点连容量为1的边。 然后在跑网络流。

预处理

预处理出在图中两两点之间的最短路，用floyd来做。 那么每次连边时，只要最短路小于mid就能连边。

Code

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define fo(i,a,b) for(i=a;i<=b;i++) #define rep(i,a) for(i=first[a];i;i=next[i]) using namespace std; typedef long long ll; const int maxn=2007,maxx=1000007; const ll da=1000000000000LL; int i,j,k,t,n,m,c,x,y,z,S,T,xx,yy,g; int first[maxx*2],last[maxx*2],next[maxx*2],chang[maxx*2],fan[maxx*2]; int fang[4][2]={1,0,0,1,-1,0,0,-1}; int a[25*25][25*25]; char s[100][100]; int rr,num; int u; ll ans,map[25*25][25*25],l,r,mid; int d[maxn],data[maxn]; struct node{ int x,y,z; }b[maxn],cc[maxn]; void add(int x,int y,int z){ // u++; last[++num]=y; next[num]=first[x]; first[x]=num; chang[num]=z; fan[num]=num+1; last[++num]=x; next[num]=first[y]; first[y]=num; chang[num]=0; fan[num]=num-1; } int de(int x,int y){return (x-1)*c+y;} bool bfs(){ int head=0,tail=1,i,j,now; fo(i,0,T)d[i]=-1; data[head]=S,d[S]=0; // u++; while(head<tail){ now=data[++head]; rep(i,now){ if(chang[i]&&d[last[i]]<0){ // u++; data[++tail]=last[i]; d[last[i]]=d[now]+1; if(last[i]==T)return 1; } } } return 0; } int dinic(int x,int y){ int i,j,k=y; if(x==T)return y; u++; rep(i,x){ if(chang[i]&&d[last[i]]==d[x]+1){ j=dinic(last[i],min(y,chang[i])); chang[i]-=j; chang[fan[i]]+=j; y-=j; if(!y)break; } } if(k==y)d[x]=-1; return k-y; } void lian(ll x){ int i,j,k; fo(i,0,T)first[i]=0;num=0; fo(i,1,n)add(S,i,1);fo(i,1,m)add(i+n,T,1); fo(j,1,g){ add(j+n+m,g+j+n+m,1); fo(i,1,n)if(map[c*(b[i].x-1)+b[i].y][j]<=x/b[i].z)add(i,n+j+m,1); fo(i,1,m)if(map[j][c*(cc[i].x-1)+cc[i].y]<=x/cc[i].z)add(n+g+j+m,n+i,1); } } bool pan(){ int t=0; while(bfs())t+=dinic(S,n); if(t==n)return 1;return 0; } int main(){ scanf("%d%d%d%d",&rr,&c,&n,&m); g=rr*c; fo(i,1,rr){ scanf("%s",s[i]+1); fo(j,1,c)if(s[i][j]=='.')a[i][j]=1; } fo(i,1,g)fo(j,1,g)map[i][j]=da; fo(i,1,rr){ fo(j,1,c){ map[de(i,j)][de(i,j)]=0; if(!a[i][j])continue; fo(k,0,3){ xx=fang[k][0]+i,yy=fang[k][1]+j; if(xx<=rr&&xx>0&&yy<=c&&yy>0&&a[xx][yy]){ map[de(i,j)][de(xx,yy)]=1; } } } } fo(k,1,g)fo(i,1,g)fo(j,1,g)map[i][j]=min(map[i][j],map[i][k]+map[k][j]); scanf("%d%d%d",&x,&y,&z); fo(i,1,n){ scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z); } fo(i,1,m){ scanf("%d%d%d",&cc[i].x,&cc[i].y,&cc[i].z); } if(n<m)b[++n].x=x,b[n].y=y,b[n].z=z;else cc[++m].x=x,cc[m].y=y,cc[m].z=z; l=0,r=da; T=n+m+g+g+1; while(l<r){ mid=(l+r)/2; lian(mid); if(pan())r=mid;else l=mid+1; } if(l==da)printf("-1\n"); else printf("%lld\n",l); }