网络流强化-HDU2732
第一次遇到加了“多余”的边会导致WA的——在我看来是很多余，见代码191行
之后会思考为什么，想出来再更。
问题弄明白了，如果你在连接边连了一条到没有柱子的点的边，这个没有柱子的点是不可能连到终点的，所以在BFS划分层次的时候就不会设置它的层次，也就是说默认为0，刚好和终点的层次相同，那么当走到这个点的时候，由于他和其他的点完全不连通，所以就会进入层次更新关节，里面有句话是是
if (--num[d[u]] == 0) break; // gap 优化
所以导致直接就退出了，没有给终点来一次机会——终点为层次0做出了唯一一次贡献，但是被这个来历不明的点“狸猫换太子”了。
解决办法有两种：
1：将起始层次设置为1
2：保证连接的边都是实际能走的路
好的，第一种错了，第一种只能保证第四个样例是对的。
让我查了错再更。2019年8月17日15:16:24
初步的查错是他居然过不了样例4——原来之前遗留的d可能会被用到没有柱子的点（实验前提：起始层次为1），所以我的d数组也每次都重置。 能过样例，但是WA了。
2019年8月17日22:44:50更新：
查出来了，原因还是在更新层次的时候，涉及到了没有柱子的点，这时候没有柱子的点的层次是0，会作为剩余连接点中层次最低的点去更新当前点的层次值——显然不合理，因为层次值每次是应该变得更大的。
2019年8月18日10:02:50
其实昨天就已经又查出来一个问题了：我是想让终点的起始层次为0，然后不连接非法（没有柱子）的点，然后还把num、vis、d三个数组一起初始化为0——修改模板。但是提交后WA了。
今天查错：发现如果起点连接了一个蜥蜴的点，但是这个蜥蜴的点和终点并不连通，这时候会出现这个蜥蜴的点层次依旧为0——好的，等到起点要走这个点发现走不通，这个点是不是要执行--num[d[u]]的操作——刚好和终点的层次撞上了。
所以：网络流建图
确保所有的点都要和终点连通——这样才是合法的点
至于这样的组合能过全部样例不能过单个样例：for(i=0;i<=t;++i) vis[i]=num[i]=0; d[t] = 0;
只能说之前的样例会让d[45]的值不是0吧。
只有这样才能保证是完全对的： for(i=0;i<=t;++i) vis[i]=num[i]=d[i]=0; d[t] = 1;
我们会发现num[0] = 0,d[45]=0,45号点不能走通，--num[0]= -1 != 0 不会跳出循环 所以能继续执行
单个样例：
1 1 2 3 11 1 4 11211221 5 31310220 6 02220113 7 23001302 8 00103033 9 33300203 10 33030032 11 20013100 12 30132221 13 33310002 14 32232333 15 .L..L.LL 16 .LL..LL. 17 ..LL.... 18 LL..LL.L 19 ......LL 20 .LL..L.. 21 .L.....L 22 ...LL... 23 L.LL...L 24 L..L...L 25 .L.L....
我觉得最好的办法是完全排除非法的点（无柱子的点，有柱子但是不能逃出火场的点）
或者简单一点把所有的d一开始置为inf，那么对于非法的点，由于d=inf，所以在选择剩余距离最小的点中根本就不会选择这个点。
这样一来，最后起点无法增广到终点的情况下，起点的d最终会被突破上限而最终跳出循环（或者中途发现中间层次缺失跳出循环）。
最终成品：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 #define maxe 25600 //pay 双向边 一共10万条路 双向就是20万 反边就是40万 6 #define maxv 1024 //pay 7 #define maxn 25 //pay 8 #define sc scanf 9 #define pt printf 10 #define rep(i,a,b) for(int i=(a);i<(b);++i) 11 const int inf = 0x3f3f3f3f; 12 int cg,sp,ins; //cg change sp是总流量 ins是加速回溯点 13 int N,M,T,D ,s,t,delta,UP_LIMIT; 14 int q[maxv],fro,rea; 15 typedef struct ed{ 16 int v,nxt,cap; //dis 17 }ed; 18 ed e[maxe]; 19 int tot,head[maxv],cur[maxv],vis[maxv],bk[maxv],d[maxv],num[maxv]; // 20 int mi(int a,int b) {return a<b?a:b;} 21 int mx(int a,int b) {return a>b?a:b;} 22 void add(int u,int v,int cap) 23 { 24 e[tot].v=v; e[tot].nxt=head[u]; 25 /*e[tot].dis=dis;*/ e[tot].cap=cap; 26 head[u]=tot++; 27 28 e[tot].v=u; e[tot].nxt=head[v]; 29 /*e[tot].dis=-dis;*/ e[tot].cap=0; 30 head[v]=tot++; 31 } 32 // 仅有一次的BFS为ISAP节省了不少时间 33 bool bfs() 34 { 35 //数组模拟queue 36 int u,v,i,my_all = t; 37 for(i=0;i<=my_all;++i) vis[i]=num[i]=0; //无须一定是my_all，涉及所有即可~~~~~~~~~~~~~~~~~~ 38 for(i=0;i<=my_all;++i) d[i]=UP_LIMIT; //UP_LIMIT的设定是比最高的层次大1 39 fro = rea = 0; 40 q[rea] = t; ++rea; 41 vis[t] = 1; 42 d[t] = 0; 43 ++num[d[t]]; 44 while (rea>fro) 45 { 46 u = q[fro]; ++fro; 47 for (i=head[u]; i!=-1; i=e[i].nxt) 48 { 49 v=e[i].v; 50 if (!vis[v] && e[i^1].cap ) 51 { 52 vis[v] = true; 53 d[v] = d[u] + 1; 54 ++num[d[v]]; 55 q[rea] = v; ++rea; 56 //pt("普度众生 u=%d,v=%d,d[u]=%d,d[v]=%d ",u,v,d[u],d[v]); 57 } 58 } 59 } 60 int last_ed=-1; 61 //把连接了到不了终点的点的边都去除 62 for(u=0;u<=my_all;++u) 63 { 64 if(!vis[u]) continue; 65 for (i=head[u]; i!=-1; i=e[i].nxt) 66 { 67 v=e[i].v; 68 if(!vis[v]) 69 { 70 if(i==head[u]){ 71 head[u] = e[i].nxt; 72 continue; 73 } 74 else{ 75 e[last_ed].nxt = e[i].nxt; 76 continue; 77 } 78 } 79 last_ed = i; 80 } 81 } 82 return vis[s]; 83 } 84 // 增广 85 int augment()/*单源单汇 不用查这个*/ 86 { 87 int flow = inf, i; 88 cg = t; 89 // 从汇点到源点通过 p 追踪增广路径, flow 为一路上最小的残量 90 while (cg != s) { 91 i = bk[cg]; 92 if(flow>=e[i].cap) 93 { 94 flow = e[i].cap; 95 ins = e[i^1].v; 96 //用来加速寻找，在最小流量断开的地方重新开始寻找 97 //嗯，等一下 我这个是从终点往起点寻找，而确定增光路径是从起点到终点 98 //那么起点是河流的上游，那么回溯的河段应该尽可能的往上游靠近 99 //所以应该将flow>e[i].cap的大于号改成大于等于号 100 } 101 cg = e[i^1].v; 102 } 103 cg = t; 104 // 从汇点到源点更新流量 105 while (cg != s) { 106 i = bk[cg]; 107 e[i].cap -= flow; 108 e[i^1].cap += flow; 109 cg = e[i^1].v; 110 } 111 return flow; 112 } 113 //由于每次修改层次的时候，都是在到剩下子节点的距离中挑选最短的加1 所以层次分明不会出现死循环 114 int max_flow() 115 { 116 int flow = 0,i,u,v; 117 bool advanced; 118 if(bfs()==false) return 0; 119 // pt("零层妖塔=%d ",num[0]); 120 //不一定是从s到t，你要知道统计每个层次的点的个数是全局统计的 121 u = s; 122 memcpy(cur, head, sizeof(head)); 123 while (d[s] < UP_LIMIT) //UP_LIMIT的设定是比最高的层次大1 124 //终点是0，那么起点所在层次最多是N-1 同理，不是d[s]<t 125 { 126 if (u == t) 127 { 128 flow += augment(); 129 u = ins; //pay speed up 130 } 131 advanced = false; 132 for (i = cur[u]; i!=-1; i=e[i].nxt) 133 { 134 v = e[i].v; 135 //pt("SELECT: %d -> %d ",u,v); 136 if (e[i].cap && d[u] == d[v] + 1) 137 { 138 advanced = true; 139 bk[v] = i; 140 cur[u] = i; 141 // pt("%d -> %d ::d[u]=%d,d[v]=%d ",u,v,d[u],d[v]); 142 u = v; 143 break; 144 } 145 } 146 if (!advanced) 147 { // retreat 148 int base = UP_LIMIT; //UP_LIMIT的设定是比最高的层次大1 149 for (i = head[u]; i != -1; i=e[i].nxt) 150 { 151 if (e[i].cap&&base>d[e[i].v]) 152 { 153 cur[u] = i; 154 base = d[e[i].v]; 155 } 156 } 157 158 if (--num[d[u]] == 0) 159 { 160 //pt("u=%d,d=%d ",u,d[u]); 161 //pt("BREAK FROM HERE "); 162 break; // gap 优化 163 } 164 ++num[d[u] = base+1]; 165 //pt("------------------我来增加层次%d：%d ",m+1,u); 166 //我以前一直在想 如果没有找到怎么办呢 现在发现原来找不到的话距离会被赋成base+1 167 //—— 比上界还高 所以接下来不会再访问到这个点 这个点也没有机会被减成0了——不会莫名其妙地break，哈哈哈 168 if (u != s) 169 { 170 //pt("from %d ",u); 171 u = e[bk[u]^1].v; 172 //pt("return to %d ",u); 173 } 174 else 175 { 176 // pt("STILL AT S:%d ",s); 177 } 178 } 179 } 180 return flow; 181 } 182 183 void init() 184 { 185 tot=0; 186 memset(head,-1,sizeof(head)); //pay 187 } 188 char times[maxn][maxn],haves[maxn][maxn]; 189 //最大流部分没有什么问题了 关键在于终点源点、编号分配、题目理解建图上面 190 //切记：不要建立无用的边！！ 包括连接不到的点 和不和终点连通的点 191 //确保所有的点都要和终点连通——这样才是合法的点 192 int main() 193 { 194 freopen("in.txt","r",stdin); 195 sc("%d",&T); 196 /*数据初始化区*/ 197 s=0, bk[0]=-1; 198 199 /*变量存放区*/ 200 int i,j,u,v,id,can,kase=0,who,LI; 201 202 while(T--) 203 { 204 ++kase; 205 sc("%d%d",&N,&D); 206 207 /*数据初始化区*/ 208 init(); sp = LI = 0; 209 210 /*数据读取区*/ 211 for(i=0;i<N;++i) sc("%s",times[i]); 212 for(i=0;i<N;++i) sc("%s",haves[i]); 213 214 /*关键数据赋值区*/ 215 M=strlen(times[0]); delta = (N)*(M); t=2*delta+1; s=2*delta; 216 UP_LIMIT = 2*delta + 2; 217 //说明：这个是层次的无法达到的上界，所以一共有N个点的时候， 218 //如果从0开始编号，那么上界就是N；如果从1开始编号，上界就是N+1 219 220 /*建图区*/ 221 for(i=0;i<N;++i) for(j=0;j<M;++j) 222 { 223 can = times[i][j]-'0'; 224 if(can==0) continue; 225 id = i*(M) + (j); 226 add(id,id + delta,can ); 227 } 228 for(i=0;i<N;++i) for(j=0;j<M;++j) 229 { 230 if(haves[i][j]!='L') continue; 231 id = i*(M) + (j); 232 add(s,id,1); 233 ++LI; 234 } 235 for(i=0;i<N;++i) for(j=0;j<M;++j) 236 { 237 if(times[i][j]=='0') continue; //这里写成过有没有蜥蜴的那个矩阵 238 id = i*(M) + (j); 239 if(i-D<0||i+D>N-1||j-D<0||j+D>M-1) add(id+delta,t,inf); 240 for(u=mx(0,i-D);u<=mi(N-1,i+D);++u) for(v=mx(0,j-D);v<=mi(M-1,j+D);++v) 241 { 242 //下面这一行居然是决胜关键 可是废点不是完全不会走吗 243 if(times[u][v]=='0') continue; 244 if(u==i&&v==j) continue; 245 //这是最终确定的可跳跃方式，他这个居然是曼哈顿距离 待会交一下看一下是不是这样 wa 了 246 if(abs(u-i)+abs(v-j)>D) continue; 247 who = u*(M) + (v); 248 add(id+delta,who,inf); 249 } 250 } 251 252 /*答案处理区*/ 253 sp = max_flow(); 254 int ans = LI-sp; 255 if(ans==0) printf("Case #%d: no lizard was left behind. ",kase); 256 else if(ans==1) printf("Case #%d: 1 lizard was left behind. ",kase); 257 else printf("Case #%d: %d lizards were left behind. ",kase,ans); 258 } 259 return 0; 260 } 261 262 /** 263 * 友情链接： 264 * http://www.renfei.org/blog/isap.html 解释ISAP原理 265 * https://www.cnblogs.com/bosswnx/p/10353301.html 使用的数据结构和我的比较相近 266 */