题目背景
班级聚会的时候，班主任为了方便管理，规定吃饭的时候同一个寝室的同学必须坐在一起;但是吃完饭后，到了娱乐时间，喜欢不同游戏的同学会聚到一起;在这个过程中就涉及到了座位分配的问题。
题目描述
有 n 张圆桌排成一排（从左到右依次编号为 0 到 n−1 ），每张桌子有 m 个座位（按照逆时针依次编号为 0到 m−1 ），在吃饭时每个座位上都有一个人；在吃完饭后的时候，每个人都需要选择一个新的座位（新座位可能和原来的座位是同一个），具体来说，第 i 桌第 j 个人的新座位只能在第 Li,j 桌到第 Ri,j 桌中选，可以是这些桌中的任何一个座位。确定好新座位之后，大家开始移动，移动的体力消耗按照如下规则计算：
移动座位过程分为两步：
- 从起始桌移动到目标桌对应座位，这个过程中的体力消耗为两桌距离的两倍，即从第 i 桌移动到第 j 桌对应座位的体力消耗为 2×|i−j|；
2.从目标桌的对应座位绕着桌子移动到目标座位，由于桌子是圆的，所以客人会选择最近的方向移动，体力消耗为移动距离的一倍，即从编号为 x 的座位移动的编号为 y 的座位的体力消耗为 min(|x−y|,m−|x−y|)；
详情如下图：
现在，给定每个客人的限制（即每个人的新座位所在的区间），需要你设计一个方案，使得所有客人消耗的体力和最小；本题中假设客人在移动的时候互不影响。
输入格式
从标准输入读入数据。
第一行输入两个数 n 和 m；
接下来输入 n 行，每行 m 个空格隔开的整数描述矩阵 L：其中，第 i 行的第 j 个数表示 Li,j；
接下来输入 n 行，每行 m 个空格隔开的整数描述矩阵 R：其中，第 i 行的第 j 个数表示 Ri,j。
输出格式
输出到标准输出。
输出总体力消耗的最小值，如果没有合法的方案输出no solution。
题解：
- 由原来的人向现在的每个可达的位置连边桌子连边做费用流($zkw$)有70；
- 设源$S$,汇$T$，原来的人为$s_{ij}$,现在的位置为$t_{ij}$，同桌之间移动的代价$c1$，不同桌的为$c2$；
- 这题的一大特点就是原来的人向现在的对应位置的连边是区间$[L_{i,j},R_{i,j}]$;
- 考虑用线段树优化建边，就是所有的$s_{i,j}$点先连向线段树，再连向$t_{i,j}$;
- 由于要共用线段树的节点所以需要对代价$c2$做一些转化;
- 将$t$拆成$t1$和$t2$分别表示不同桌向左走或向右走，$S$连向$s_{i,j}$代价$i*2$ ，$t1$,$t2$连向$T$代价$-i*2$；
- 建两颗线段树，叶子节点分别连向$t1$和$t2$，区间[L,R]拆成[L,i]和[i,R]即可向线段树节点连边；
- 节点个数$O(3*nm + 8*nm)$，边数$O( 3*nm + 4*nm + 8*nm + logn * nm)$
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=,K=;
int S,T,n,m,o,hd[N],dis[N],vis[N],sum1[K],sum2[K];
int id1[K][K],id2[K][K],id3[K][K],id4[K][K],L[K][K],R[K][K];
struct Edge{int v,nt,f,w;}E[N<<];
void adde(int u,int v,int f,int w){
E[o]=(Edge){v,hd[u],f,w};hd[u]=o++;
E[o]=(Edge){u,hd[v],,-w};hd[v]=o++;
}
queue<int>q;
bool bfs(){
memset(vis,,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q.push(T);dis[T]=;vis[T]=;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=;
for(int i=hd[u];~i;i=E[i].nt)if(E[i^].f){
int v=E[i].v;
if(dis[v]>dis[u]+E[i^].w){
dis[v]=dis[u]+E[i^].w;
if(!vis[v])vis[v]=,q.push(v);
}
}
}
return dis[S]!=inf;
}
int dfs(int u,int F){
vis[u]=;
if(u==T||!F)return F;
int flow=,f;
for(int i=hd[u];~i;i=E[i].nt){
int v=E[i].v;
if(!vis[v]&&dis[v]+E[i].w==dis[u]&&E[i].f&&(f=dfs(v,min(F,E[i].f)))){
flow+=f;F-=f;
E[i].f-=f,E[i^].f+=f;
if(!F)break;
}
}
return flow;
}
int zkw(){
int flow=,cost=,f;
while(bfs()){
do{
memset(vis,,sizeof(vis));
f=dfs(S,inf);
flow+=f;
cost+=dis[S]*f;
}while(vis[T]);
}
return flow==n*m?cost:-;
}
int main(){
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
memset(hd,-,sizeof(hd));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
id1[i][j]=(i-)*m+j;
id2[i][j]=n*m+id1[i][j];
id3[i][j]=n*m+id2[i][j];
id4[i][j]=n*m+id3[i][j];
}
S=,T=id4[n][m]+;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
adde(S,id1[i][j],,);
adde(id2[i][j],id4[i][j],,);
adde(id3[i][j],id4[i][j],,);
adde(id4[i][j],T,,);
int ri=j%m+,le=(j+m-)%m+;
adde(id2[i][j],id2[i][ri],inf,);
adde(id2[i][j],id2[i][le],inf,);
adde(id3[i][j],id3[i][ri],inf,);
adde(id3[i][j],id3[i][le],inf,);
if(i>)adde(id2[i][j],id2[i-][j],inf,);
if(i<n)adde(id3[i][j],id3[i+][j],inf,);
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){scanf("%d",&L[i][j]);sum2[++L[i][j]]++;}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){scanf("%d",&R[i][j]);sum1[++R[i][j]]++;}
for(int i=;i<=n;i++){
sum1[i]+=sum1[i-];
if(sum1[i]>i*m)return puts("no solution"),;
}
for(int i=n;i>=;i--){
sum2[i]+=sum2[i+];
if(sum2[i]>(n-i+)*m)return puts("no solution"),;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if(L[i][j]<=i&&i<=R[i][j])adde(id1[i][j],id2[i][j],,),adde(id1[i][j],id3[i][j],,);
else if(i<L[i][j])adde(id1[i][j],id3[L[i][j]][j],,(L[i][j]-i)<<);
else adde(id1[i][j],id2[R[i][j]][j],,(i-R[i][j])<<);
}
int ans = zkw();
if(!~ans)puts("-1");
else printf("%d\n",ans);
return ;
}70pts
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define il inline
#define ID(i,j) (i-1)*m+j
using namespace std;
const int N=,M=;
int n,m,L[][],R[][],ls1[],rs1[],ls2[],rs2[],cnt,rt1,rt2;
int S,T,o,hd[N],vis[N],dis[N],id1[],id2[],q[N],head,tail;
struct Edge{int v,nt,f,w;}E[M<<];
il void adde(int u,int v,int f,int w){
// printf("%d %d %d %d\n",u,v,f,w);
E[o]=(Edge){v,hd[u],f,w};hd[u]=o++;
E[o]=(Edge){u,hd[v],,-w};hd[v]=o++;
}
il void Adde(int u,int v,int f,int w){
for(int i=;i<=m;i++)adde(ID(u,i),ID(v,i),f,w);
}
void build1(int&k,int l,int r){
k=++cnt;
if(l==r){Adde(k,id2[l],inf,-*l);return;}
int mid=(l+r)>>;
build1(ls1[k],l,mid);
build1(rs1[k],mid+,r);
Adde(k,ls1[k],inf,);
Adde(k,rs1[k],inf,);
}
void build2(int&k,int l,int r){
k=++cnt;
if(l==r){Adde(k,id2[l],inf,-*(n-l+));return;}
int mid=(l+r)>>;
build2(ls2[k],l,mid);
build2(rs2[k],mid+,r);
Adde(k,ls2[k],inf,);
Adde(k,rs2[k],inf,);
}
void update1(int k,int l,int r,int x,int y,int i,int j,int val){
if(l==x&&r==y){adde(ID(id1[i],j),ID(k,j),inf,val);}
else{
int mid=(l+r)>>;
if(y<=mid)update1(ls1[k],l,mid,x,y,i,j,val);
else if(x>mid)update1(rs1[k],mid+,r,x,y,i,j,val);
else update1(ls1[k],l,mid,x,mid,i,j,val),update1(rs1[k],mid+,r,mid+,y,i,j,val);
}
}
void update2(int k,int l,int r,int x,int y,int i,int j,int val){
if(l==x&&r==y){adde(ID(id1[i],j),ID(k,j),inf,val);}
else{
int mid=(l+r)>>;
if(y<=mid)update2(ls2[k],l,mid,x,y,i,j,val);
else if(x>mid)update2(rs2[k],mid+,r,x,y,i,j,val);
else update2(ls2[k],l,mid,x,mid,i,j,val),update2(rs2[k],mid+,r,mid+,y,i,j,val);
}
}
bool spfa(){
for(int i=;i<=cnt*m;i++)vis[i]=,dis[i]=inf;
head=tail=;dis[q[tail++]=T]=;
while(head!=tail){
int u=q[head++];if(head==N)head=;
vis[u]=;
for(int i=hd[u];~i;i=E[i].nt)if(E[i^].f){
int v=E[i].v;
if(dis[v]>dis[u]+E[i^].w){
dis[v]=dis[u]+E[i^].w;
if(!vis[v]){
vis[v]=,q[tail++]=v;
if(tail==N)tail=;
}
}
}
}
return dis[S]!=inf;
}
int dfs(int u,int F){
vis[u]=;
if(u==T||!F)return F;
int flow=,f;
for(int i=hd[u];~i;i=E[i].nt){
int v=E[i].v;
if(E[i].f&&!vis[v]&&dis[v]+E[i].w==dis[u]&&(f=dfs(v,min(F,E[i].f)))){
flow+=f,F-=f;
E[i].f-=f,E[i^].f+=f;
if(!F)break;
}
}
return flow;
}
int zkw(){
int flow=,cost=,f;
while(spfa()){
do{
for(int i=;i<=cnt*m;i++)vis[i]=;
f=dfs(S,inf);
flow+=f;
cost+=dis[S]*f;
}while(vis[T]);
}
return (flow==n*m)?cost:-;
}
int main(){
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
memset(hd,-,sizeof(hd));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&L[i][j]),L[i][j]++;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&R[i][j]),R[i][j]++;
S=;T=++cnt;
for(int i=;i<=n;i++){
id1[i]=++cnt;
id2[i]=++cnt;
}
build1(rt1,,n);
build2(rt2,,n);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
adde(S,ID(id1[i],j),,);
adde(ID(id2[i],j),T,,);
adde(ID(id2[i],j),ID(id2[i],j%m+),inf,);
adde(ID(id2[i],j),ID(id2[i],(j+m-)%m+),inf,);
if(R[i][j]<=i)update1(rt1,,n,L[i][j],R[i][j],i,j,*i);
else if(L[i][j]>=i)update2(rt2,,n,L[i][j],R[i][j],i,j,*(n-i+));
else update1(rt1,,n,L[i][j],i,i,j,*i),
update2(rt2,,n,i,R[i][j],i,j,*(n-i+));
}
int ans=zkw();
if(!~ans)puts("no solution");
else printf("%d\n",ans);
return ;
}THUSC2017D1T3