题目大意

　　有 \(n\) 个圆形的桌子排成一排，每个桌子有 \(m\) 个座位。

　　最开始每个位置上都有一个人。现在每个人都要重新选择一个座位，第 \(i\) 桌的第 \(j\) 个人的新座位只能在第 \(l_{i,j}\) 到第 \(r_{i,j}\) 桌之间选。

　　选完后，所有人会移动到他选择的座位上去。如果一个人从第 \(i\) 桌的第 \(x\) 个座位移动到第 \(j\) 桌的第 \(y\) 个座位，那么花费的体力是 \(2\lvert i-j\rvert +\min(\lvert x-y\rvert,m-\lvert x-y\rvert)\)。

　　求一种方案，使得所有人消耗的体力之和最小。

　　\(n\leq 300,m\leq 10\)

题解

　　直接跑 KM 是 \(O(n^3m^3)\) 的。可以拿到很多分。

　　先把每个桌子的所有人连成一个环。

　　然后对于所有桌的第 \(i\) 个位置建两棵线段树，分别代表向左走和向右走。总共就是 \(20\) 棵线段树。

　　然后跑费用流就好了。

　　点数为 \(O(nm)\)，边数为 \(O(nm\log n)\)。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             //using namespace std;using std::min;using std::max;using std::swap;using std::sort;using std::reverse;using std::random_shuffle;using std::lower_bound;using std::upper_bound;using std::unique;using std::vector;typedef long long ll;typedef unsigned long long ull;typedef double db;typedef long double ldb;typedef std::pair
             
               pii;typedef std::pair
              
                pll;void open(const char *s){#ifndef ONLINE_JUDGE char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}void open2(const char *s){#ifdef DEBUG char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}int upmin(int &a,int b){if(b
               
                a){a=b;return 1;}return 0;}const int inf=0x3fffffff;namespace flow{ int cnt; int v[1000010]; int t[1000010]; int c[1000010]; int w[1000010]; int h[1000010]; int vis[12000]; void add(int x,int y,int _c,int _w) { cnt++; v[cnt]=y; t[cnt]=h[x]; c[cnt]=_c; w[cnt]=_w; h[x]=cnt; } int len,cost,flow; int num; int S,T; int op(int x) { return ((x-1)^1)+1; } int aug(int x,int fl) { if(x==T) { flow+=fl; cost+=len*fl; return fl; } vis[x]=1; int s=0; for(int i=h[x];i;i=t[i]) if(c[i]&&!w[i]&&!vis[v[i]]) { int d=aug(v[i],min(fl,c[i])); c[i]-=d; c[op(i)]+=d; s+=d; fl-=d; if(!fl) break; } return s; } int gao() { int s=inf; for(int i=1;i<=num;i++) if(vis[i]) for(int j=h[i];j;j=t[j]) if(c[j]&&!vis[v[j]]) s=min(s,w[j]); if(s==inf) return 0; for(int i=1;i<=num;i++) if(vis[i]) for(int j=h[i];j;j=t[j]) { w[j]-=s; w[op(j)]+=s; } len+=s; return 1; } void solve() { flow=cost=len=0; do do memset(vis,0,sizeof vis); while(aug(S,inf)); while(gao()); }}void add(int x,int y,int c,int w){ flow::add(x,y,c,w); flow::add(y,x,0,-w);}int nodecnt;int n,m;int id(int x,int y){ return (x-1)*m+y;}struct seg{#define lc (p<<1)#define rc ((p<<1)|1)#define mid ((L+R)>>1) int s1[10000]; int s2[10000]; void build(int p,int k,int L,int R) { if(L==R) { s1[p]=s2[p]=id(L,k)+n*m; return; } s1[p]=++nodecnt; s2[p]=++nodecnt; build(lc,k,L,mid); build(rc,k,mid+1,R); add(s1[p],s1[lc],inf,(R-mid)*2); add(s1[p],s1[rc],inf,0); add(s2[p],s2[lc],inf,0); add(s2[p],s2[rc],inf,(mid-L+1)*2); } void gao1(int p,int l,int r,int x,int y,int L,int R) { if(l<=L&&r>=R) { add(y,s1[p],inf,(x-R)*2); return; } if(l<=mid) gao1(lc,l,r,x,y,L,mid); if(r>mid) gao1(rc,l,r,x,y,mid+1,R); } void gao2(int p,int l,int r,int x,int y,int L,int R) { if(l<=L&&r>=R) { add(y,s2[p],inf,(L-x)*2); return; } if(l<=mid) gao2(lc,l,r,x,y,L,mid); if(r>mid) gao2(rc,l,r,x,y,mid+1,R); }}seg[11];int l[1010][12];int r[1010][12];int main(){ open("seat"); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&l[i][j]); l[i][j]++; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&r[i][j]); r[i][j]++; } nodecnt=2*n*m; for(int i=1;i<=m;i++) seg[i].build(1,i,1,n); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(l[i][j]<=i) seg[j].gao1(1,l[i][j],min(r[i][j],i),i,id(i,j),1,n); if(r[i][j]>=i) seg[j].gao2(1,max(l[i][j],i),r[i][j],i,id(i,j),1,n); } flow::S=++nodecnt; flow::T=++nodecnt; flow::num=nodecnt; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { add(n*m+id(i,j),n*m+id(i,j%m+1),inf,1); add(n*m+id(i,j),n*m+id(i,(j-2+m)%m+1),inf,1); } for(int i=1;i<=n*m;i++) { add(flow::S,i,1,0); add(i+n*m,flow::T,1,0); } flow::solve(); if(flow::flow