[国家集训队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

讲的超级详细，很好理解。

建图好恶心

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

代码

作者：乌鸦坐飞机
出处：http://www.cnblogs.com/whistle13326/
新的风暴已经出现怎么能够停止不前穿越时空竭尽全力我会来到你身边微笑面对危险梦想成真不会遥远鼓起勇气坚定向前奇迹一定会出现