HDU 4606 Occupy Cities 解题报告

报告"/>

HDU 4606 Occupy Cities 解题报告

题目

2013 多校训练 第一场

题意：

有n个城市，m个边界线，p名士兵。现在士兵要按一定顺序攻占城市，但从一个城市到另一个城市的过程中不能穿过边界线。士兵有一个容量为K的背包装粮食，士兵到达一个城市可以选择攻占城市或者只是路过，如果攻占城市，就能装满背包。从城市到城市消耗的粮食等于两城市的距离，如果距离大于士兵当前的背包的容量，士兵就不能走这条路。士兵可以选择空降一次，空降不耗费。求p个士兵攻占完所有城市所需要的最小背包容量k。

解法：

很容易想到二分答案。

先用线段求交和floyed求出两个城市之间的最短距离(即两城市路上不攻占任何城市的最小花费)，两个城市(u,v)如果从u到v需要跨过边境线或者城市u在v之后被攻占其距离就设为inf。

现在问题变成p个士兵攻打n个城市，如果某两个城市间距离小于mid就可达，如何判断能否攻占完n个城市？

利用二分图匹配，最小路径覆盖：在一个P*P的有向图中，在图中找一些路经，使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联，最小路径=点数-最大匹配数。只需要判断最小路径覆盖是否小于等于p即可，因为最小路径覆盖即攻占完所有城市所需要的最少士兵数。

代码：

#include #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 105
const double EPS=1e-6;
const int INF=1000000000;
int n,m,p;
int ord[maxn],result[maxn];
bool state[maxn];
double dis[maxn*3][maxn*3];
int dcmp(double x)
{if (fabs(x)<EPS) return 0;return x<0?-1:1;
}
struct Point
{double x,y;Point(){}Point(double a,double b):x(a),y(b){}Point operator+(const Point &a)const{ return Point(x+a.x,y+a.y); }Point operator-(const Point &a)const{ return Point(x-a.x,y-a.y); }void input(){scanf("%lf%lf",&x,&y);}
}C[maxn*3];
struct Line
{Point a,b;
}L[maxn];
typedef Point Vector;
double Cross(Vector a,Vector b)
{return a.x*b.y-a.y*b.x;
}
double Dot(Vector a,Vector b)
{return a.x*b.x+a.y*b.y;
}
double Dist(Vector a)
{return sqrt(Dot(a,a));
}
bool Ispinter(Point a,Point b,Point c,Point d)
{double c1=Cross(b-a,c-a),c2=Cross(b-a,d-a),c3=Cross(d-c,a-c),c4=Cross(d-c,b-c);return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
int find(int x,double key)
{for (int i=1;i<=n;i++)if (!state[i]&&dis[x][i]<key+EPS){state[i]=1;if (!result[i]||find(result[i],key)){result[i]=x;return 1;}}return 0;
}
int solve(double key)
{int ans=0;memset(result,0,sizeof(result));for (int i=1;i<=n;i++){memset(state,0,sizeof(state));if (find(i,key)) ans++;}return n-ans;
}
int main()
{//freopen("/home/christinass/code/in.txt","r",stdin);int cas,d,num;scanf("%d",&cas);while (cas--){scanf("%d%d%d",&n,&m,&p);for (int i=1;i<=n;i++) C[i].input();num=n;for (int i=1;i<=m;i++){L[i].a.input(),L[i].b.input();C[++num].x=L[i].a.x,C[num].y=L[i].a.y;C[++num].x=L[i].b.x,C[num].y=L[i].b.y;}for (int i=1;i<=n;i++){scanf("%d",&d);ord[d]=i;}for (int i=1;i<=num;i++)for (int j=1;j<=num;j++) dis[i][j]=INF;for (int i=1;i<=num;i++)for (int j=i+1;j<=num;j++){bool flag=1;for (int k=1;k<=m&&flag;k++)if (Ispinter(C[i],C[j],L[k].a,L[k].b)) flag=0;if (flag) dis[i][j]=dis[j][i]=Dist(C[i]-C[j]);}for (int k=1;k<=num;k++)for (int i=1;i<=num;i++)for (int j=1;j<=num;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (ord[i]>=ord[j]) dis[i][j]=INF;double l=0,r=INF;while (l<r-EPS){double mid=(l+r)/2;if (solve(mid)<=p) r=mid;else l=mid;}printf("%.2f\n",(l+r)/2);}return 0;
}

二分图有关的其他性质：

最小点覆盖=最大匹配。给定一个二分图G=(V,E)，定义一个点如果被覆盖，那么称所有与这个点相邻的弧被覆盖，求最少需要覆盖多少个点才能覆盖所有的边。

最大独立集=顶点数-最大匹配。独立集：图中两两互不连通的顶点构成的集合。

最小路径覆盖=顶点数-最大匹配。