HDU 5076 Memory
HDU memory
2023-09-11 14:15:28 时间
Memory
Time Limit: 4000ms
Memory Limit: 262144KB
This problem will be judged on HDU. Original ID: 507664-bit integer IO format: %I64d Java class name: Main
Special Judge
Little Bob’s computer has 2n bytes of memory. For convenience, n-bit integers 0 to 2n - 1 are used to index these bytes.
Now he wants to assign a value to each byte of the memory. In this problem, a byte is composed of m bits. Therefore he can only assign 0 to 2m - 1 (inclusive) to a single byte.
Bob has some preferences on which value to be assigned to each byte. For the byte indexed by i, if it is assigned with value j (0 ≤ j < 2m), the preference score for it is wi,j.
In addition, each byte has a threshold value. For two different bytes indexed by a and b, if the following two conditions are satisfied, there will be an additional score (ua xor ub):
1.a and b only have one bit of difference in their binary forms;
2.The assigned value of byte a is not less than its threshold value, or the assigned value of byte b is not less than its threshold value.
The total score of an assignment solution is the sum of the preference scores of all bytes plus the sum of all additional scores.
Bob wants to find an assignment solution with the maximum total score. If there are multiple solutions, you can output any of them.
Now he wants to assign a value to each byte of the memory. In this problem, a byte is composed of m bits. Therefore he can only assign 0 to 2m - 1 (inclusive) to a single byte.
Bob has some preferences on which value to be assigned to each byte. For the byte indexed by i, if it is assigned with value j (0 ≤ j < 2m), the preference score for it is wi,j.
In addition, each byte has a threshold value. For two different bytes indexed by a and b, if the following two conditions are satisfied, there will be an additional score (ua xor ub):
1.a and b only have one bit of difference in their binary forms;
2.The assigned value of byte a is not less than its threshold value, or the assigned value of byte b is not less than its threshold value.
The total score of an assignment solution is the sum of the preference scores of all bytes plus the sum of all additional scores.
Bob wants to find an assignment solution with the maximum total score. If there are multiple solutions, you can output any of them.
Input
The first line contains an integer T (T ≤ 3), denoting the number of the test cases.
For each test case, the first line contains two integers, n and m(1 ≤ n, m ≤ 8), as mentioned above. The second line contains 2n integers, and the i-th integer is the threshold value for byte i. The threshold values are between 0 and 2m - 1, inclusively. The third line contains 2n integers, and the i-th integer is ui(0 ≤ ui < 1024). The next 2n lines give all preference scores. Each line contains 2m integers, and the j-th integer of the i-th line is wi,j (-1024 ≤ wi,j < 1024).
For each test case, the first line contains two integers, n and m(1 ≤ n, m ≤ 8), as mentioned above. The second line contains 2n integers, and the i-th integer is the threshold value for byte i. The threshold values are between 0 and 2m - 1, inclusively. The third line contains 2n integers, and the i-th integer is ui(0 ≤ ui < 1024). The next 2n lines give all preference scores. Each line contains 2m integers, and the j-th integer of the i-th line is wi,j (-1024 ≤ wi,j < 1024).
Output
For each test case, output one line consisting of 2n integers between 0 and 2m - 1, and the i-th integer is the value assigned to byte i in the assignment solution with the maximum total score.
Sample Input
1 3 2 0 1 1 3 3 0 3 3 4 8 8 7 0 9 2 9 -9 -8 3 2 -9 -6 4 1 -6 -8 -5 3 3 -1 -4 -1 -6 -5 1 10 -10 7 3 -10 -3 -10 -4 -5 -2 -1 -9 1
Sample Output
2 2 3 0 3 1 0 3
Source
解题:网络流
- 对于每个位置拆成两个点,左边源右边汇。
- 如果这个位置的index有奇数个1,左边连小于的w,右边连大于等于的w。
- 如果这个位置的index有偶数个1,左边连大于等于的w,右边连小于的w。
- 每个位置左边往右边连一条inf的弧,代表这两个点不能都不割。
- 对于每组a,b,从奇数的小于连向偶数的小于,ua xor ub。
- 为了避免负流量可以把所有w加一个1024,不影响最后结果。
- 总之建出来是个二分图。
- 最后建完就可以发现其实可以不用拆点,但拆了还是更好理解一些。
最后所有的收益加起来减掉最小割就是最大收益。
据说上面是昂神分析的
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = ~0U>>2; 4 const int maxn = 1024; 5 struct arc { 6 int to,flow,next; 7 arc(int x = 0,int y = 0,int z = -1) { 8 to = x; 9 flow = y; 10 next = z; 11 } 12 } e[maxn*maxn]; 13 int head[maxn],d[maxn],cur[maxn],tot,S,T; 14 void add(int u,int v,int flow) { 15 e[tot] = arc(v,flow,head[u]); 16 head[u] = tot++; 17 e[tot] = arc(u,0,head[v]); 18 head[v] = tot++; 19 } 20 bool bfs() { 21 queue<int>q; 22 memset(d,-1,sizeof d); 23 d[S] = 1; 24 q.push(S); 25 while(!q.empty()) { 26 int u = q.front(); 27 q.pop(); 28 for(int i = head[u]; ~i; i = e[i].next) { 29 if(e[i].flow && d[e[i].to] == -1) { 30 d[e[i].to] = d[u] + 1; 31 q.push(e[i].to); 32 } 33 } 34 } 35 return d[T] > -1; 36 } 37 int dfs(int u,int low) { 38 if(u == T) return low; 39 int a,tmp = 0; 40 for(int &i = cur[u]; ~i; i = e[i].next) { 41 if(e[i].flow &&d[e[i].to] == d[u]+1&&(a=dfs(e[i].to,min(low,e[i].flow)))) { 42 e[i].flow -= a; 43 e[i^1].flow += a; 44 low -= a; 45 tmp += a; 46 if(!low) break; 47 } 48 } 49 if(!tmp) d[u] = -1; 50 return tmp; 51 } 52 int dinic(int ret = 0) { 53 while(bfs()) { 54 memcpy(cur,head,sizeof cur); 55 ret += dfs(S,INF); 56 } 57 return ret; 58 } 59 int U[maxn],Th[maxn],B[maxn],L[maxn],ans[maxn],Bid[maxn],Lid[maxn]; 60 int main() { 61 int kase,n,m; 62 scanf("%d",&kase); 63 while(kase--) { 64 scanf("%d%d",&n,&m); 65 n = (1<<n); 66 m = (1<<m); 67 for(int i = tot = 0; i < n; ++i) 68 scanf("%d",Th + i); 69 for(int i = 0; i < n; ++i) 70 scanf("%d",U + i); 71 for(int i = 0; i < n; ++i) { 72 B[i] = L[i] = -1; 73 for(int j = 0,w; j < m; ++j) { 74 scanf("%d",&w); 75 w += 1024; 76 if(j >= Th[i] && B[i] < w) { 77 B[i] = w; 78 Bid[i] = j; 79 } else if(L[i] < w) { 80 L[i] = w; 81 Lid[i] = j; 82 } 83 } 84 } 85 S = n<<1; 86 T = S + 1; 87 memset(head,-1,sizeof head); 88 for(int i = 0; i < n; ++i) { 89 int k = __builtin_popcount(i); 90 add(i,i + n,INF); 91 if(k&1) { 92 add(S,i,L[i]); 93 add(i + n,T,B[i]); 94 } else { 95 add(S,i,B[i]); 96 add(i + n,T,L[i]); 97 } 98 for(int j = i + 1; j < n; ++j) { 99 if(__builtin_popcount(i^j) == 1) { 100 if(k&1) add(i,j + n,U[i]^U[j]); 101 else add(j,i + n,U[i]^U[j]); 102 } 103 } 104 } 105 dinic(); 106 for(int i = 0; i < n; ++i) { 107 if(i) putchar(' '); 108 if(__builtin_popcount(i)&1) 109 printf("%d",(~d[i])?Lid[i]:Bid[i]); 110 else printf("%d",(~d[i])?Bid[i]:Lid[i]); 111 } 112 putchar('\n'); 113 } 114 return 0; 115 }
相关文章
- hdu 5045 费用流
- HDU 5389 Zero Escape(DP + 滚动数组)
- HDU 1199 && ZOJ 2301 线段树离散化
- HDU 5402 Travelling Salesman Problem (模拟 有规律)(左上角到右下角路径权值最大,输出路径)
- hdu 1856 More is better(并查集)
- HDU 5421 Victor and String
- HDU 3749 Financial Crisis
- HDU 1693 Eat the Trees (插头DP)
- poj3211Washing Clothes(字符串处理+01背包) hdu1171Big Event in HDU(01背包)
- HDU 2845 Beans(dp)
- hdu 1068 Girls and Boys (最大独立集)