【BZOJ 2965】保護古跡平面図回転対偶図、暴力、ネットワークフロー

#include <stdio.h>
int main()
{
	puts("         ");
	puts("http://blog.csdn.net/vmurder/article/details/43199045");
}

标题:自分で見に行こう.
問題解:この問題のいくつかの小さなデータ範囲を考慮しないと、
では、正解は次のとおりです.
まず平面図を対偶図に回し、
そして走査線で名所旧跡を処理します
過程で邪悪なバランスツリーに運用(setでも気持ち悪い)
あるいは不思議な方法Iで1つの名所旧跡がどのドメインの中にあるかを判断します
[注:ドメイン]:いくつかのセグメントで囲まれています.
そして不思議な方法II(cheat<<1)でi個を保護する際のi個を算出する
そして裸最小割ぷっ.
幸い:
一、
名所旧跡は最大10個で、どの地域にあるかを暴力的に判断することができます.
(ドメインの各エッジを列挙し、onleft(ポイント、エッジあり))を判断します.
しかし、それでも不思議な方法が必要です.
大きなポリゴンの中に小さなポリゴンをセットして、ドメインがリングになったらどうしますか?!!
1つの多角形は特に1つの凹んだ多角形で、ある名所旧跡がある辺の右側にあることを招いて、しかし依然としてドメインの中でどうしますか?!!!
幸い:
二、
「単純多角形」というタイトルで、
単純多角形は世界でとっくに定義されているが、出題者には解釈権があり、この2つの状況がないことを説明することができるのは明らかだ.の
そしてその保護i個の時に守るべきものは何でもいい~~~
暴捜しても通れないわけではない~~
240 msは強くてすごい(しかも私はスラグ定数です!)
コード:

#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
",ans);
	}
	return 0;
}