2014哈尔滨理工大学秋季训练赛
题意：有个N*N的房间，每个房间可能有人和逃生工具，A巨阵表示每个房间人数的状况，B巨阵表示每个房间的逃生工具数量的状况。现在那些人有 t 个时间去找逃生工具逃生，每个逃生工具只能给一个人使用。问最多有多少人逃生成功。 #include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define captype intconst int MAXN = 1010; //点的总数
const int MAXM = 400010; //边的总数
const int INF = 1<<30;
struct EDG{int to,next;captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN]; //每种距离(或可认为是高度)点的个数
int dis[MAXN]; //每个点到终点eNode 的最短距离
int cur[MAXN]; //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];void init(){eid=0;memset(head,-1,sizeof(head));
}
//有向边 三个参数，无向边4个参数
void addEdg(int u,int v,captype c,captype rc=0){edg[eid].to=v; edg[eid].next=head[u];edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v];edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));memcpy(cur,head,sizeof(head));pre[sNode] = -1;gap[0]=n;captype ans=0; //最大流int u=sNode;while(dis[sNode]<n){ //判断从sNode点有没有流向下一个相邻的点if(u==eNode){ //找到一条可增流的路captype Min=INF ;int inser;for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]) //从这条可增流的路找到最多可增的流量Minif(Min>edg[i].cap-edg[i].flow){Min=edg[i].cap-edg[i].flow;inser=i;}for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){edg[i].flow+=Min;edg[i^1].flow-=Min; //可回流的边的流量}ans+=Min;u=edg[inser^1].to;continue;}bool flag = false; //判断能否从u点出发可往相邻点流int v;for(int i=cur[u]; i!=-1; i=edg[i].next){v=edg[i].to;if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}//如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1int Mind= n;for(int i=head[u]; i!=-1; i=edg[i].next)if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){Mind=dis[edg[i].to];cur[u]=i;}gap[dis[u]]--;if(gap[dis[u]]==0) return ans; //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径//因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1gap[dis[u]]++;if(u!=sNode) u=edg[pre[u]^1].to; //退一条边}return ans;
}
struct NODE{int u , t;
};
int A[15][15],B[15][15],n,tim1 , dir[4][2]={0,1,0,-1,1,0,-1,0};
void bfs(int x,int y)
{queue<NODE>q;NODE now,pre;int S;bool vist[15][15]={0};now.u=x*n+y;now.t=tim1;S=now.u;vist[x][y]=1;q.push(now);while(!q.empty()){pre=q.front(); q.pop();x=pre.u/n; y=pre.u%n;if(B[x][y])addEdg(S , pre.u+n*n, INF);if(pre.t==0)continue;for(int e=0; e<4; e++){int tx=x+dir[e][0] , ty=y+dir[e][1];if(tx>=0&&tx<n&&ty>=0&&ty<n&&vist[tx][ty]==0){vist[tx][ty]=1;now.u=tx*n+ty;now.t=pre.t-1;q.push(now);}}}
}
int main()
{while(scanf("%d%d",&n,&tim1)>0){int vs,vt ;vs = n*n*2 ;vt = vs+1;init();for(int i=0; i<n; i++)for(int j=0; j<n; j++){scanf("%d",&A[i][j]);if(A[i][j])addEdg(vs , i*n+j , A[i][j]);}for(int i=0; i<n; i++)for(int j=0; j<n; j++){scanf("%d",&B[i][j]);if(B[i][j])addEdg(i*n+j+n*n , vt, B[i][j]);}for(int i=0; i<n; i++)for(int j=0; j<n; j++)if(A[i][j])bfs(i,j);printf("%d\n",maxFlow_sap(vs , vt , vt+1));}
}
|
