[CQOI2017]老C的方块 网络流
题解：
做这题做了好久，，，换了4种建图QAQ
首先我们观察弃疗的形状，可以发现有一个特点，那就是都以一个固定不变的特殊边为中心的，如果我们将特殊边两边的方块分别称为s块和t块，
那么我们可以观察到，s块和t块永远是在中心位置，而其他两块则是紧邻s块和t块，一边一个。
所以我们要考虑将这个图像用一根线串起来，这样跑最小割才能割最小的边，
那么如何做到一条边割几个图形呢？
首先我们观察到一个非st方块本来就可以属于多个图形，因此也会有多条连边，因此我们只需要对每个方块拆点，限制其只能割一次就可以了。
一开始我选择的连图方式是：
以特殊边左边为s块，右边为t块，s连向s块，t块连向t（s块和t块名字来源），s块连向四周的非t块，t块四周的非s块连向它，s块四周的非t块连向t块四周的非s块。
但这样为什么这样不行呢？
我们可以观察到这样一种情况，
可以发现，右边的小圆圈同时处在s块和t块周围，那么由于扮演了两个角色，这就有可能导致右边的s块的流量流到左边的t块里，于是就出现了不合法情况。
…………
遂交换偶行的s块和t块。
可以发现，右边的s块和左边的t块构成了一个不合法图形，那么这是为什么？
显然是上面反过来的t块和s块在勾桥搭线。。。。
那怎么办？
我们再观察一下图形。既然所有图形都是以s块和t块为中心，那么这两块显然是更加稳定的，因此我们不再用其他块作为中转块，而是采用以s块和t块为中转。
即：
s ---> s块周围的块 ----> s块 ---> t块 ---> t块周围的块
经验证，可以满足要求。
我是强行暴力人工分类讨论建图的。。。因此代码很长，建图就有60行。。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define inf 2139062143 5 #define getchar() *o++ 6 #define AC 200100 7 #define ac 1700000 8 9 char READ[7001000], *o = READ; 10 int n, x, ans, s, t, addflow, X, Y; 11 int last[AC], good[AC], have[AC], c[AC], power[AC]; 12 int q[AC], head, tail; 13 int date[ac], Next[ac], haveflow[ac], Head[AC], tot = 1; 14 15 struct point{ 16 int x, y; 17 }p[AC]; 18 19 bool operator < (point a, point b) 20 { 21 if(a.x != b.x) return a.x < b.x; 22 else return a.y < b.y; 23 } 24 25 map<point, int> m; 26 27 inline int read() 28 { 29 int x=0;char c=getchar(); 30 while(c > '9' || c < '0') c = getchar(); 31 while(c >= '0' && c <= '9') x=x*10+c-'0',c=getchar(); 32 return x; 33 } 34 35 inline void add(int f, int w, int S) 36 { 37 date[++tot] = w, Next[tot] = Head[f], haveflow[tot] = S, Head[f] = tot; 38 date[++tot] = f, Next[tot] = Head[w],/* haveflow[tot] = 0,*/ Head[w] = tot; 39 // printf("%d ---> %d %d ", f, w, S); 40 } 41 42 void pre() 43 { 44 X = read(), Y = read(), n = read(); 45 s = n * 2 + 1, t = s + 1; 46 for(R i=1;i<=n;i++) 47 { 48 p[i].y = read(), p[i].x = read(), power[i] = read();//注意行列是反的！ 49 m[p[i]] = i;//编号 50 } 51 } 52 53 void build()//暴力枚举加边 54 { 55 int x, y; 56 for(R i=1;i<=n;i++)//枚举方块，只连出边 57 { 58 add(i, n + i, power[i]);//拆点连边 59 x = p[i].x, y = p[i].y; 60 if(x % 2)//按奇偶行分类 61 { 62 if(y % 2)//按奇偶列分类（可能为s or t右） 63 {//因为2 = 2 * 1, 6 = 2 * 3 .... 所以有余数就说明是s 64 if(((y + 1) / 2) % 2)//有余数所以是s 65 {//跟旁边的t连上 66 if(m[(point){x, y + 1}]) add(i + n, m[(point){x, y + 1}], inf); 67 } 68 else add(i + n, t, inf);//不然就要连向t了 69 } 70 else//不然就是s左的 or t 71 { 72 if((y / 2) % 2) 73 { 74 if(m[(point){x, y + 1}]) add(i + n, m[(point){x, y + 1}], inf);//如果有余数说明是t 75 if(m[(point){x + 1, y}]) add(i + n, m[(point){x + 1, y}], inf); 76 if(m[(point){x - 1, y}]) add(i + n, m[(point){x - 1, y}], inf); 77 } 78 else//不然属于s周围的 79 { 80 if(m[(point){x, y + 1}]) add(i + n, m[(point){x, y + 1}], inf); 81 if(m[(point){x + 1, y}]) add(i + n, m[(point){x + 1, y}], inf); 82 if(m[(point){x - 1, y}]) add(i + n, m[(point){x - 1, y}], inf); 83 add(s, i, inf);//注意s周围的要连s 84 } 85 } 86 } 87 else //偶行 88 { 89 if(y % 2)//奇列，t or s右 90 { 91 if(((y + 1) / 2) % 2)//如果有余数说明是s右 92 { 93 if(m[(point){x, y - 1}]) add(i + n, m[(point){x, y - 1}], inf); 94 if(m[(point){x + 1, y}]) add(i + n, m[(point){x + 1, y}], inf); 95 if(m[(point){x - 1, y}]) add(i + n, m[(point){x - 1, y}], inf); 96 add(s, i, inf); 97 } 98 else 99 { 100 if(m[(point){x, y - 1}]) add(i + n, m[(point){x, y - 1}], inf);//如果有余数说明是t 101 if(m[(point){x + 1, y}]) add(i + n, m[(point){x + 1, y}], inf); 102 if(m[(point){x - 1, y}]) add(i + n, m[(point){x - 1, y}], inf); 103 } 104 } 105 else//t左 or s 106 { 107 if((y / 2) % 2) add(i + n, t, inf);//如果有余数的话，说明是t左 108 else//不然就是s 109 if(m[(point){x, y - 1}]) add(i + n, m[(point){x, y - 1}], inf); 110 }//注意加了n才是出发点 111 } 112 } 113 } 114 115 void bfs() 116 { 117 int x, now; 118 c[t] = 1, x = t, q[++tail] = t; 119 while(head < tail) 120 { 121 x = q[++head]; 122 for(R i=Head[x]; i; i=Next[i]) 123 { 124 now = date[i]; 125 if(haveflow[i^1] && !c[now]) 126 { 127 ++have[c[now] = c[x] + 1]; 128 q[++tail] = now; 129 } 130 } 131 } 132 memcpy(good, Head, sizeof(Head)); 133 } 134 135 inline void aru() 136 { 137 while(x != s) 138 { 139 haveflow[last[x]] -= addflow; 140 haveflow[last[x] ^ 1] += addflow; 141 x = date[last[x] ^ 1]; 142 } 143 ans += addflow; 144 } 145 146 void isap() 147 { 148 int now; bool done; 149 addflow = inf, x = s; 150 while(c[s] != 200051) 151 { 152 if(x == t) aru(), addflow = inf; 153 done = false; 154 for(R i =good[x]; i ;i =Next[i]) 155 { 156 now = date[i]; 157 if(haveflow[i] && c[now] == c[x] -1) 158 { 159 addflow = min(addflow, haveflow[i]); 160 last[now] = i; 161 good[x] = i; 162 done = true; 163 x = now; 164 break; 165 } 166 } 167 if(!done) 168 { 169 int go = 200050; 170 for(R i=Head[x]; i ;i=Next[i]) 171 { 172 now = date[i]; 173 if(haveflow[i] && c[now]) go = min(go, c[now]); 174 } 175 good[x] = Head[x]; 176 if(!(--have[c[x]])) break; 177 ++have[c[x] = go + 1]; 178 if(x != s) x = date[last[x] ^ 1]; 179 } 180 } 181 printf("%d ", ans); 182 } 183 184 int main() 185 { 186 // freopen("in.in","r",stdin); 187 fread(READ, 1, 7000000, stdin); 188 pre(); 189 build(); 190 bfs(); 191 isap(); 192 // fclose(stdin); 193 return 0; 194 }