这道题 51nod只Ac了十二个人 没有题解可以研究 所以就自己YY了半天 在这里先感谢一波岚清大爷 orz
然后这道题我分了两种情况 一种是左边的往左跑右边的往右跑 中间有一部分直接走不用跑左右
另一种是全部都要跑左右 然后有一部分点需要左右都跑的 但是左跑和右跑的有一部分点会相互冲突 这个时候需要处理一波矛盾关系
讲的不清楚 给一份数据自己模拟试试吧（再次感谢一波 orzllq）
1
5 11
5 3
3 4
1 10
7 9
9 1
这个时候 我们第一个想到的是一波网络流找最小割 经过一波混乱以后 代码成功出世并且意外AC了 贴一波代码
当然也可以贪心枚举而且数据大了会快很多 推荐一篇写的很全的博客吧 orzzsn
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define LL long long
using namespace std;
const int M=,inf=0x3f3f3f3f;
LL read(){
LL ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL ans,sum,cnt;
LL n,L,m,S,T;
int f[M][M];
struct node{LL l,r;}e[*M];
bool cmp(node a,node b){return a.l<b.l;}
int first[M],cur[M];
struct note{LL to,next,flow;}q[*M*M];
void ins(LL a,LL b,LL flow){cnt++; q[cnt].to=b; q[cnt].flow=flow; q[cnt].next=first[a]; first[a]=cnt;}
void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}
void find1(LL x,LL k){
bool f=;
LL now=e[x].r;
for(int i=k+;i<=n;i++) if(now>e[i].r) insert(x,i,inf),f=;
if(f) insert(S,x,*(L-e[x].r));
}
void find2(LL x,LL k){
LL now=e[x].r;
for(int i=;i<=k;i++) if(now<e[i].r){
insert(x,T,*e[x].r);
break;
}
}
int check(int x){
LL mx1=,mx2=L,now=e[x].r;
for(int i=;i<x;i++) mx1=max(mx1,e[i].r);
for(int i=x+;i<=n;i++) mx2=min(mx2,e[i].r);
return mx1<now&&mx2>now;
}
int okay(int x){
LL mx1=,mn1=L;
for(int i=;i<=x;i++) mx1=max(mx1,e[i].r);
for(int i=x+;i<=n;i++) mn1=min(mn1,e[i].r);
return mx1<mn1;
}
LL calc1(int x){
LL sum=;
for(int i=;i<=x;i++) sum=sum+e[i].l+e[i].r;
return sum;
}
LL calc2(int x){
LL sum=;
for(int i=x;i<=n;i++) sum=sum+(*L-e[i].l-e[i].r);
return sum;
}
LL pd(LL x){return x>=?x:-x;}
LL d[M],st[M];
int bfs(){
memset(d,-,sizeof(d));
int head=,tail=;
st[]=S; d[S]=;
while(head!=tail){
int x=st[head++]; if(head>M) head=;
for(int i=first[x];i;i=q[i].next){
int now=q[i].to;
if(q[i].flow&&d[now]==-){st[tail++]=now; d[now]=d[x]+; if(tail>M) tail=;}
}
}
return d[T]!=-;
}
LL dfs(LL x,LL a){
if(x==T||a==) return a;
int f,flow=;
for(int &i=cur[x];i;i=q[i].next){
int now=q[i].to;
if(d[now]==d[x]+&&(f=dfs(now,min(a,q[i].flow)))>){
q[i].flow-=f; q[i^].flow+=f;
flow+=f;
a-=f; if(a==) break;
}
}
return flow;
}
LL dinic(){
LL ans=;
while(bfs()){for(int i=;i<=T;i++) cur[i]=first[i]; ans+=dfs(S,inf);}
return ans;
}
int main()
{
for(int v=read();v;v--){
ans=inf; n=read(); L=read();
for(int i=;i<=n;i++) e[i].l=read(),e[i].r=read();
e[].l=; e[].r=; e[n+].l=L; e[n+].r=L;
sort(e+,e++n,cmp);
sum=; for(int i=;i<=n;i++) sum=sum+e[i].l+e[i].r; ans=min(ans,sum);
sum=; for(int i=;i<=n;i++) sum=sum+(*L-e[i].r-e[i].l); ans=min(ans,sum);
for(int i=;i<=n;i++)if(okay(i)){
int k=i+; sum=;
sum+=calc1(i);
while(check(k)) sum=sum+pd(e[k].r-e[k].l),k++;
sum+=calc2(k);
ans=min(ans,sum);
}
for(int i=;i<=n;i++){
sum=; cnt=; S=; T=n+;
memset(first,,sizeof(first));
sum+=calc1(i)+calc2(i+);
for(int k=;k<=i;k++) find1(k,i);
for(int k=i+;k<=n;k++) find2(k,i);
sum+=dinic();
ans=min(ans,sum);
}
printf("%lld\n",ans);
}
return ;
}