首页 > 代码库 > HDU 1565&1569 方格取数系列（状压DP或者最大流）
HDU 1565&1569 方格取数系列（状压DP或者最大流）
方格取数(2)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6206 Accepted Submission(s): 1975
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。
第一题数据范围较小，题目链接：HDU 1565，范围只有20，直接状压DP就可以水过了，把状态存下来可以优化一下空间，dp[i][j]表示当前第i行为第j个状态时的最大值，则有：
$dp[i][k]=max(dp[i][k], dp[i-1][j]+sta_val(k)] (sta[k]&sta[j]==0)$
第一题代码：
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=21;const int M=17720;int pos[N][N];int dp[N][M];int sta[M],cnt;inline bool check(const int &x,const int &y){ return (x&y)==0;}inline int bittonum(const bitset<N> &t,const int &l,const int &n){ int r=0; for (int i=0; i<n; ++i) if(t[i]) r+=pos[l][i]; return r;}void init(int n){ int R=1<<n; cnt=0; for (int i=0; i<R; ++i) if(check(i,i<<1)) sta[cnt++]=i; CLR(dp,0);}int main(void){ int n,i,j,k,temp; while (~scanf("%d",&n)) { if(!n) { puts("0"); continue; } init(n); for (i=0; i<n; ++i) for (j=0; j<n; ++j) scanf("%d",&pos[i][j]); bitset<N>bit; for (i=0; i<cnt; ++i) dp[0][i]=bittonum(bit=sta[i],0,n); for (i=1; i<n; ++i) { for (j=0; j<cnt; ++j) { for (k=0; k<cnt; ++k) { if(check(sta[j],sta[k])) { temp=dp[i-1][j]+bittonum(bit=sta[k],i,n); if(temp>dp[i][k]) dp[i][k]=temp; } } } } int r=0; for (i=0; i<cnt; ++i) if(dp[n-1][i]>r) r=dp[n-1][i]; printf("%d\n",r); } return 0;}
第二题范围较大$2^{50}$次的状态数预处理存的时候估计就T了，网上查了一下，发现是用最大流过的最近又学了最大流，先套个模版过掉再说……这个写的比较简单，应该是最朴素的最大流Ford-Fulkerson算法的DFS版，比较好理解一直DFS直到找不到可增广的路径。
建图要注意一下把图建成二分图的时候不是简单地吧奇数归一边，偶数归另外一边（DEBUG很久才发现这个低级错误），而是选取开头一个作为黑色，不相邻的作为白色，然后进行黑白染色，怎么判断当前的格子是黑色还是白色呢？看(i+j)的值，具体看下标从0还是1开始，简单点直接选第一个格子作为黑色即可，建图三条规则：假设原点S为0，汇点T为n*m+1。遇到黑色格子则建一条S->id[i][j]的边，流量为val[i][j]，另外向旁边的合法白色格子建一条边,流量为INF，白色则是id[i][j]->T的边，流量也是val[i][j]，既然是最大流显然都要多建一条初始容量为0的反向边。最后求S~T的最大流就是最大点权独立集的权值，用sum减去这个数就是答案了，具体定理和证明可以百度
代码：
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define CLR(arr,val) memset(arr,val,sizeof(arr))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=55;const int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};struct edge{ int to; int nxt; int cap;};int val[N][N],id[N][N];edge E[N*N*12];int head[N*N],tot;bitset<N*N>vis;inline void bid_add(int s,int t,int c){ E[tot].cap=c; E[tot].to=t; E[tot].nxt=head[s]; head[s]=tot++; E[tot].cap=0; E[tot].to=s; E[tot].nxt=head[t]; head[t]=tot++;}void init(){ CLR(head,-1); tot=0;}int dfs(int s,int t,int f){ if(s==t) return f; vis[s]=1; for (int i=head[s]; ~i; i=E[i].nxt) { int v=E[i].to; if(!vis[v]&&E[i].cap>0) { int d=dfs(v,t,min<int>(f,E[i].cap)); if(d>0) { E[i].cap-=d; E[i^1].cap+=d; return d; } } } return 0;}int max_flow(int s,int t){ int r=0; while (true) { vis.reset(); int f=dfs(s,t,INF); if(!f) break; r+=f; } return r;}int main(void){ int n,m,i,j,k; while (~scanf("%d%d",&n,&m)) { init(); int sum=0; for (i=0; i<n; ++i) { for (j=0; j<m; ++j) { scanf("%d",&val[i][j]); sum+=val[i][j]; id[i][j]=i*m+j+1; } } int S=0,T=n*m+1; for (i=0; i<n; ++i) { for (j=0; j<m; ++j) { if((i+j)&1) bid_add(id[i][j],T,val[i][j]); else { bid_add(S,id[i][j],val[i][j]); for (k=0; k<4; ++k) { int ti=i+dir[k][0]; int tj=j+dir[k][1]; if(ti>=0&&ti<n&&tj>=0&&tj<m) bid_add(id[i][j],id[ti][tj],INF); } } } } printf("%d\n",sum-max_flow(S,T)); } return 0;}HDU 1565&1569 方格取数系列（状压DP或者最大流）