国家集训队2011happiness _国家

追风赶月莫停留，平芜尽处是春山。这篇文章主要讲述国家集训队2011happiness相关的知识，希望能为你提供帮助。
【试题来源】
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。 solution： (ps：这个题输入是真的new bee) 网络流之最大流的最小割用到了翻转源汇 1.先考虑两个点的情况设cw为同选文 cl为同选理 w为选文happiness l为选理happiness

文章图片

据图当 1.i 文 j 理 2.i，j同文 3.i理 j文 4.i，j同理四种情况时，把边割掉，用总的-割的就是答案
2.当多个点时也一样，S-i / i-T 都是i周围的 (同文+同理)/2 i-j都是 (同文+同理)(i，j的)/2
注意：
1.一开始先乘2，最后再/2，就不用double了
2.数组开10005/105 不要开10001/101
3.连的时候不要重复

文章图片

1 #include< cstdio> 2 #include< cstring> 3 #include< iostream> 4 //#define dd double 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int N=105; 8 const int INF=(1< < 31)-1; 9 inline int minn(int a,int b){return a< b?a:b; } 10 struct son 11 { 12int v,next,u; 13int w; 14 }; 15 son a1[1000001]; 16 int first[1000001],e; 17 inline void addbian(int u,int v,int w) 18 { 19a1[e].u=u; 20a1[e].v=v; 21a1[e].w=w; 22a1[e].next=first[u]; 23first[u]=e++; 24 } 25 26 int dui[10000001],he,en; 27 inline void clear(){he=1; en=0; } 28 inline void push(int x){dui[++en]=x; } 29 inline int top(){return dui[he]; } 30 inline void pop(){++he; } 31 inline bool empty(){return en> =he?0:1; } 32 33 int n,m,S,T; 34 int sum; 35 int wen[N][N],li[N][N]; 36 int xiawen[N][N],xiali[N][N]; 37 int youwen[N][N],youli[N][N]; 38 39 int ha[N][N]; 40 int wensum[10005],lisum[10005]; 41 42 int dep[10005]; 43 44 int bfs() 45 { 46mem(dep,0); clear(); 47dep[S]=1; push(S); 48while(!empty()) 49{ 50int now=top(); pop(); 51for(int i=first[now]; i!=-1; i=a1[i].next) 52{ 53int temp=a1[i].v; 54if(!a1[i].w||dep[temp])continue; 55dep[temp]=dep[now]+1; 56push(temp); 57if(temp==T)return 1; 58} 59} 60return 0; 61 } 62 63 int dfs(int x,int val) 64 { 65if(x==T)return val; 66int val2=val,k; 67for(int i=first[x]; i!=-1; i=a1[i].next) 68{ 69int temp=a1[i].v; 70if(dep[temp]!=dep[x]+1||!val2||!a1[i].w)continue; 71k=dfs(temp,minn(val2,a1[i].w)); 72if(!k){dep[temp]=0; continue; } 73a1[i].w-=k; a1[i^1].w+=k; val2-=k; 74} 75return val-val2; 76 } 77 78 int Dinic() 79 { 80int ans=0; 81while(bfs()) 82ans+=dfs(S,INF); 83return ans; 84 } 85 86 int main(){ 87//freopen("nt2011_happiness.in","r",stdin); 88//freopen("nt2011_happiness.out","w",stdout); 89//freopen("1.txt","r",stdin); 90mem(first,-1); 91scanf("%d%d",& n,& m); 92S=0; T=n*m+1; 93for(int i=1; i< =n; ++i) 94for(int j=1; j< =m; ++j) 95{ha[i][j]=(i-1)*m+j; } 96 97for(int i=1; i< =n; ++i) 98for(int j=1; j< =m; ++j) 99{scanf("%d",& wen[i][j]); wen[i][j]*=2; sum+=wen[i][j]; } 100for(int i=1; i< =n; ++i) 101for(int j=1; j< =m; ++j) 102{scanf("%d",& li[i][j]); li[i][j]*=2; sum+=li[i][j]; } 103 104for(int i=1; i< n; ++i) 105for(int j=1; j< =m; ++j) 106{scanf("%d",& xiawen[i][j]); xiawen[i][j]*=2; sum+=xiawen[i][j]; } 107for(int i=1; i< n; ++i) 108for(int j=1; j< =m; ++j) 109{scanf("%d",& xiali[i][j]); xiali[i][j]*=2; sum+=xiali[i][j]; } 110 111for(int i=1; i< =n; ++i) 112for(int j=1; j< m; ++j) 113{scanf("%d",& youwen[i][j]); youwen[i][j]*=2; sum+=youwen[i][j]; } 114for(int i=1; i< =n; ++i) 115for(int j=1; j< m; ++j) 116{scanf("%d",& youli[i][j]); youli[i][j]*=2; sum+=youli[i][j]; } 117// 118for(int i=1; i< =n; ++i) 119for(int j=1; j< =m; ++j) 120{ 121wensum[ha[i][j]]=wen[i][j]+((i> 1?xiawen[i-1][j]:0)+(i< n?xiawen[i][j]:0)+(j> 1?youwen[i][j-1]:0)+(j< m?youwen[i][j]:0))/2; 122lisum[ha[i][j]]=li[i][j]+((i> 1?xiali[i-1][j]:0)+(i< n?xiali[i][j]:0)+(j> 1?youli[i][j-1]:0)+(j< m?youli[i][j]:0))/2; 123} 124 125for(int i=1; i< T; ++i) 126{addbian(S,i,wensum[i]); addbian(i,S,0); } 127for(int i=1; i< T; ++i) 128{addbian(i,T,lisum[i]); addbian(T,i,0); } 129 130for(int i=1; i< =n; ++i) 131for(int j=1; j< =m; ++j) 132{ 133/*if(i> 1) 134{ 135addbian(ha[i][j],ha[i-1][j],(xiawen[i-1][j]+xiali[i-1][j])/2); 136addbian(ha[i-1][j],ha[i][j],(xiawen[i-1][j]+xiali[i-1][j])/2); 137}*/ 138if(i< n) 139{ 140addbian(ha[i][j],ha[i+1][j],(xiawen[i][j]+xiali[i][j])/2); 141addbian(ha[i+1][j],ha[i][j],(xiawen[i][j]+xiali[i][j])/2); 142} 143/*if(j> 1) 144{ 145addbian(ha[i][j],ha[i][j-1],(youwen[i][j-1]+youli[i][j-1])/2); 146addbian(ha[i][j-1],ha[i][j],(youwen[i][j-1]+youli[i][j-1])/2); 147}*/ 148if(j< m) 149{ 150addbian(ha[i][j],ha[i][j+1],(youwen[i][j]+youli[i][j])/2); 151addbian(ha[i][j+1],ha[i][j],(youwen[i][j]+youli[i][j])/2); 152} 153} 154 155//printf("sum=%d\\n",sum/2); 156 157printf("%d",(sum-Dinic())/2); 158//while(1); 159return 0; 160 }

code【国家集训队2011happiness】