#include <stdio.h>
int main()
{
	puts("转载请注明出处谢谢");
	puts("http://blog.csdn.net/vmurder/article/details/43199045");
}

题意：自己看去吧。

题解：如果不考虑这道题的某些小数据范围，

那么正解应该是：

首先平面图转对偶图，

然后扫描线处理名胜古迹

过程中运用到邪恶的平衡树（就算是set也依然恶心）

或者用神奇方法Ⅰ判断（cheat）一个名胜古迹在哪些域里面

[注: 域]：就是一些线段围起来的一块啦。

然后用神奇方法Ⅱ（cheat<<1）算出保护i个时是哪i个

然后是裸最小割噗。

所幸:

一、

名胜古迹最多10个，这样我们就可以暴力判断一个名胜古迹在哪些域里了

（枚举域的每一条边，然后判断onleft( 点 ， 有向边 )）

但是，即使这样，我们仍然需要神奇方法Ⅰ：

一个大多边形中间套一个小多边形，导致一个域是环形怎么办啊？！！！

一个多边形特么地是一个凹多边形，导致某名胜古迹在某条边的右边，但是依然在域里怎么办啊？！！！

所幸：

二、

题目中说“简单多边形”，

虽然简单多边形世上早有定义，但是显然出题人有解释权，可以解释没有这两种情况。。。

然后那个保护i个时需要保护的是哪些就无所谓啦~~~

暴搜一下又不是不能过~~

240ms又强又厉害（而且我还是渣常数呢！）

代码：

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 300
#define M 50000
#define eps 1e-9
#define inf 0x3f3f3f3f
const double pi=acos(-1.0);
using namespace std;

struct Point
{
	int x,y;
	void read(){scanf("%d%d",&x,&y);}
	Point(int _x=0,int _y=0):x(_x),y(_y){}
}point[N],palace[N];
struct Line
{
	int u,v,next;
	int crs,cost;
	double ang;
	Line(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost)
	{
		ang=atan2(point[v].y-point[u].y,point[v].x-point[u].x);
		if(ang<eps)ang+=2*pi;
		next=crs=0;
	}
}line[M];
bool cmp_eid(int a,int b){return line[a].ang-line[b].ang<eps;}
struct D
{
	int eid[105],m;
	void sort_the_eid(){sort(eid+1,eid+m+1,cmp_eid);}
}place[N];

struct KSD
{
	int v,len,il,next;
	void init(){len=il;}
}e[M];
int head[N],cnt;
inline void add(int u,int v,int len)
{
	e[++cnt].v=v;
	e[cnt].len=e[cnt].il=len;
	e[cnt].next=head[u];
	head[u]=cnt;
}

int s,t,d[N];
queue<int>q;
bool bfs()
{
	while(!q.empty())q.pop();
	memset(d,0,sizeof d);

	int i,u,v;
	q.push(s),d[s]=1;
	while(!q.empty())
	{
		u=q.front(),q.pop();
		for(i=head[u];i;i=e[i].next)if(e[i].len)
		{
			if(!d[v=e[i].v])
			{
				d[v]=d[u]+1;
				if(v==t)return 1;
				q.push(v);
			}
		}
	}
	return 0;
}
int dinic(int x,int flow)
{
	if(x==t)return flow;
	int remain=flow,i,v,k;
	for(i=head[x];i&&remain;i=e[i].next)
	{
		if(d[v=e[i].v]==d[x]+1&&e[i].len)
		{
			k=dinic(v,min(remain,e[i].len));
			if(!k)d[v]=0;
			e[i].len-=k,e[i^1].len+=k;
			remain-=k;
		}
	}
	return flow-remain;
}

int n,m,p;

int stk[M],top,tot;
void dfs_trans(int now,int end)
{
	stk[++top]=now;
	int id=line[now^1].next;
	if(id!=end)dfs_trans(id,end);
}
inline long long xmul(Point a,Point b,Point c)
{return (long long)(b.x-a.x)*(c.y-a.y)-(long long)(b.y-a.y)*(c.x-a.x);}
inline bool on_left(Point a,Line b)
{return xmul(a,point[b.u],point[b.v])>eps;}
bool check_t()
{
	long long sum=0;
	for(int i=1;i<=top;i++)sum+=xmul(Point(0,0),point[line[stk[i]].u],point[line[stk[i]].v]);
	return sum<eps;
}
bool check_p(int id)
{
	for(int i=1;i<=top;i++)
		if(!on_left(palace[id],line[stk[i]]))
			return 0;
	return 1;
}
int yc;
void build_map()
{
	int i,j,k;
	int a,b,c;
	scanf("%d%d%d",&p,&n,&m);
	cnt=1;
	for(i=1;i<=p;i++)palace[i].read();
	for(i=1;i<=n;i++)point[i].read();
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		line[++cnt]=Line(a,b,c);
		place[a].eid[++place[a].m]=cnt;
		line[++cnt]=Line(b,a,c);
		place[b].eid[++place[b].m]=cnt;
	}
	for(i=1;i<=n;i++)
	{
		place[i].sort_the_eid();
		if(!place[i].m)continue;
		for(j=2;j<=place[i].m;j++)
		{
			k=place[i].eid[j];
			line[k].next=place[i].eid[j-1];
		}
		line[place[i].eid[1]].next=place[i].eid[j-1];
	}
	k=cnt,cnt=1;
	tot=s=0;
	for(i=2;i<=k;i++)if(!line[i].crs)
	{
		dfs_trans(i,i);
		tot++;
		if(check_t())t=tot;
		else {
			for(j=1;j<=p;j++)if(check_p(j))
			{
				add(s,tot,0);
				add(tot,s,0);
			}
		}
		while(top)
		{
			int de=stk[top--];
			line[de].crs=tot;
		}
	}
	yc=cnt;
	for(i=2;i<=k;i+=2)
	{
		add(line[i].crs,line[i^1].crs,line[i].cost);
		add(line[i^1].crs,line[i].crs,line[i].cost);
	}
	return ;
}
bool vis[N];
int ans,maxflow;
void dfs_build(int dep,int deep,int now)
{
	int i;
	if(dep>deep)
	{
		for(i=1;i<=p;i++)
		{
			if(vis[i])e[i<<1].len=e[i<<1|1].len=inf;
			else e[i<<1].len=e[i<<1|1].len=0;
		}
		for(i=p*2+2;i<=cnt;i++)e[i].init();
		maxflow=0;
		while(bfs())maxflow+=dinic(s,inf);
		ans=min(ans,maxflow);
		return ;
	}
	int uplimit=p-deep+dep;
	for(i=now;i<=uplimit;i++)
	{
		vis[i]=1;
		dfs_build(dep+1,deep,i+1);
		vis[i]=0;
	}
	return ;
}

int main()
{
//	freopen("test.in","r",stdin);
	build_map();
	for(int i=1;i<=p;i++)
	{
		ans=inf;
		dfs_build(1,i,1);
		printf("%d\n",ans);
	}
	return 0;
}

【BZOJ2965】保护古迹 平面图转对偶图，暴力，网络流