BZOJ_3894_文理分科&&BZOJ_2127_happiness_最小割 _最小割

犀渠玉剑良家子，白马金羁侠少年。这篇文章主要讲述BZOJ_3894_文理分科& & BZOJ_2127_happiness_最小割相关的知识，希望能为你提供帮助。
BZOJ_3894_文理分科_最小割
Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到： 1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。 2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。 3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same_science[i]j[]的满意值。小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。Input第一行为两个正整数：n，m 接下来n术m个整数，表示art[i][j]；接下来n术m个整数．表示science[i][j]；接下来n术m个整数，表示same_art[i][j]；Output输出为一个整数，表示最大的满意值之和Sample Input 3 4
13 2 4 13
7 13 8 12
18 17 0 5

8 13 15 4
11 3 8 11
11 18 6 5

12 3 4
42 3 2
31 0 4

32 3 2
02 2 1
02 4 4 Sample Output 152转化为“ 不选则割” 的最小割模型。每个人要么学文要么学理，故S-> x(a[x])，x-> T(s[i])。对于所有的组合，新建两个结点。 S-> p1(sa[]),p1-> x(inf),x-> p2(inf),p2-> T(ss[]) 然后总权值减最小割为答案。代码：

#include < stdio.h> #include < string.h> #include < algorithm> using namespace std; #define N 30050 #define M 500050 #define S (n*m+1) #define T (n*m+2) #define p(i,j) ((i-1)*m+j) #define inf 100000000 int head[N],to[M< < 1],nxt[M< < 1],cnt=1,n,m,dep[N],Q[N],l,r,flow[M< < 1],sum,a[105][105],b[105][105]; int tx[]={0,1,-1,0}; int ty[]={1,0,0,-1}; inline void add(int u,int v,int f) { to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; } bool bfs() { memset(dep,0,sizeof(dep)); int i; l=r=0; Q[r++]=S; dep[S]=1; while(l< r) { int x=Q[l++]; for(i=head[x]; i; i=nxt[i]) { if(!dep[to[i]]& & flow[i]) { dep[to[i]]=dep[x]+1; if(to[i]==T) return 1; Q[r++]=to[i]; } } } return 0; } int dfs(int x,int mf) { // puts("fgvfiugv"); if(x==T) return mf; int i,nf=0; for(i=head[x]; i; i=nxt[i]) { if(dep[to[i]]==dep[x]+1& & flow[i]) { int tmp=dfs(to[i],min(mf-nf,flow[i])); //if(!tmp) dep[to[i]]=0; nf+=tmp; flow[i]-=tmp; flow[i^1]+=tmp; if(nf==mf) break; } } return nf; } void dinic() { int f; while(bfs()) while(f=dfs(S,inf)) sum-=f; printf("%d\n",sum); } int main() { scanf("%d%d",& n,& m); int i,j,x,k; for(i=1; i< =n; i++) { for(j=1; j< =m; j++) { scanf("%d",& x); sum+=x; add(S,p(i,j),x); } } for(i=1; i< =n; i++) { for(j=1; j< =m; j++) { scanf("%d",& x); sum+=x; add(p(i,j),T,x); } } for(i=1; i< =n; i++) { for(j=1; j< =m; j++) { scanf("%d",& a[i][j]); sum+=a[i][j]; } } for(i=1; i< =n; i++) { for(j=1; j< =m; j++) { scanf("%d",& b[i][j]); sum+=b[i][j]; } } int tot=n*m+2; for(i=1; i< =n; i++) { for(j=1; j< =m; j++) { tot+=2; add(S,tot-1,a[i][j]); add(tot,T,b[i][j]); add(tot-1,p(i,j),inf); add(p(i,j),tot,inf); for(k=0; k< 4; k++) { int di=i+tx[k],dj=j+ty[k]; if(di> =1& & di< =n& & dj> =1& & dj< =m) { add(tot-1,p(di,dj),inf); add(p(di,dj),tot,inf); } } } } dinic(); } /* 3 4 13 2 4 13 7 13 8 12 18 17 0 58 13 15 4 11 3 8 11 11 18 6 51 2 3 4 4 2 3 2 3 1 0 43 2 3 2 0 2 2 1 0 2 4 4 */

【BZOJ_3894_文理分科& & BZOJ_2127_happiness_最小割】