题面

传送门

思路

其实就是很明显的平面图模型。

不咕咕咕的平面图学习笔记

用最左转线求出对偶图的点，以及原图中每个边两侧的点是谁

建立网络流图：

源点连接至每一个对偶图点，权值为这个区域的光明能量

每一个对偶图点连接至汇点，权值为这个区域的黑暗能量

对于每一条原图中的边，在它两侧的对偶图点之间连一条双向边，权值为这个边的代价

用所有点的光明能量和黑暗能量之和，减去最小割，得到的就是答案

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#include<cmath>

#include<map>

#include<vector>

#include<queue>

#define next DEEP_DARK_FANTASY

#define mp make_pair

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

int n,m,T,x[100010],y[100010],light[100010],dark[100010],cnt;

vector<pair<int,int> >e[100010];

vector<pair<long double,int> >ee;

map<int,int>suf[100010],col[100010];

int suml[100010],sumd[100010];

namespace g{//当前弧dinic

	int first[100010],cnte=-1;

	struct edge{

		int to,next,w;

	}a[1000010];

	inline void init(){memset(first,-1,sizeof(first));}

	inline void add(int u,int v,int w1,int w2){

		a[++cnte]=(edge){v,first[u],w1};first[u]=cnte;

		a[++cnte]=(edge){u,first[v],w2};first[v]=cnte;

	}

	int dep[100010],cur[100010];queue<int>q;

	inline bool bfs(int s,int t){

		int i,u,v;

		for(i=s;i<=t;i++) dep[i]=-1,cur[i]=first[i];

		dep[s]=0;q.push(s);

		while(!q.empty()){

			u=q.front();q.pop();

			for(i=first[u];~i;i=a[i].next){

				v=a[i].to;if(~dep[v]||!a[i].w) continue;

				dep[v]=dep[u]+1;q.push(v);

			}

		}

		return ~dep[t];

	}

	inline int dfs(int u,int t,int lim){

		if(u==t||!lim) return lim;

		int i,v,f,flow=0;

		for(i=cur[u];~i;i=a[i].next){

			v=a[i].to;cur[u]=i;

			if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(a[i].w,lim)))){

				a[i].w-=f;a[i^1].w+=f;

				flow+=f;lim-=f;

				if(!lim) return flow;

			}

		}

		return flow;

	}

	inline int dinic(int s,int t){

		int re=0;

		while(bfs(s,t)) re+=dfs(s,t,1e9);

		return re;

	}

}

int main(){

	T=read();n=read();m=read();int i,j,t1,t2,t3,tot,pos,from,next;

	for(i=1;i<=n;i++){

		x[i]=read();y[i]=read();

		light[i]=read();dark[i]=read();

	}

	for(i=1;i<=m;i++){

		t1=read();t2=read();t3=read();

		e[t1].push_back(mp(t2,t3));

		e[t2].push_back(mp(t1,t3));

	}

	for(i=1;i<=n;i++){

		tot=e[i].size();ee.clear();

		for(j=0;j<tot;j++){

			ee.push_back(mp(atan2(y[e[i][j].first]-y[i],x[e[i][j].first]-x[i]),e[i][j].first));

		}

		sort(ee.begin(),ee.end());

		for(j=0;j<tot-1;j++){//最左转线预处理：标记每一个点的后继

			suf[i][ee[j].second]=ee[j+1].second;

		}

		if(tot) suf[i][ee[tot-1].second]=ee[0].second;

	}

	for(i=1;i<=n;i++){

		for(j=0;j<e[i].size();j++){

			pos=e[i][j].first;from=i;

			if(col[i][pos]) continue;

			cnt++;

			col[i][pos]=cnt;

			suml[cnt]+=light[pos];

			sumd[cnt]+=dark[pos];

			while(1){//求出一个区域

				next=suf[pos][from];

				if(col[pos][next]) break;

				from=pos;pos=next;

				col[from][pos]=cnt;

				suml[cnt]+=light[pos];

				sumd[cnt]+=dark[pos];

			}

		}

	}

	g::init();int ans=0;

	for(i=1;i<=cnt;i++){

		g::add(0,i,suml[i],0);

		g::add(i,n<<1,sumd[i],0);

		ans+=suml[i];ans+=sumd[i];

	}

	for(i=1;i<=n;i++){

		for(j=0;j<e[i].size();j++){

			t1=col[i][e[i][j].first];

			t2=col[e[i][j].first][i];

			if(i<e[i][j].first) g::add(t1,t2,e[i][j].second,e[i][j].second);

		}

	}

	cout<<ans-g::dinic(0,n<<1)<<'\n';

}

巴特西

[NOI.AC省选模拟赛3.31] 附耳而至 [平面图+最小割]

题面

思路

Code

最新文章

热门文章