almost 4 years ago

裸的km……但是坑很大

主要还是载在了关于三点共线的判断上

1、最好用叉积,这样不用考虑无斜率的情况

2、判断一点是否在两点炼成的线段中间,算出横纵坐标的范围,判断是否符合

其实w[][]很多blog上初始值是负无穷的。但是我在这里开了一个lt[][]所以在每次向下走之前判断一下是否连边。【其实如果不判断的话总觉得remain有可能很大然后爆掉】

``` c++

include

include

include

include

include

include

include

include

define maxn 2001

define inf 1000000000

define eps 1e-7

using namespace std;
short w[maxn][maxn]={0};
bool lt[maxn][maxn]={false};
int res[maxn]={0};
int slack[maxn*2]={0},l[maxn*2]={0};
bool visx[maxn]={0},visy[maxn*2]={0};
int d,n;
struct point
{
int x,y;
}a[maxn*2]={0};
mapq;
string st;
void change(string &st)
{
int l=st.length();
for (int i=0;i if (st[i]>='a') st[i]=st[i]-32;
}
void swap(int &x,int &y)
{
int o=x;x=y;y=o;
}
bool find(int x)
{
visx[x]=true;
for (int i=n+1;i<=(n< if (lt[x][i]&&!visy[i])
{
int remain=l[x]+l[i]-w[x][i];
if (remain==0)
{
visy[i]=true;
if (res[i]==-1||find(res[i]))
{
res[i]=x;return true;
}
}
else slack[i]=min(slack[i],remain);
}
return false;
}
int max(int x,int y)
{
if (x }
int km()
{int i,j;
memset(res,-1,sizeof(res));
for (i=1;i for (j=n+1;j if (lt[i][j])l[i]=max(l[i],w[i][j]);
for (i=1;i {
memset(slack,0x7f,sizeof(slack));
while (true)
{
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if (find(i)) break;
int minn=inf;
for (j=n+1;j if (!visy[j]) minn=min(minn,slack[j]);
for (j=1;j if (visx[j]) l[j]-=minn;
for (j=n+1;j if (!visy[j]) slack[j]-=minn; else l[j]+=minn;
}
}
int result=0;
for (i=1+n;i if (res[i]!=-1) result+=w[res[i]][i];
return result;
}
double calc(int p,int q)
{
return sqrt((a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y));
}
double fabs(double x)
{
if (x }
int dcmp(double x,double y)
{
if (fabs(x-y) if (x>y) return 1;return -1;
}
bool judge(int p,int q,int o)
{ int x1=min(a[p].x,a[q].x),x2=max(a[p].x,a[q].x),y1=min(a[p].y,a[q].y),y2=max(a[p].y,a[q].y);
if (a[o].x<=x2&&a[o].x>=x1&&a[o].y<=y2&&a[o].y>=y1) return true;
return false;
}
int calccross(int x1,int y1,int x2,int y2)
{
return (x1*y2-x2*y1);
}
int cross(int x,int y,int z)
{
return calccross(a[y].x-a[x].x,a[y].y-a[x].y,a[z].x-a[x].x,a[z].y-a[x].y);
}
int main()
{
int x,y,i,j,k;
scanf("%d%d",&d,&n);
for (i=1;i<=n*2;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
cin>>st;change(st);q[st]=i;
}
memset(w,0,sizeof(w));
for (i=1;i<=n;i++)
for (j=(n+1);j<=(n< {if (dcmp(calc(i,j),d) {
int bj=0;
for (k=1;k if (k!=i&&k!=j)
{
if (cross(i,j,k)==0&&judge(i,j,k))
{bj=1;
break;}
}
if (bj==0)lt[i][j]=true,w[i][j]=1;
}
}
while (true)
{
cin>>st; if (st=="End") break;change(st);x=q[st];
cin>>st;change(st);y=q[st];
if (x>y) swap(x,y);
scanf("%d",&k);
if (lt[x][y])w[x][y]=k;
}
printf("%d\n",km());
}
```

← 【bzoj1492】【cdq分治】【整体二分】【动态凸包】货币兑换 【bzoj1225】求正整数 →
 
comments powered by Disqus