T1 Seal

想了好久，也不知道怎么建图，然后心态就崩了，就刷BZOJ去了……

考场上写的随机化和错误贪心都被大爷卡了，T_T，Orz YYH,YZY,GZZ三位AK大佬。

首先，以一个恶魔为中心，形成一个直角的充要条件是，在左右相邻格子中选一个，在上下相邻格子中选一个。

然后发现，对于那些水晶格，同为奇数行的总是不会同时被选，同为偶数行的也不会同时被选（此指被选中流向同一个恶魔格子）。就是说，水晶格可以按照所在行（或者列，随便啦）的奇偶进行黑白染色，每个恶魔总是需要匹配一个黑水晶和一个白水晶。

所以把黑水晶放在左侧，每个和源点之间有容量为1的边；白水晶放在右侧，每个和汇点之间也有容量为1的边。中间是恶魔点，每个恶魔拆成两个点，分别和相邻的黑、白水晶相连，中间是容量为1的边。跑最大流就行了。

  1 #include <cstdio>
  2 
  3 inline int nextChar(void) {
  4     const int siz = 1024;
  5     
  6     static char buf[siz];
  7     static char *hd = buf + siz;
  8     static char *tl = buf + siz;
  9     
 10     if (hd == tl)
 11         fread(hd = buf, 1, siz, stdin);
 12         
 13     return *hd++;
 14 }
 15  
 16 inline int nextInt(void) {
 17     register int ret = 0;
 18     register int neg = false;
 19     register int bit = nextChar();
 20     
 21     for (; bit < 48; bit = nextChar())
 22         if (bit == '-')neg ^= true;
 23         
 24     for (; bit > 47; bit = nextChar())
 25         ret = ret * 10 + bit - 48;
 26         
 27     return neg ? -ret : ret;
 28 }
 29 
 30 int n, m;
 31 
 32 bool g[55][55];
 33 
 34 inline bool next(void)
 35 {
 36     char c = nextChar();
 37     
 38     while (c != '.' && c != 'X')
 39         c = nextChar();
 40         
 41     return c == '.';
 42 }
 43 
 44 const int siz = 500005;
 45 const int inf = 1000000007;
 46 
 47 int tot;
 48 int s, t;
 49 int hd[siz];
 50 int to[siz];
 51 int fl[siz];
 52 int nt[siz];
 53 
 54 inline void add(int u, int v, int f)
 55 {
 56     nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; hd[u] = tot++;
 57     nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; hd[v] = tot++;
 58 }
 59 
 60 int dep[siz];
 61 
 62 inline bool bfs(void)
 63 {
 64     static int que[siz], head, tail;
 65     
 66     for (int i = s; i <= t; ++i)dep[i] = 0;
 67     
 68     dep[que[head = 0] = s] = tail = 1;
 69     
 70     while (head != tail)
 71     {
 72         int u = que[head++], v;
 73         
 74         for (int i = hd[u]; ~i; i = nt[i])
 75             if (!dep[v = to[i]] && fl[i])
 76                 dep[que[tail++] = v] = dep[u] + 1;
 77     }
 78     
 79     return dep[t];
 80 }
 81 
 82 int cur[siz];
 83 
 84 inline int min(int a, int b)
 85 {
 86     return a < b ? a : b;
 87 }
 88 
 89 int dfs(int u, int f)
 90 {
 91     if (u == t || !f)
 92         return f;
 93         
 94     int used = 0, flow, v;
 95     
 96     for (int i = cur[u]; ~i; i = nt[i])
 97         if (dep[v = to[i]] == dep[u] + 1 && fl[i])
 98         {
 99             flow = dfs(v, min(fl[i], f - used));
100             
101             used += flow;
102             fl[i] -= flow;
103             fl[i^1] += flow;
104             
105             if (used == f)
106                 return f;
107             
108             if (fl[i])
109                 cur[u] = i;
110         }
111         
112     if (!used)
113         dep[u] = 0;
114     
115     return used;
116 }
117 
118 inline int maxFlow(void)
119 {
120     int maxFlow = 0, newFlow;
121     
122     while (bfs())
123     {
124         for (int i = s; i <= t; ++i)
125             cur[i] = hd[i];
126             
127         while (newFlow = dfs(s, inf))
128             maxFlow += newFlow;
129     }
130     
131     return maxFlow;
132 }
133 
134 inline int pos(int x, int y)
135 {
136     return m * (x - 1) + y;
137 }
138 
139 const int mv[4][2] = 
140 {
141     {0, +1},
142     {0, -1},
143     {-1, 0},
144     {+1, 0}
145 };
146 
147 signed main(void)
148 {
149     freopen("Seal.in", "r", stdin);
150     freopen("Seal.out", "w", stdout);
151     
152     n = nextInt();
153     m = nextInt();
154     
155     
156     for (int i = 1; i <= n; ++i)
157         for (int j = 1; j <= m; ++j)
158             g[i][j] = next();
159             
160     s = 0, t = n * m * 2 + 1;
161             
162     for (int i = s; i <= t; ++i)
163         hd[i] = -1;
164     
165     for (int i = 1; i <= n; ++i)
166         for (int j = 1; j <= m; ++j)
167             if (g[i][j])
168             {
169                 if ((i + j) & 1)
170                 {
171                     if (i & 1)
172                         add(s, pos(i, j), 1);
173                     else
174                         add(pos(i, j), t, 1);
175                 }
176                 else
177                 {
178                     for (int k = 0; k < 4; ++k)
179                     {
180                         int x = i + mv[k][0];
181                         int y = j + mv[k][1];
182                         
183                         if (x < 1 || x > n)
184                             continue;
185                         if (y < 1 || y > m)
186                             continue;
187                         if (!g[x][y])
188                             continue;
189                             
190                         if (x & 1)
191                             add(pos(x, y), pos(i, j), 1);
192                         else
193                             add(pos(i, j) + n*m, pos(x, y), 1);
194                             
195                         add(pos(i, j), pos(i, j) + n*m, 1);
196                     }
197                 }
198             }
199             
200     printf("%d
", maxFlow());
201             
202     return fclose(stdin), fclose(stdout), 0;
203 }

T2 Repair

依旧不会做，然后听LH大爷讲题解，讲完就怀疑自己智商了……

有点像是可行流问题（本来就是可行流好嘛），只是需要分类讨论一下。

对于一条边，如果一开始流量$F$大于$C$，即$F gt C$，那么有如下情况：

如果最后流量$X$大于$F$，即$X gt F gt C$，那么有$fare=X-F+X-C$，如果设$K=F-C$，有$fare=K+2(X-F)$.

如果最后流量$X$在$F$和$C$之间，即$F gt X gt C$，那么有$fare=F-X+X-C=K$.

如果最后流量$X$小于$C$，即$F gt C gt X$，那么有$fare=F-X=K+C-X$.

不难总结出对于这类边的建新边方式：

先将$K$直接统计到答案之中，然后从$u$向$v$连容量为$INF$的边，费用为$2$，从$v$向$u$连容量为$F-C$的边，费用为$0$，从$v$向$u$连容量为$C$的边，费用为$1$。

对于一条边，如果一开始流量$F$小于$C$，即$F lt C$，那么有如下情况：

如果最后流量$X$大于$C$，即$X gt C gt F$，那么有$fare=X-C+X-F$。

2017 01 05 校内网络流小测

T1 Seal

T2 Repair

T3 Flow