首页 > 代码库 > HDU 5076 Memory
HDU 5076 Memory
昂神的解题报告:http://sd-invol.github.io/2014/10/22/Anshan-2014-G/
我来对他的话进行翻译就好了…
之所以看出最小割 是因为每个位置有两种方案 这样形成二分图后 我们要进行决策 最小割也就变成了进行决策所要丢掉的最小价值
之所以根据每个位置的二进制表示中1的个数来决定该位置两种决策放在左边还是右边 是为了避免二分图中同一个集合里的两个点连边
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> #include<bitset> using namespace std; #define N 300 #define inf 50000000 int T, S, n, m, tot, cas, ans; int head[N * 2], f[N], g[N], Less[N], Lid[N], More[N], Mid[N], dis[N * 2], qu[N * 2]; struct edge { int v, w, next; } ed[N * N * 100]; int cut(int x) { int i; for (i = 0; x; x -= (x & (-x)), i++) ; return i; } void add(int u, int v, int w) { ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; ed[tot].v = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot++; } bool bfs() { int l, r, u, v, i; memset(dis, -1, sizeof(dis)); dis[S] = 0; qu[0] = S; l = 0; r = 1; while (l < r) { u = qu[l++]; for (i = head[u]; ~i; i = ed[i].next) { v = ed[i].v; if (dis[v] < 0 && ed[i].w > 0) { dis[v] = dis[u] + 1; if (v == T) return true; qu[r++] = v; } } } return false; } int dfs(int u, int nowflow) { if (u == T) return nowflow; int i, v, tmp, res = 0; for (i = head[u]; ~i; i = ed[i].next) { v = ed[i].v; if (dis[v] == dis[u] + 1 && ed[i].w > 0) { tmp = dfs(v, min(nowflow, ed[i].w)); nowflow -= tmp; ed[i].w -= tmp; ed[i ^ 1].w += tmp; res += tmp; if (!nowflow) break; } } if (!nowflow) dis[u] = -1; return res; } int main() { scanf("%d", &cas); while (cas--) { scanf("%d%d", &n, &m); n = 1 << n; m = 1 << m; tot = 0; memset(head, -1, sizeof(head)); ans = 0; memset(Less, -1, sizeof(Less)); memset(More, -1, sizeof(More)); S = 0; T = n * 2 + 1; for (int i = 0; i < n; i++) scanf("%d", &f[i]); for (int i = 0; i < n; i++) scanf("%d", &g[i]); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int k; scanf("%d", &k); k += 1024; if (j < f[i]) { if (Less[i] < k) { Less[i] = k; Lid[i] = j; } } else { if (More[i] < k) { More[i] = k; Mid[i] = j; } } } } for (int i = 0; i < n; i++) { int aa = cut(i); if (aa & 1) { add(S, i + 1, Less[i]); add(i + 1 + n, T, More[i]); } else { add(S, i + 1, More[i]); add(i + 1 + n, T, Less[i]); } add(i + 1, i + 1 + n, inf); for (int j = i + 1; j < n; j++) { if (cut(i ^ j) == 1) { if (aa & 1) add(i + 1, j + 1 + n, g[i] ^ g[j]); else add(j + 1, i + 1 + n, g[i] ^ g[j]); } } } while (bfs()) ans += dfs(S, inf); for (int i = 0; i < n; i++) { if (i) printf(" "); int aa = cut(i); if (aa & 1) { if (dis[i + 1] != -1) printf("%d", Lid[i]); else printf("%d", Mid[i]); } else { if (dis[i + 1] != -1) printf("%d", Mid[i]); else printf("%d", Lid[i]); } } printf("\n"); } return 0; }
HDU 5076 Memory
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。