锐客网

  1. 首页 > 生活百科 > it技术 > >

[国家集训队2011]happiness(吴确) (最小割)

IT知识Happiness最小割集训

【[国家集训队2011]happiness(吴确) (最小割)】大鹏一日同风起，扶摇直上九万里。这篇文章主要讲述[国家集训队2011]happiness(吴确) (最小割)相关的知识，希望能为你提供帮助。
2017-08-09  19:03:49
【试题来源】
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(吴确) (最小割)

文章图片
[国家集训队2011]happiness(吴确) (最小割)

文章图片
1 #include< queue> 2 #include< cstdio> 3 #include< iostream> 4 #define MAXN 200010 5 6 using namespace std; 7 8 const int INF=0x7fffffff; 9 10 struct node { 11int to; 12int next; 13int val; 14 }; 15 node e[MAXN]; 16 17 int head[MAXN],cur[MAXN],tot=1; 18 19 int depth[MAXN],ans,map[2][110][110],src,decc,p,sum; 20 21 int n,m; 22 23 queue< int> q; 24 25 inline void read(int& x) { 26int f=1; x=0; char c=getchar(); 27while(c> ‘9‘||c< ‘0‘) {if(c==‘-‘) f=-1; c=getchar(); } 28while(c> =‘0‘& & c< =‘9‘) {x=(x< < 1)+(x< < 3)+c-48; c=getchar(); } 29x=x*f; 30 } 31 32 inline int cal(int i,int j) { 33return (i-1)*m+j; 34 } 35 36 inline void add(int x,int y,int z) { 37e[++tot].to=y; 38e[tot].val=z; 39e[tot].next=head[x]; 40head[x]=tot; 41 } 42 43 inline void add_edge(int x,int y,int z,int f) { 44if(!f) { 45add(x,y,z); 46add(y,x,0); 47} 48else { 49add(x,y,z); 50add(y,x,z); 51} 52 } 53 54 bool bfs() { 55for(int i=0; i< =decc; i++) cur[i]=head[i],depth[i]=-1; 56while(!q.empty()) q.pop(); 57q.push(src); 58depth[src]=0; 59while(!q.empty()) { 60int u=q.front(); 61q.pop(); 62for(int i=head[u]; i!=-1; i=e[i].next) { 63int to=e[i].to; 64if(e[i].val& & depth[to]==-1) { 65q.push(to); 66depth[to]=depth[u]+1; 67if(to==decc) return true; //卧槽 连return都忘了 只剩一个true 找了好长时间的错 68} 69} 70} 71return false; 72 } 73 74 int dfs(int now,int flow) { 75if(now==decc) return flow; 76int rest=0,delat; 77for(int & i=cur[now]; i!=-1; i=e[i].next) { 78int to=e[i].to; 79if(e[i].val& & depth[to]==depth[now]+1) { 80delat=flow-rest; 81delat=dfs(to,min(e[i].val,delat)); 82e[i].val-=delat; 83e[i^1].val+=delat; 84rest+=delat; 85if(rest==flow) return flow; 86} 87} 88if(!rest) depth[now]=-1; 89return rest; 90 } 91 92 inline void dinic() { 93while(bfs()) 94ans+=dfs(src,INF); 95return; 96 } 97 98 inline int hhh(){ 99freopen("nt2011_happiness.in","r",stdin); 100freopen("nt2011_happiness.out","w",stdout); 101read(n); read(m); 102fill(head,head+1+MAXN,-1); 103src=https://www.songbingjia.com/android/0; decc=n*m+1; 104for(int i=1; i< =n; i++) for(int j=1; j< =m; j++) read(map[0][i][j]),sum+=map[0][i][j],map[0][i][j]< < =1; 105for(int i=1; i< =n; i++) for(int j=1; j< =m; j++) read(map[1][i][j]),sum+=map[1][i][j],map[1][i][j]< < =1; 106for(int i=1; i< n; i++) 107for(int j=1; j< =m; j++) { 108read(p); 109map[0][i][j]+=p; map[0][i+1][j]+=p; 110sum+=p; 111add_edge(cal(i,j),cal(i+1,j),p,1); 112} 113for(int i=1; i< n; i++) 114for(int j=1; j< =m; j++) { 115read(p); 116map[1][i][j]+=p; map[1][i+1][j]+=p; 117sum+=p; 118add_edge(cal(i,j),cal(i+1,j),p,1); 119} 120for(int i=1; i< =n; i++) 121for(int j=1; j< m; j++) { 122read(p); 123map[0][i][j]+=p; map[0][i][j+1]+=p; 124sum+=p; 125add_edge(cal(i,j),cal(i,j+1),p,1); 126} 127for(int i=1; i< =n; i++) 128for(int j=1; j< m; j++) { 129read(p); 130map[1][i][j]+=p; map[1][i][j+1]+=p; 131sum+=p; 132add_edge(cal(i,j),cal(i,j+1),p,1); 133} 134for(int i=1; i< =n; i++) 135for(int j=1; j< =m; j++) 136add_edge(src,cal(i,j),map[0][i][j],0), 137add_edge(cal(i,j),decc,map[1][i][j],0); 138 139dinic(); 140printf("%d\n",sum-(ans> > 1)); 141return 0; 142 } 143 144 int sb=hhh(); 145 int main() {; }

代码 

    推荐阅读


    上一篇：Android 如何让EditText不自动获取焦点 （转）

    下一篇：spring boot 读取 application.properties 初始化bean