TTTTTTTTTTTTT poj 3057 Evacuation 二分图匹配+bfs
2024-10-07 02:04:28
题意：见挑战230页
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
int n,m,x,y;
vector<int> G[100005];
vector<int> dx,dy,px,py;
char field[15][15];
int xx[4]={-1,1,0,0},yy[4]={0,0,1,-1};
int sroad[15][15][15][15],dist[15][15];
int used[30000],match[1000000];
void add_edge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
dist[x][y]=0;
queue<int> qx,qy;
qx.push(x);
qy.push(y);
while(!qx.empty())
{
int sx=qx.front();
int sy=qy.front();
for(int i=0;i<=3;i++)
{
int tx=sx+xx[i],ty=sy+yy[i];
if(tx>=0&&tx<n&&ty>=0&&ty<m)
if(field[tx][ty]=='.'&&dist[tx][ty]<0)
{
dist[tx][ty]=dist[sx][sy]+1;
sroad[x][y][tx][ty]=dist[tx][ty];
qx.push(tx);
qy.push(ty);
}
}
qx.pop();
qy.pop();
}
}
int dfs(int u)
{
used[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i],w=match[v];
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
return 1;
}
}
return 0;
}
int pipei(int t)
{
int res=0;
for(int i=0;i<dx.size();i++)
{
int u=i+t*dx.size();
if(match[u]<0)
{
memset(used,0,sizeof(used));
if(dfs(u))
res++;
}
}
return res;
}
int num(int t)
{
for(int i=0;i<px.size();i++)
for(int j=0;j<dx.size();j++)
{
int renx=px[i],reny=py[i];
int menx=dx[j],meny=dy[j];
if(sroad[menx][meny][renx][reny]<=t)
add_edge(t*dx.size()+j,(n*m+10)*dx.size()+10+i);
}
return pipei(t);
}
void solve()
{
memset(match,-1,sizeof(match));
int ans=0;
for(int t=0;t<=n*m+3;t++)
{
ans+=num(t);
if(ans>=px.size())
{
cout<<t<<endl;
return;
}
}
cout<<"impossible"<<endl;
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
scanf("%d %d",&n,&m);
dx.clear();dy.clear();
px.clear();py.clear();
for(int i=0;i<=100005;i++)
G[i].clear();
for(int i=0;i<n;i++)
scanf("%s",field[i]);
memset(sroad,inf,sizeof(sroad));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(field[i][j]=='D')
{
dx.push_back(i);
dy.push_back(j);
bfs(i,j);
}
else if(field[i][j]=='.')
{
px.push_back(i);
py.push_back(j);
}
}
solve();
}
return 0;
}
分析：强大的二分匹配（因为一个门一时刻只能通过一个人），这是我的做法，用的是枚举时间
不过看挑战上是直接枚举时间和门组成的二元组的点，每次dfs该点，进行一次匈牙利算法，最后再算出时间
好像程序可以简化一点，不过我的这份代码的效率比较高，排名在270多名，不过开的数组大小很关键，在这个上wa了很多次。
下面是wa代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
int n,m,x,y;
vector<int> G[1005];
vector<int> dx,dy,px,py;
char field[15][15];
int xx[4]={-1,1,0,0},yy[4]={0,0,1,-1};
int sroad[15][15][15][15],dist[15][15];
int used[150],match[10000];
void add_edge(int u,int v)
{
G[u].push_back(v);
G[v].push_back(u);
}
void bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
dist[x][y]=0;
queue<int> qx,qy;
qx.push(x);
qy.push(y);
while(!qx.empty())
{
for(int i=0;i<=3;i++)
{
int tx=qx.front()+xx[i],ty=qy.front()+yy[i];
if(tx>=0&&tx<n&&ty>=0&&ty<m)
if(field[tx][ty]=='.'&&dist[tx][ty]<0)
{
dist[tx][ty]=dist[x][y]+1;
sroad[x][y][tx][ty]=dist[tx][ty];
qx.push(tx);
qy.push(ty);
}
}
qx.pop();
qy.pop();
}
}
int dfs(int u)
{
used[u]=1;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i],w=match[v];
//printf("%d %d\n",v,match[v]);
// printf("match: %d w:%d\n",match[v],w);
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
//printf("wwwww\n");
return 1;
}
}
return 0;
}
int pipei(int t)
{
int res=0;
for(int i=0;i<dx.size();i++)
{
int u=i+t*dx.size();
//printf("4 match:%d\n",match[0]);
if(match[u]<0)
{
memset(used,0,sizeof(used));
if(dfs(u))
res++;
}
}
// printf("res:%d\n",res);
return res;
}
int num(int t)
{
for(int i=0;i<px.size();i++)
for(int j=0;j<dx.size();j++)
{
int renx=px[i],reny=py[i];
int menx=dx[j],meny=dy[j];
if(sroad[menx][meny][renx][reny]<=t)
add_edge(t*dx.size()+j,px.size()*dx.size()+10+i);
}
//printf("3 match:%d\n",match[0]);
return pipei(t);
}
void solve()
{
memset(match,-1,sizeof(match));
//printf("1 match:%d\n",match[0]);
int ans=0;
for(int t=0;t<=n*m+3;t++)
{
ans+=num(t);
//cout<<t<<" "<<num(t)<<endl;
//printf("2 match:%d\n",match[0]);
if(ans>=px.size())
{
cout<<t<<endl;
return;
}
}
cout<<"impossible"<<endl;
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
scanf("%d %d",&n,&m);
dx.clear();dy.clear();
px.clear();py.clear();
for(int i=0;i<=500;i++)
G[i].clear();
for(int i=0;i<n;i++)
scanf("%s",field[i]);
memset(sroad,inf,sizeof(sroad));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(field[i][j]=='D')
{
dx.push_back(i);
dy.push_back(j);
bfs(i,j);
}
else if(field[i][j]=='.')
{
px.push_back(i);
py.push_back(j);
}
}
solve();
}
return 0;
}
最新文章
- Signlar
- php中opendir函数用法实例
- 让计算机崩溃的python代码，求共同分析
- mfc/格式转换
- PHP面向对象程序设计的61条黄金法则
- JNI字段描述符-Java Native Interface Field Descriptors
- Ubuntu 13.10下Hadoop 2.2 安装、配置、编译（伪分布式）
- TT付款方式、前TT和后TT、LC信用证+TT付款方式
- BZOJ 1051: [HAOI2006]受欢迎的牛 缩点
- 获取API返回值
- spoj cot: Count on a tree 主席树
- HDU 3264 Open-air shopping malls （计算几何-圆相交面积）
- pubwin数据云备份
- Jasper_pass data_from main report to subReport (local CSV)
- CSV 客座文章系列：KGroup 通过 Windows Azure 将 Qoob 内容管理发布到云中
- 说说BroadcastReceiver和ContentProvider
- 走进Linux01-磁盘分区与文件夹结构
- Caused by: java.lang.ClassNotFoundException: javax.persistence.Entity
- 使用javamelody进行web监控
- 保存一个经常用的Makefile