[BZOJ 3171][TJOI2013]循环格
转载请注明出处:http://danihao123.is-programmer.com/
流量平衡入门中……
我竟然想民白了……
这个题就是要求每个点在且仅在一个环中,这样每个点的入、出度都是1。出度肯定是1,接下来我们想想怎么保证入度为1。
我们建两排点(也可以说是拆点?),一排表示流出,一排表示接受。然后流出点向相邻的接收点连边,费用的话考虑是否和原来这一格的方向不一样就行了。
这个不需要判断是否满流啥的……因为一定有解(比如说每个行构成一个环啥的)。
代码:
/************************************************************** Problem: 3171 User: danihao123 Language: C++ Result: Accepted Time:28 ms Memory:13844 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <utility> #include <queue> const int maxn = 20; typedef long long ll; char S[maxn][maxn]; int tot = 0; int num[maxn][maxn][2]; int R, C; char D[4] = {'L', 'R', 'U', 'D'}; int tow(int i, int j, char dir, int flag) { int dx = 0, dy = 0; if(dir == 'L') { dx = -1; } else if(dir == 'R') { dx = 1; } else if(dir == 'U') { dy = -1; } else if(dir == 'D') { dy = 1; } int nx = (i + dy + R) % R; int ny = (j + dx + C) % C; return num[nx][ny][flag]; } const int maxno = 100005; const int maxe = 400005; int first[maxno]; int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe]; ll cost[maxe]; int gcnt = 0; void add_edge(int u, int v, int f, ll c) { gcnt ++; next[gcnt] = first[u]; first[u] = gcnt; from[gcnt] = u; to[gcnt] = v; cap[gcnt] = f; flow[gcnt] = 0; cost[gcnt] = c; } int rev(int i) { return ((i - 1) ^ 1) + 1; } void ins_edge(int u, int v, int f, ll c = 0LL) { #ifdef LOCAL printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c); #endif add_edge(u, v, f, c); add_edge(v, u, 0, -c); } const ll LINF = 0x7f7f7f7f7f7f7f7fLL; bool spfa(int s, int t, int &f, ll &c) { static ll d[maxno]; static bool inq[maxno]; static int a[maxno], p[maxno]; std::fill(d, d + tot + 1, LINF); std::fill(inq, inq + tot + 1, false); std::fill(a, a + tot + 1, 0); std::fill(p, p + tot + 1, 0); d[s] = 0; std::queue<int> Q; Q.push(s); inq[s] = true; a[s] = 0x7fffffff; while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for(int i = first[u]; i; i = next[i]) { if(cap[i] > flow[i]) { int v = to[i]; if(d[v] > d[u] + cost[i]) { d[v] = d[u] + cost[i]; a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i; if(!inq[v]) { Q.push(v); inq[v] = true; } } } } } if(a[t] == 0) return false; f += a[t]; c += (ll(a[t])) * d[t]; for(int e = p[t]; e; e = p[from[e]]) { flow[e] += a[t]; flow[rev(e)] -= a[t]; } return true; } void mcmf(int s, int t, int &f, ll &c) { while(spfa(s, t, f, c)); } int main() { tot = 1; int s = 0, t = 1; scanf("%d%d", &R, &C); for(int i = 0; i < R; i ++) { scanf("%s", S[i]); for(int j = 0; j < C; j ++) { num[i][j][0] = ++ tot; num[i][j][1] = ++ tot; } } for(int i = 0; i < R; i ++) { for(int j = 0; j < C; j ++) { ins_edge(s, num[i][j][0], 1); ins_edge(num[i][j][1], t, 1); for(int it = 0; it < 4; it ++) { int u = num[i][j][0]; int v = tow(i, j, D[it], 1); ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL); } } } int f = 0; ll c = 0; mcmf(s, t, f, c); printf("%lld\n", c); return 0; }
Sep 03, 2022 07:02:16 PM
Haryana Board Model Paper 2023 Class 8 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Haryana Board 8th Class Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.