锐客网

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

国家集训队2011]happiness(吴确)

IT知识Happiness国家集训

【国家集训队2011]happiness(吴确)】出门莫恨无人随，书中车马多如簇。这篇文章主要讲述国家集训队2011]happiness(吴确)相关的知识，希望能为你提供帮助。
                              1873. [国家集训队2011]happiness(吴确)★★★    输入文件：nt2011_happiness.in    输出文件：nt2011_happiness.out      简单对比
时间限制：1 s    内存限制：512 MB
【试题来源】
2011中国国家集训队命题答辩【问题描述】
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。 【输入格式】
第一行两个正整数n，m。
接下来是六个矩阵
第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。
第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。
第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。
第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。
第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。
第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。 【输出格式】
输出一个整数，表示喜悦值总和的最大值 【样例输入】
1 2
1 1
100 110
1
1000 【样例输出】
1210 【样例说明】
两人都选理，则获得100+110+1000的喜悦值。 【数据规模和约定】
对于10%以内的数据，n,m< =4
对于30%以内的数据，n,m< =8
对于100%以内的数据，n,m< =100 数据保证答案在2^30以内
对于100%的数据，时间限制为0.5s。

　参考了大佬的题解http://blog.sina.com.cn/s/blog_c5566b0f0102v7yo.html首先不用想，这肯定是个最小割……不妨将其解题过程记录下来，以作为一个典型的最小割模型题。   “最小割”求的是一个“最小”的值，而本题需要最大化喜悦值之和，所以很显然，在最小割中被割掉的边应该意味着“放弃该喜悦值”。也就是说，最小割是放弃掉的所有喜悦值。   首先，为了简单起见，我们不妨选取一对相邻点进行研究。不妨设是这样的：
国家集训队2011]happiness(吴确)

文章图片
  其中S是源点，x,y是我们研究的两个点（也就是原问题中的两个学生），T是汇点。为了方便起见，没有画出边。   文中可能会用到一些符号：w(a,b)表示边(a,b)的容量，x选文的喜悦值为W_x文，x,y都选文的额外喜悦值是W_同文，以此类推。

最小割模型常用的一个手段是：每个点都需要在“在S集”和“在T集”两个事件中选一个。我们规定，“在S集”代表学文，“在T集”代表学理。   那么总的快乐值是：W_x文 + W_x理 + W_y文 + W_y理 + W_同文 + W_同理，割值就是从其中扣掉的快乐值。   下面考虑四种情况： ①x在S，y在S：
国家集训队2011]happiness(吴确)

文章图片

红线代表割，左边是S集，右边是T集。 割边容量之和：w(x,T) + w(y,T) “放弃的快乐值”之和：W_x理 + W_y理 + W_同理 （两个人同时学文） 即：w(x,T) + w(y,T) = W_x理 + W_y理 + W_同理   ②x在S，y在T：
国家集训队2011]happiness(吴确)

文章图片

x学文，y学理。 w(x,T) + w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理   类似可以推出后两种情况： ③x在T，y在S：w(S,x) + w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文 + W_同理 ④x在T，y在T：w(S,x) + w(S,y) = W_x文 + W_y文 + W_同文   把四种情况写在一起：   ①SS：w(x,T) + w(y,T) = W_x理 + W_y理 + W_同理   ②ST：w(x,T) + w(S,y) + w(x,y) = W_x理 + W_y文 + W_同文 + W_同理   ③TS：w(S,x) + w(y,T) + w(y,x) = W_x文 + W_y理 + W_同文 + W_同理   ④TT：w(S,x) + w(S,y) = W_x文 + W_y文 + W_同文   然后，怎么设置这些边的容量呢？   我们看①，左边有两项，右边有三项。 秉承“对称”的思想，我们令： w(x,T) = W_x理 + 0.5W_同理， w(y,T) =  W_y理 + 0.5W_同理。 类似地， w(S,x) = W_x文 + 0.5W_同文， w(S,y) = W_y文 + 0.5W_同文。   然后我们检查②和③。以②为例，将w(x,T)和w(S,y)代入并化简：   w(x,y) = 0.5 ( W_同文 + W_同理 )   同样地由③得：   w(y,x) = 0.5 ( W_同文 + W_同理 )   把x,y扩展至整张棋盘： 对于某个人(i,j)，设它对应的顶点是x。 连边(S,x)，容量为：W_x理 + 0.5 ( x和所有邻居的W_同理之和 )  连边(x,T)，容量为：W_x文 + 0.5 ( x和所有邻居的W_同文之和 ) 对于某两个相邻的人x和y（y可能在x的上下左右）， 连边(x,y)，容量为：0.5 ( W_同文 + W_同理 )   用所有的快乐值之和（其实就是输入的那六个矩阵的所有元素之和）减去最小割（即最大流）的值即为答案。这里有一点细节：实数容量的网络流不好求，可以把所有边的容量*2，最后输出答案时/2即可。 打代码的时候不小心把n*m打成了n+m，wa了四次，手残.......
1 #include< cstdio> 2 #include< iostream> 3 #include< cstring> 4 #include< algorithm> 5 using namespace std; 6 #define inf 100000007 7 #define int long long 8 int read() { 9int s=0,f=1; 10char ch=getchar(); 11while(ch> ‘9‘||ch< ‘0‘) { 12if(ch==‘-‘) { 13f=-1; 14} 15ch=getchar(); 16} 17while(ch> =‘0‘& & ch< =‘9‘) { 18s=(s< < 1)+(s< < 3)+(ch^48); 19ch=getchar(); 20} 21return s*f; 22 } 23 int n,m,sum; 24 int wen_sin[101][101],li_sin[101][101],wen_xia[101][101],li_xia[101][101],wen_you[101][101],li_you[101][101]; 25 int dis[102][102],num[101][101],zong,tot,S,T,r[10005]; 26 int sum_li[10002],sum_wen[10002]; 27 struct oo { 28int to,vv,next; 29 } c[1000005]; 30 void add(int x,int y,int z) { 31c[tot].to=y; 32c[tot].vv=z; 33c[tot].next=r[x]; 34r[x]=tot++; 35 } 36 void init() { 37memset(r,-1,sizeof(r)); 38n=read(); 39m=read(); 40T=n*m+1; 41for(int i=1; i< =n; i++) { 42for(int j=1; j< =m; j++) { 43num[i][j]=++zong; 44} 45} 46for(int i=1; i< =n; i++) { 47for(int j=1; j< =m; j++) { 48wen_sin[i][j]=read()*2; 49sum+=wen_sin[i][j]; 50} 51} 52for(int i=1; i< =n; i++) { 53for(int j=1; j< =m; j++) { 54li_sin[i][j]=read()*2; 55sum+=li_sin[i][j]; 56} 57} 58for(int i=1; i< n; i++) { 59for(int j=1; j< =n; j++) { 60wen_xia[i][j]=read()*2; 61sum_wen[num[i][j]]+=wen_xia[i][j]; 62sum_wen[num[i+1][j]]+=wen_xia[i][j]; 63sum+=wen_xia[i][j]; 64} 65} 66for(int i=1; i< n; i++) { 67for(int j=1; j< =m; j++) { 68li_xia[i][j]=read()*2; 69sum_li[num[i][j]]+=li_xia[i][j]; 70sum_li[num[i+1][j]]+=li_xia[i][j]; 71sum+=li_xia[i][j]; 72} 73} 74for(int i=1; i< =n; i++) { 75for(int j=1; j< m; j++) { 76wen_you[i][j]=read()*2; 77sum_wen[num[i][j]]+=wen_you[i][j]; 78sum_wen[num[i][j+1]]+=wen_you[i][j]; 79sum+=wen_you[i][j]; 80} 81} 82for(int i=1; i< =n; i++) { 83for(int j=1; j< m; j++) { 84li_you[i][j]=read()*2; 85sum_li[num[i][j]]+=li_you[i][j]; 86sum_li[num[i][j+1]]+=li_you[i][j]; 87sum+=li_you[i][j]; 88} 89} 90 } 91 // S li T wen 92 void build() { 93for(int i=1; i< =n; i++) { 94for(int j=1; j< =m; j++) { 95int x=li_sin[i][j]+sum_li[num[i][j]]/2; 96add(S,num[i][j],x); 97add(num[i][j],S,0); 98int y=wen_sin[i][j]+sum_wen[num[i][j]]/2; 99add(num[i][j],T,y); 100add(T,num[i][j],0); 101if(i< n) { 102add(num[i][j],num[i+1][j],(li_xia[i][j]+wen_xia[i][j])/2); 103add(num[i+1][j],num[i][j],0); 104add(num[i+1][j],num[i][j],(li_xia[i][j]+wen_xia[i][j])/2); 105add(num[i][j],num[i+1][j],0); 106} 107if(j< m) { 108add(num[i][j],num[i][j+1],(li_you[i][j]+wen_you[i][j])/2); 109add(num[i][j+1],num[i][j],0); 110add(num[i][j+1],num[i][j],(li_you[i][j]+wen_you[i][j])/2); 111add(num[i][j],num[i][j+1],0); 112} 113} 114} 115 } 116 int queue[1000005],head,tail,deep[10005]; 117 bool bfs(int s,int t) { 118memset(deep,0,sizeof(deep)); 119head=tail=0; 120deep[s]=1; 121queue[++tail]=s; 122while(head< tail) { 123int opt=queue[++head]; 124for(int i=r[opt]; ~i; i=c[i].next) { 125if(c[i].vv& & !deep[c[i].to]) { 126deep[c[i].to]=deep[opt]+1; 127queue[++tail]=c[i].to; 128if(c[i].to==t) { 129return 1; 130} 131} 132} 133} 134return 0; 135 } 136 int dfs(int opt,int fw) { 137if(opt==T) { 138return fw; 139} 140int tmp=fw,k; 141for(int i=r[opt]; ~i; i=c[i].next) { 142if(tmp& & c[i].vv& & deep[c[i].to]==deep[opt]+1) { 143k=dfs(c[i].to,min(c[i].vv,tmp)); 144if(!k) { 145deep[c[i].to]=0; 146continue; 147} 148c[i].vv-=k; 149c[i^1].vv+=k; 150tmp-=k; 151} 152} 153return fw-tmp; 154 } 155 int dinic(int s,int t) { 156int ans=0; 157while(bfs(s,t)) { 158ans+=dfs(s,inf); 159} 160return ans; 161 } 162 int Main(){ 163freopen("nt2011_happiness.in","r",stdin); 164freopen("nt2011_happiness.out","w",stdout); 165init(); 166build(); 167int ans=dinic(S,T); 168printf("%d\n",(sum-ans)> > 1); 169return 0; 170 } 171 int hehe=Main(); 172 signed main() { 173; 174 }

 




















    推荐阅读


    上一篇：使用清华大学开源软件镜像AOSP的&ldquo;每月更新初始化包&rdquo;更新指定版本的Android源码

    下一篇：Android中XML文件的序列化生成与解析