P3357 最长k可重线段集问题 题解
Post time: 2020-03-04 18:59:51
题目链接
网络流题目，关键在于建模。
这题是个最大费用最大流，最大流保证k可重，最大费用就是题目求的最长的长度。
建模：
-
对于输入的 \(x_i\) 和 \(y_i\)，我们计算此线段的长度 \(Len_i\)：\(Len_i=\sqrt {x^2_i+y^2_i}\)
-
\(S\to 1\) 流 \(k\)，费用 \(0\)
-
\(i-1\to i\)，流 \(k\)，费用 \(0\)
-
\(i\to j(i\le j)\) 因为可能出现 \(x\) 坐标相同（线段平行于 \(y\) 轴）的情况，所以这里要拆点，每个点拆为 \(2i-1\) 和 \(2i\)。我们设这两个点为 \(X_i\) 和 \(Y_i\)。将 \(i\) 和 \(j\) 离散化之后：若 \(i=j\)，那么连 \(X_i\) 和 \(Y_i\)；若 \(i\neq j\)，连 \(Y_i\) 和 \(X_j\)。流都是 \(k\)，费用都是 \(Len_i\)。
-
连 \(X_n\),\(Y_n\) 到 \(t\)，流 \(k\)，费用 \(0\)。
建模毕。
然后就是 mcmf 板子，注意最大费用最大流最好是边权取反然后跑正常的，但是本人比较懒就直接在SPFA中换了个符号：
if(f&&dist[v]>dist[u]+w)
这里把 > 直接改了 <，数据小的话应该没问题。
注意初始化要改成
memset(dist,0xcf,sizeof(dist));
其他没什么了，上代码：
点击查看代码
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1000+5,INF=0x3f3f3f3f;
struct Edge{int u,v,f,w,nxt;}e[N*N];
int h[N],flow[N],dist[N],pre[N],last[N];
bool vis[N];
int l[N],r[N],a[N*2],len[N];
int n,m,s,t,k,tot=1,mc,mf;
inline void add(int u,int v,int f,int w){//建图，建双向边
e[++tot]=(Edge){u,v,f,w,h[u]};h[u]=tot;
e[++tot]=(Edge){v,u,0,-w,h[v]};h[v]=tot;
}
bool spfa(){
memset(dist,0xcf,sizeof(dist));//跑最大费用，dist要赋无穷小
memset(vis,0,sizeof(vis));
memset(flow,0x3f,sizeof(flow));
queueq;
q.push(s);
dist[s]=0;
vis[s]=1;
pre[t]=-1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,f=e[i].f,w=e[i].w;
if(f&&dist[v]r[i]) swap(l[i],r[i]);
len[i]=sqrt(pow(y1-y2,2)+pow(r[i]-l[i],2));//计算Len[i]
l[i]<<=1,r[i]<<=1;
if(l[i]==r[i]) r[i]++;
else l[i]++;
a[i]=l[i],a[i+n]=r[i];
}
//下面是拆点
sort(a+1,a+2*n+1);
m=unique(a+1,a+2*n+1)-a-1;s=m+1,t=m+2;
for(int i=1,L,R;i<=n;++i){
L=lower_bound(a+1,a+m+1,l[i])-a;
R=lower_bound(a+1,a+m+1,r[i])-a;
add(L,R,1,len[i]);
}
for(int i=1;i<=m;++i){
if(i==1) add(s,i,k,0);
else{
add(i-1,i,k,0);
if(i==m) add(i,t,k,0),add(i,t,k,0);
}
}
mcmf();
printf("%d\n",mc);//输出最大费用
return 0;
}