BZOJ 1108 POI2007 天然气管道Gaz

题目大意:给定平面上的n个黑点和n个白点。一个黑点仅仅能和右下方的白点匹配。代价为曼哈顿距离,求最小权值完备匹配

STO OTZ

STO OTZ

STO OTZ

ans=Σ(y黑-y白+x白-x黑)

=Σy黑-Σy白+Σx白-Σx黑

然后。。

。233333333333333333333

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
long long ans;
int main()
{
	int i,x,y;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		ans-=x;ans+=y;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		ans+=x;ans-=y;
	}
	cout<<ans<<endl;
	return 0;
}


原文地址:https://www.cnblogs.com/mfmdaoyou/p/6951148.html