poj 3057 Evacuation //二分图匹配（匈牙利算法模板）
题意，每个'.'可以通过D逃生，但是每一个门不能同时通过多个'.'，求最小时间。
建立二分图，左边是人，右边是 每个门的每个时间点，连接合法的逃生路径(即某人逃出的某个门的时间要大于最短距离，最短距离提前bfs预处理)，那么求最大匹配(匈牙利）即可。
一开始用最大流求，然后挂了。。。。。。。。。
又学了一下匈牙利算法，刚好过，时间卡的nice
正解匈牙利算法复杂度O(EV) 即 O(N^6) (都最坏）
最大流求解复杂度最坏O(EV^2*lg)
代码写的很烂。凑合
细节看代码。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<climits>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define LL long long
#define mod 1000000007
const int maxn=60000; //好像开大了一倍
const int N=13*13; //最多的人数
struct no{int to,cap,rev;}; //arc
struct bfsno{int h,l,step;}; //bfs结点
char mp[20][20]; //存储图
int doornum[20][20]; // 门加上编号的图
int go[4][2]={0,1,1,0,-1,0,0,-1};
vector<int>g[maxn]; //最后的图
int used[maxn],match[maxn];
int pp=0,dop; //总人数，总门数
int up=0; //最后图中点数的上限
int n,m;
void finddoor(int x,int y,int ii){//bfs找每个人能到点
bool vis[20][20];
memset(vis,0,sizeof(vis));
queue<bfsno>q;
while(!q.empty()) q.pop();
q.push((bfsno){x,y,0});
vis[x][y]=1;
while(!q.empty()){
bfsno now= q.front();q.pop();
if(mp[now.h][now.l]=='D') {
for(int i=now.step;i<=m*n;i++){
int xx=pp+(dop+1)*i+doornum[now.h][now.l]; //注意hash 不要点重复，保证人，时间点和每个门对于的笛卡尔积不重复
// cout<<ii<<' '<<xx<<' '<<now.h<<' '<<now.l<<endl;
up=max(up,xx);
g[xx].push_back(ii);
g[ii].push_back(xx);
}
continue;
}
for(int i=0;i<=3;i++){
int th=now.h+go[i][0];
int tl=now.l+go[i][1];
if(mp[th][tl]=='X'||vis[th][tl])continue;
vis[th][tl]=1;
q.push((bfsno){th,tl,now.step+1});
}
}
}
bool HA(int v){ //dfs找增广路
used[v]=1;
for(int i=0;i<g[v].size();i++){
int u=g[v][i],w=match[u];
if(w<0||!used[w]&&HA(w)){
match[u]=v;
match[v]=u;
return 1;
}
}
return 0;
}
int bipartite_matching(){
int res=0;
memset(match,-1,sizeof(match));
for(int v=pp+1;v<=up;v++){ //直接按照时间点往后面找
if(match[v]<0){
memset(used,0,sizeof(used));
if(HA(v))
res++;
if(res==pp) return (v-pp)/(dop+1); //注意还原的方式，对应好hash的方式，保证其准确性
}
}
return -1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>mp[i];
dop=0;pp=0;up=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='D') doornum[i][j]=++dop;
if(mp[i][j]=='.') ++pp;
}
}
int p=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='.') {
finddoor(i,j,++p);
}
}
}
int ans=bipartite_matching();
if(ans==-1) cout<<"impossible"<<endl;
else cout<<ans<<endl;
for(int i=0;i<=up;i++) g[i].clear();
}
return 0;
}匈牙利算法模板
bool HA(int v){ //dfs找增广路
used[v]=1;
for(int i=0;i<g[v].size();i++){
int u=g[v][i],w=match[u];
if(w<0||!used[w]&&HA(w)){
match[u]=v;
match[v]=u;
return 1;
}
}
return 0;
}
int bipartite_matching(){ //记得加入双向边
int res=0;
memset(match,-1,sizeof(match));
for(int v=pp+1;v<=up;v++){ //直接按照时间点往后面找
if(match[v]<0){
memset(used,0,sizeof(used));
if(HA(v))
res++;
}
}
return res;
}贴一下自己又丑又长的最大流超时解法（不过挺酷的）。
二分+最大流（DInic）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<climits>
#include<cmath>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define LL long long
#define mod 1000000007
const int maxn=6000;
const int N=13*13; //最多的人数
struct no{int to,cap,rev;}; //arc
struct bfsno{int h,l,step;}; //bfs结点
char mp[20][20]; //存储图
int doornum[20][20];
int go[4][2]={0,1,1,0,-1,0,0,-1};
vector<bfsno>v[400]; //存储每一个人到出口的距离
vector<no>g[60000]; //图
int level[maxn]; //到起点的距离
int iter[maxn]; //当前弧，在其之前的边已经没用了
int pp=0,dop; //总人数
void addarc(int s,int e,int c){
g[s].push_back((no){e,c,g[e].size()});
g[e].push_back((no){s,0,g[s].size()-1});
}
//更新层次，即level
void bfs(int s){
memset(level,-1,sizeof(level));
level[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<(int)g[now].size();i++){
no &arc=g[now][i];
if(level[arc.to]!=-1||arc.cap<=0) continue;
level[arc.to]=level[now]+1;
q.push(arc.to);
}
}
}
//寻找增广路
int dfs(int v,int t,int f){
if(v==t) return f;
for(iter[v];iter[v]<(int)g[v].size();iter[v]++){
no &arc=g[v][iter[v]];
if(arc.cap<=0||level[arc.to]!=level[v]+1) continue;
int d=dfs(arc.to,t,min(f,arc.cap));
if(d>0) {
arc.cap=arc.cap-d;
g[arc.to][arc.rev].cap+=d;
return d;
}
}
return 0;
}
int Dinic(int s,int t){
int re=0;
while(1){
bfs(s);
memset(iter,0,sizeof(iter));
if(level[t]==-1) return re;
int f;
while((f=dfs(s,t,INT_MAX))>0)
re=re+f;
}
return re;
}
void finddoor(int x,int y,int ii){//bfs找每个人能到点
bool vis[20][20];
memset(vis,0,sizeof(vis));
queue<bfsno>q;
while(!q.empty()) q.pop();
q.push((bfsno){x,y,0});
vis[x][y]=1;
while(!q.empty()){
bfsno now= q.front();q.pop();
if(mp[now.h][now.l]=='D') {
v[ii].push_back((bfsno){now.h,now.l,now.step});
continue;
}
for(int i=0;i<=3;i++){
int th=now.h+go[i][0];
int tl=now.l+go[i][1];
if(mp[th][tl]=='X'||vis[th][tl])continue;
vis[th][tl]=1;
q.push((bfsno){th,tl,now.step+1});
}
}
}
int bipartite_matching(int tt){
int carc=0; //求边总数
for(int i=1;i<=pp;i++){
for(int j=0;j<v[i].size();j++){
int x=v[i][j].h,y=v[i][j].l,t=v[i][j].step;
for(int k=t;k<=tt;k++){
int to=pp+dop*k+doornum[x][y];
addarc(i,to,1);
carc=max(carc,to);
}
}
}
for(int i=1;i<=pp;i++) addarc(0,i,1); //人连超级源点
for(int i=pp+1;i<=carc;i++) addarc(i,carc+1,1);
int re=Dinic(0,carc+1);
for(int i=0;i<=carc+2;i++) g[i].clear();
return re;
}
bool check(int m){
if(bipartite_matching(m)==pp) return 1;
return 0;
}
int binary(int l,int r){ //二分
int res=INT_MAX;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int T;cin>>T;
while(T--){
int n,m;cin>>n>>m;
for(int i=0;i<n;i++) cin>>mp[i];
dop=0;pp=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mp[i][j]=='.') {
finddoor(i,j,++pp);
}
if(mp[i][j]=='D') doornum[i][j]=++dop;
}
}
int ans=binary(1,m*n+1);
if(ans==INT_MAX) cout<<"impossible"<<endl;
else cout<<ans<<endl;
for(int i=0;i<=pp;i++) v[i].clear();
}
return 0;
}