HDU-6749mosquito(2020年百度之星编程竞赛-首战一1007 ) 2020.7.21
sample input 25541101510511051105510551033118 sample output4- 1主题链接： hdu-6749
2020百度之星首战1007
分析：共有m*n个格点，窗户都在边上。 蚊子每秒可以移动一帧。 询问每个网格有一只蚊子要花多长时间。
首先我们可以知道答案是否存在。 如果所有窗户上的蚊子总数少于网格点总数，肯定无法完成任务。 相反，答案一定存在。 一扇窗户的蚊子飞到某个目标网格所需的最小时间是窗户和目标网格的曼哈顿距离。 问题满足两个性质，即时间越长越有可能满足条件。 答案的下限是0。 因为从一开始就有可能符合条件。 的上限是m n-2。 因为这是格点中最远的两点曼哈顿距离。
现在，考虑如何检查，因为给定了限制时间t，所以要验证能否满足主题的条件。 因为蚊子的数量不变，所以一只蚊子去了网格点a就不能去网格点b。 这满足网络流动的性质。 可以通过网络的流程来判断。 我们考虑如何构图。
首先，可以创建源点s和汇点t。 因为窗口的数量不超过6个，所以为每个窗口创建一个节点。 第I个窗口有a[i]只蚊子，所以制作从源点到窗口I的权重为a[i]的边，将输入的总流量限制为蚊子之和。
很明显，每个网格可以创建一个节点，一共将创建n*m个节点。 我们为了让蚊子能从各窗户在各t时间内到达网格，权重无限大(这里用a[i]就可以了。 因为这个窗户最多有这么多蚊子)的边缘。 而且，到点t为止的权重为1的边与各网格点相连。 这样，从s到t的最大流程就是t时间内蚊子最能覆盖的网格点数量。 最大流等于总网格点数n*m时可以，否则不行。但是我们发现这样图的结点太多，我们考虑是否可以合并结点。因为对于每个窗户的蚊子是否可达，很多格点的情况都是一样的。我们可以根据窗户上的蚊子是否能到达进行分类。 只有小组有六个窗户很多。 每扇窗户能否到达，用0.1列表示。 那么，在二进制压缩状态下，最多可以达到2^6=64种状态。 那么可以根据t时间内所有窗蚊的可达情况将n*m个网格划分为2^k类，并将各类所有网格合并为一个节点。 的状态为x，x的二进制的第I个比特为1，则从第I个窗口到状态x的节点的权重为无限大的边。 当然，计数各状态分类中有多少个节点，即cnt[x]，各节点形成与具有cnt[x]权重的宿t相连的边缘。 到此为止，直接行驶最大流，判断最大流是否达到m*n即可。
方法：统计蚊虫总数，若蚊虫总数小于格点总数，直接输出-1，结束。 如果蚊子总数=网格点总数，就一定会有答案。 我们可以把答案一分为二。 回答范围为[0，Mn-1]check回答时使用网络流。 首先，考虑增加源点s和汇点t。 每个窗口是一个节点，从源点到第I个窗口连接权重a[i]的单向边缘。 将网格点分为2^w类，其中w是窗户的数量。 每班状态为x(0x2^w )。 状态x的二进制第I位为1意味着在当前时刻t窗I的蚊子可以到达这样的网格点。 统计cnt[x]是满足状态x的格点数。 为每个状态创建一个节点。 各状态x在汇点t上连接权重为cnt[x]的边缘。 如果第I个位为1，则各状态x只要从第I个窗将权重无限大的边a[i]连接到该状态x即可。 构图只要能行驶从s到t的最大流，最大流达到m*n即可。 可以将节点号分配为M=2^w。 状态0到M-1的号码本身。 表示第I个窗口的节点编号为mI(0=iw )，s编号为M w，t编号为M w 1。最大流可以使用最常用的dinic算法。 决定构图的时候，如果制作权重为0的反方向的话，容易产生“反感”。 每当dfs要求加宽大路时。 可以在dfs之前用bfs将图分层为dep，扩大道路深度路径的dep只能增加。 代码： # include bits/stdc.husingnamespacestd； const int N=1001； int x[6]、y[6]、a[6]、dis[n][6]、m、n、w； int cnt[16]； //cnt[i]是state[i]的格子的个数struct Node{int to，next，d； }node[2000]； //链式前方星构图int head[100]、tot、cur[100]、dep[100]、s、t； voidaddedge(intu，int v，int d ) {node[tot].to=v； node[tot].d=d； node[tot].next=head[u]； head[u]=tot； }void initEdge () {tot=0； memset(head，-1，sizeof ) ) head )； }voidaddedge(intu，int v，int d ) addedge ) u，v，d )； addedge(v，u，0 )； //边翻转}bool bfs () memset (dep，-1，sizeof ) ) dep )； dep[S]=0； queueint根据到源点的步骤数对图进行分层
Q;Q.push(S);while(!Q.empty()) {int u = Q.front(); Q.pop();for(int i=head[u];i!=-1;i=node[i].next) {int to = node[i].to;if(dep[to]==-1&&node[i].d>0) //流量分配完的结点不分配深度 dep[to] = dep[u]+1,Q.push(to);}}return dep[T]!=-1;}int dfs(int u,int flow) {if(u==T) return flow;int sum = 0;for(int& i=cur[u];i!=-1;i=node[i].next) { //当前弧优化 int to = node[i].to;if(dep[to]==dep[u]+1&&node[i].d>0) {int add = dfs(to,min(flow,node[i].d));sum += add; //记录增广路之和 flow -= add; //减去已经分配过的流量 node[i].d -= add;node[i^1].d += add; //i^1为反向边 }if(flow==0) break;}if(sum==0) dep[u] = -1;return sum; }int dinic() {int ans = 0;while(bfs()) {for(int i=0;i<=T;++i) cur[i] = head[i];ans += dfs(S,m*n);} return ans;}bool check(int t) {memset(cnt,0,sizeof(cnt));int M = 1<<w;for(int i=0;i<n;++i) for(int j=0;j<m;++j) {int x = 0; //记录各窗户蚊子在时间t下到格点(i,j)的可达状态 for(int k=0;k<w;++k)if(dis[i][j][k]<=t) x|=(1<<k);cnt[x]++; //状态计数 }//结点编号：状态0~M-1,就是本身的编号，M+0~M+w-1是窗户的编号initEdge();//初始化前向星 S = M+w; T = S+1; for(int i=0;i<M;++i) {AddEdge(i,T,cnt[i]); //状态到终点的边，为满足该条件的格子的个数for(int k=0;k<w;++k) {if(i&(1<<k)) AddEdge(M+k,i,a[k]);//连一条无穷大的边(最大为a[k]) } }for(int k=0;k<w;++k) //起点到窗户的边，最大流量为a[i] AddEdge(S,M+k,a[k]);return dinic()==n*m; }int main(void) {int Ca;scanf("%d",&Ca);while(Ca--) {int sum = 0;scanf("%d%d%d",&n,&m,&w);for(int i=0;i<w;++i) scanf("%d%d%d",x+i,y+i,a+i),sum+=a[i],x[i]--,y[i]--; //数据下标从1开始 if(sum<m*n) {puts("-1");continue;}for(int i=0;i<n;++i) //预处理每个坐标和窗户的曼哈顿距离 for(int j=0;j<m;++j)for(int k=0;k<w;++k)dis[i][j][k] = abs(i-x[k])+abs(j-y[k]); //预处理每个结点到每个窗口的距离 int left = -1,right = m+n-1;while(right-left>1) { //[) int mid = (left+right)>>1;if(check(mid)) right = mid;else left = mid;}printf("%dn",right);}return 0;}