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想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。
分析： 1.对于这种n选1可以得到一些收益，并且在一些特殊情况下有更多收益的，一般判断为网络流。而处理冲突情况，一般通过添加一条inf边来表示。 这个题目直接正向求不好求，于是我们选择将总收益减去最小代价。 2.那么我们令S为学文，T为学理，对于额外的收入，加入一个新的点。 
3.而具体的来说，对于这个图，x表示一个学生，与S连通表示学文，与T连通表示学理。y表示新加的点，用来计算同时学理的额外收益，与S连通表示不 要额外收益，与T连通表示要额外收益先算出总收益，在用最小割减去即可。 4.于是我们可以列出方程：
解得：
a=A[i]b=0c=B[i]d=WBe=0f=inf同时学文类似，只是方向不同，收益不同。
5.所以，最终的建图就是：
step 1 S向每一个学生连边，容量为学文的收益，每个学生再向T连边，容量为学理的收益。step 2 S向代表相邻5个人都学文收益点连边，容量为同时学文的收益step 3 该点再向对应5个人连边，容量为inf，表示只要有人学理，就必须割掉同时学文的收益step 4 学理类似#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int maxm=1000010;const int maxn=300010;const int INF=1e9;int to[maxm],Next[maxm],Begin[maxn],w[maxm],e;int n,m;int art[110][110],sci[110][110],same_art[110][110],same_sci[110][110];int id[110][110],gap[maxn],d[maxn];int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};int s,t;int sum;void addedge(int x,int y,int z){ to[++e]=y; Next[e]=Begin[x]; Begin[x]=e; w[e]=z;}void add(int x,int y,int z){ addedge(x,y,z);addedge(y,x,0);}int isap(int x,int flow){ if(x==t) return flow; int res=flow; int v; for(int i=Begin[x];i;i=Next[i])if(w[i]>0 && d[x]==d[v=to[i]]+1){ int Min=isap(v,min(res,w[i])); w[i]-=Min;w[i^1]+=Min; res-=Min; if(!res) return flow; } if(!(--gap[d[x]])) d[s]=t; ++gap[++d[x]]; return flow-res;}int cnt;bool pd(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m;}int main(){ scanf("%d%d",&n,&m); e=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=++cnt; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&art[i][j]),sum+=art[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&sci[i][j]),sum+=sci[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&same_art[i][j]),sum+=same_art[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&same_sci[i][j]),sum+=same_sci[i][j]; s=cnt*3+1;t=s+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int tmp=(id[i][j]-1)*3; add(s,tmp+1,art[i][j]); add(tmp+1,t,sci[i][j]); add(s,tmp+2,same_art[i][j]); for(int k=0;k<5;k++){ int tx=i+dx[k],ty=j+dy[k]; if(!pd(tx,ty)) continue; add(tmp+2,3*(id[tx][ty]-1)+1,INF); } add(tmp+3,t,same_sci[i][j]); for(int k=0;k<5;k++){ int tx=i+dx[k],ty=j+dy[k]; if(!pd(tx,ty)) continue; add(3*(id[tx][ty]-1)+1,tmp+3,INF); } } int maxflow=0; for(gap[0]=t;d[s]<t;){ maxflow+=isap(s,INF); } PRintf("%d",sum-maxflow); return 0;}^_^
新闻热点
疑难解答
