AtCoder agc_034D – Manhattan Max Matching(最大费用最大流)


AtCoder agc_034D – Manhattan Max Matching
题目大意
平面上有

N

N

N个位置上分别有若干红点,

N

N

N个位置上分别有若干蓝点,保证红点蓝点总数相等。求一个红点和蓝点的匹配,使得每个点对的曼哈顿距离之和最大,输出最小的答案。

N

1000

N≤1000

N≤1000
题解
据说奇奇怪怪限制的题,一般会想到网络流,这题还有关点对之间的匹配,则更像是网络流。观察题目的限制,不同的匹配权值不同,考虑使用费用流,即最大费用最大流。由于曼哈顿距离的式子中有绝对值,先把绝对值拆开,会出现四种情况,分别是

(

x

i

x

j

)

+

(

y

i

y

j

)

(x_i-x_j)+(y_i-y_j)

(xi​−xj​)+(yi​−yj​)、

(

x

i

x

j

)

+

(

y

j

y

i

)

(x_i-x_j)+(y_j-y_i)

(xi​−xj​)+(yj​−yi​)、

(

x

j

x

i

)

+

(

y

i

y

j

)

(x_j-x_i)+(y_i-y_j)

(xj​−xi​)+(yi​−yj​)、

(

x

j

x

i

)

+

(

y

j

y

i

)

(x_j-x_i)+(y_j-y_i)

(xj​−xi​)+(yj​−yi​),
先从源点连向每个红点的位置(简称为红点),费用为

0

0

0,容量为这个位置上的点数;每个蓝点连向汇点同理, 接着上述四种情况对应另外新设的四个点,每个红点往这四个点连边,容量正无穷,费用为这个点的代表的式子中

x

i

x_i

xi​和

x

j

x_j

xj​分别对应的正负之和,这四个点再连向蓝点,边权同理。但是会发现,这样能保证流出的费用正好是曼哈顿距离吗?如果一对匹配不是恰好在大减小的位置流过,那不就错了吗?其实会发现,因为题目求的是最大费用,而加上绝对值一定是大于等于没有绝对值的,所以最终流过去的方案必然会是曼哈顿距离,且必为最优解。至于最大费用最大流,只需要把费用流SPFA中的最短路改成最长路即可。
代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1010
#define ll long long
int last[N*2],cur[N*2],len=1;
ll dis[N*2];
int q[N*2],p[N*2];
ll ans=0;
struct
{
int c,w,to,next;
}a[N*20];
int n,ns,m;
void add(int x,int y,int c,int w)
{
a[++len].to=y;
a[len].next=last[x];
a[len].c=c,a[len].w=w;
last[x]=len;
}
int id = 0;
int SPFA()
{
for(int i=0;i<=ns;i++) dis[i]=-1e16;
q[1]=0,p[0]=++id,dis[0]=0;
int l=0,r=1;
while(l!=r)
{
l=l%(ns+10)+1;
int k=q[l];
p[k]=0;
for(int i=last[k];i;i=a[i].next)
{
int x=a[i].to;
if(dis[k]+a[i].w>dis[x]&&a[i].c)
{
dis[x]=dis[k]+a[i].w;
if(p[x] < id)
{
p[x]=id;
r=r%(ns+10)+1;
q[r]=x;
}
}
}
}
return dis[ns]>0;
}
int dfs(int k,int flow)
{
if(k==ns) return flow;
int have=0;
p[k]=1;
for(int i=cur[k];i;i=a[i].next)
{
int x=a[i].to;
if(!p[x]&&dis[k]+a[i].w==dis[x]&&a[i].c)
{
cur[k] = i;
int t=min(flow-have,a[i].c);
int now=dfs(x,t);
ans+=(ll)now*a[i].w;
have+=now,a[i].c-=now,a[i^1].c+=now;
if(have==flow) break;
}
}
p[k]=0;
return have;
}
int main()
{
int i,x,y,c;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&c);
add(i,2*n+1,c,x+y);
add(2*n+1,i,0,-x-y);
add(i,2*n+2,c,x-y);
add(2*n+2,i,0,y-x);
add(i,2*n+3,c,y-x);
add(2*n+3,i,0,x-y);
add(i,2*n+4,c,-x-y);
add(2*n+4,i,0,x+y);
add(0,i,c,0);
add(i,0,0,0);
}
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&c);
add(2*n+1,i+n,1e6,-x-y);
add(i+n,2*n+1,0,x+y);
add(2*n+2,i+n,1e6,y-x);
add(i+n,2*n+2,0,x-y);
add(2*n+3,i+n,1e6,x-y);
add(i+n,2*n+3,0,y-x);
add(2*n+4,i+n,1e6,x+y);
add(i+n,2*n+4,0,-x-y);
add(i+n,2*n+5,c,0);
add(2*n+5,i+n,0,0);
}
ns=2*n+5;
while(SPFA())
{
while(1) {
for(i = 0; i <= ns; i++) cur[i] = last[i];
int t = dfs(0,1e6);
if(!t) break;
}
}
printf("%lld",ans);
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

AtCoder agc_034D - Manhattan Max Matching(最大费用最大流)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » AtCoder agc_034D – Manhattan Max Matching(最大费用最大流)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏