锐客网

  1. 首页 > 睿知 > it技术 > >

[BZOJ2127]happiness

IT知识bzojHappiness

天下之事常成于困约，而败于奢靡。这篇文章主要讲述[BZOJ2127]happiness相关的知识，希望能为你提供帮助。
【[BZOJ2127]happiness】 题目大意：
有一个$n\times m$的阵列，每个位置上有一元素，现在要将这些元素分为$A$部和$B$部，
对于每个元素$i$，如果它被分到了$A$部，就会得到相应的收益$a_i$；如果它被分到了$B$部，也会得到相应的收益$b_i$。
对于每两个相邻的元素$i$和$j$，如果被同时分在$A$部或$B$部，也会有相应的额外收益$c_{ij}$，$d_{ij}$。
思路：
考虑最小割将所有元素分$S$集和$T$集，$S$集表示$A$部，$T$集表示$B$部，
对于每个元素$i$，连一条从$S$到$i$的容量为$a_i$的边，再连一条从$i$到$T$的容量为$b_i$的边，若其中一条被割去，则说明该元素不在那个集合，易证在最小割中，这两条边有且仅有一条会被割去。
对于每两个相邻的元素$i$和$j$，设$flow(x,y)$表示下面新加入的边的容量，分以下三种情况考虑：
1.两个元素都被分在了$A$部，那么两人加入$B$部得到的收益应当被加入到割集中，除了割去原有的边以外，还需要割去两个元素共同加入$B$集的收益，因此只要增加满足$flow(i,T)+flow(j,T)=c_{ij}$的边即可。
2.两个元素都被分在了$B$部，同上得$flow(S,i)+flow(S,j)=d_{ij}$。
3.两个元素属于不同集合，假设$i$属于$A$部，$j$属于$B$部，那么我们可以发现，两者都属于$A$部或$B$部的额外收益都得被割掉，因此我们需要保证新加入的边$flow(S,i)+flow(i,j)+flow(j,T)=c_{ij}+d_{ij}$。同理，若$j$属$A$部，$i$属$B$部，则需要保证$flow(S,j)+flow(j,i)+flow(i,T)=c_{ij}+d_{ij}$。
然后跑一遍最小割，就得到了不能被满足的那些收益，答案即为总收益-最小割。
细节：
1.因为建图时的规则比较多，可能会导致两点见被连了多条边，因此可以将两点之间的边合并成一条。
2.合并的时候不能直接用一个$V\times V$的数组存（$V$为原图中点数），这样会MLE，用map或者hash_map的也不好。
3.因为除了$S$和$T$外，其它的元素之间只有相邻的四个点才可能有边，因此可以考虑只记录相邻元素的边的情况，这样内存比较小，时间也会比较快。
4.lych有一个神奇的加边方法，就是先用数组把输入数据存起来，然后加边的时候统一计算即可，代码只有57行。

1 #include< queue> 2 #include< cstdio> 3 #include< cctype> 4 #include< vector> 5 #include< cstring> 6 inline int getint() { 7char ch; 8while(!isdigit(ch=getchar())); 9int x=ch^‘0‘; 10while(isdigit(ch=getchar())) x=(((x< < 2)+x)< < 1)+(ch^‘0‘); 11return x; 12 } 13 const int inf=0x7fffffff; 14 int s,t; 15 const int V=10002,E=80000; 16 int ss[V]={0},left[V]={0},right[V]={0},up[V]={0},down[V]={0},tt[V]={0}; 17 struct Edge { 18int to,remain; 19 }; 20 Edge e[E]; 21 int sz=0; 22 std::vector< int> g[V]; 23 inline void add_edge(const int u,const int v,const int w) { 24e[sz]=(Edge){v,w}; 25g[u].push_back(sz); 26sz++; 27 } 28 int lev[V]; 29 inline void bfs() { 30std::fill(& lev[1],& lev[t+1],-1); 31lev[s]=0; 32std::queue< int> q; 33q.push(s); 34while(!q.empty()) { 35int x=q.front(); 36q.pop(); 37for(unsigned i=0; i< g[x].size(); i++) { 38Edge & y=e[g[x][i]]; 39if(y.remain& & !~lev[y.to]) { 40lev[y.to]=lev[x]+1; 41q.push(y.to); 42} 43} 44} 45 } 46 unsigned cur[V]; 47 int dfs(const int x,const int flow) { 48if(x==t) return flow; 49for(unsigned & i=cur[x]; i< g[x].size(); i++) { 50Edge & y=e[g[x][i]]; 51if(y.remain& & lev[x]< lev[y.to]) { 52if(int f=dfs(y.to,std::min(flow,y.remain))) { 53e[g[x][i]].remain-=f; 54e[g[x][i]^1].remain+=f; 55return f; 56} 57} 58} 59return 0; 60 } 61 inline int Dinic() { 62int maxflow=0; 63for(; ; ) { 64bfs(); 65if(!~lev[t]) break; 66memset(cur,0,sizeof cur); 67while(int flow=dfs(s,inf)) { 68maxflow+=flow; 69} 70} 71return maxflow; 72 } 73 int main() { 74int n=getint(),m=getint(); 75s=0,t=n*m+1; 76int sum=0; 77for(int i=1; i< =n; i++) { 78for(int j=1; j< =m; j++) { 79int w=getint()< < 1; 80sum+=w; 81ss[(i-1)*m+j]+=w; 82} 83} 84for(int i=1; i< =n; i++) { 85for(int j=1; j< =m; j++) { 86int w=getint()< < 1; 87sum+=w; 88tt[(i-1)*m+j]+=w; 89} 90} 91for(int i=1; i< n; i++) { 92for(int j=1; j< =m; j++) { 93int w=getint(); 94sum+=w< < 1; 95down[(i-1)*m+j]+=w; 96up[i*m+j]+=w; 97ss[(i-1)*m+j]+=w; 98ss[i*m+j]+=w; 99} 100} 101for(int i=1; i< n; i++) { 102for(int j=1; j< =m; j++) { 103int w=getint(); 104sum+=w< < 1; 105down[(i-1)*m+j]+=w; 106up[i*m+j]+=w; 107tt[(i-1)*m+j]+=w; 108tt[i*m+j]+=w; 109} 110} 111for(int i=1; i< =n; i++) { 112for(int j=1; j< m; j++) { 113int w=getint(); 114sum+=w< < 1; 115right[(i-1)*m+j]+=w; 116left[(i-1)*m+j+1]+=w; 117ss[(i-1)*m+j]+=w; 118ss[(i-1)*m+j+1]+=w; 119} 120} 121for(int i=1; i< =n; i++) { 122for(int j=1; j< m; j++) { 123int w=getint(); 124sum+=w< < 1; 125right[(i-1)*m+j]+=w; 126left[(i-1)*m+j+1]+=w; 127tt[(i-1)*m+j]+=w; 128tt[(i-1)*m+j+1]+=w; 129} 130} 131for(int i=1; i< =n; i++) { 132for(int j=1; j< =m; j++) { 133add_edge(s,(i-1)*m+j,ss[(i-1)*m+j]); 134add_edge((i-1)*m+j,s,0); 135} 136} 137for(int i=1; i< n; i++) { 138for(int j=1; j< m; j++) { 139add_edge((i-1)*m+j,i*m+j,down[(i-1)*m+j]); 140add_edge(i*m+j,(i-1)*m+j,up[i*m+j]); 141add_edge((i-1)*m+j,(i-1)*m+j+1,right[(i-1)*m+j]); 142add_edge((i-1)*m+j+1,(i-1)*m+j,left[(i-1)*m+j+1]); 143} 144} 145for(int i=1; i< n; i++) { 146add_edge(i*m,(i+1)*m,down[i*m]); 147add_edge((i+1)*m,i*m,up[(i+1)*m]); 148} 149for(int j=1; j< m; j++) { 150add_edge((n-1)*m+j,(n-1)*m+j+1,right[(n-1)*m+j]); 151add_edge((n-1)*m+j+1,(n-1)*m+j,left[(n-1)*m+j+1]); 152} 153for(int i=1; i< =n; i++) { 154for(int j=1; j< =m; j++) { 155add_edge((i-1)*m+j,t,tt[(i-1)*m+j]); 156add_edge(t,(i-1)*m+j,0); 157} 158} 159printf("%d\n",(sum-Dinic())> > 1); 160return 0; 161 }

 

    推荐阅读


    上一篇：Tomcat 访问manager app报403 解决方案（虚拟机可以正常使用，外面访问报错）

    下一篇：MPchartAndroid-柱状图