首页 > 其他分享 >AT655 玉座の間 题解

AT655 玉座の間 题解

时间:2023-02-24 13:45:06浏览次数:60  
标签:费用 一个点 int 题解 短路 流量 AT655 include 玉座

首先我们要学习一下费用流。

费用流是什么呢,可以理解为边带权值的网络流。

那么最小费用最大流,是指在满足最大流的情况下的最小费用。

那么我们就要实现这个过程。

首先对于一条有向边,建立的反向边的权值为原权值的相反数。

所以明显图带负数,只能用 SPFA,泪目

每一次跑一次 SPFA 找到最短路,当然计算最短路时没有流量的边是不能走的,期间记录流量。

如果发现汇点最短路发生了更新,那么可以从汇点出发,往回跑最短路,然后就是减去流量,对反向边增加流量的操作了。

往回跑最短路可以由每次更新一个点的最短路值时记录从哪一个点转移过来的即可。

本题也是一个费用流。

首先可以保证,在 \(y\) 轴同侧的两点不会出现一个点跑到另一个坐标轴与另外一点进行匹配的情况,这个应该很好证。

所以对于坐标轴两边的点,可能都是能匹配的,那么就可以连边,而对于每一个点,也可以连 \(y\) 轴,所以也与 \(y\) 轴连边。

综上,我们可以考虑建出这个图。

首先,将每个点复制成两份,从 \(1\) 到 \(n\),与从 \(n+1\) 到 \(2\times n\)。

第二步,将源点 \(S\) 与 \(1\) 到 \(n\) 连边,流量为 \(1\),边权为 \(0\)。

第三步,走 \(y\) 轴,可以理解为自己与自己匹配,连接 \(i\) 与 \(i+n\),流量为 \(1\),边权为 \(\left|x_i\right|\)。

第四步,连接坐标轴两边的点,当 \(x_i\times x_j<0\) 时,说明在坐标轴两端,连接 \(i\) 与 \(j+n\),流量为 \(1\),边权为 \(\sqrt{(x_i+x_j)^2+(y_i-y_j)^2}\div 2\)。因为如果要匹配会匹配两次,所以要每次除以 \(2\),而连向 \(y\) 轴只有一次,所以不需要除以 \(2\)。

第五步,连接 \(n+1\) 到 \(2\times n\) 与汇点 \(T\),流量为 \(1\),边权为 \(0\)。

最后跑最小费用最大流即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<deque>
#include<vector>
using namespace std;
const int N=205;
int n;
inline double tabs(int x)
{
	return x>0?x:-x;
}
struct node2
{
	int x,y;
}t[N];
struct node
{
	int to,v;
	double w;
};
vector<node>a[N];
vector<int>b[N];
deque<int>q;
double dis[N],ans;
bool vis[N];
int incf[N],pre[N];
bool spfa()
{
	for(int i=1;i<=2*n+3;i++)dis[i]=1e9;
	memset(vis,0,sizeof(vis));
	q.push_back(2*n+1);
	dis[2*n+1]=0;
	incf[2*n+1]=1e9;
	while(!q.empty())
	{
		int x=q.front();
		q.pop_front();
		vis[x]=0;
		int len=a[x].size();
		for(int i=0;i<len;i++)
		{
			if(!a[x][i].v)continue;
			if(dis[x]+a[x][i].w<dis[a[x][i].to])
			{
				dis[a[x][i].to]=dis[x]+a[x][i].w;
				incf[a[x][i].to]=min(incf[x],a[x][i].v);
				pre[a[x][i].to]=b[x][i];
				if(!vis[a[x][i].to])
				{
					if(!q.empty()&&dis[a[x][i].to]<dis[q.front()])q.push_front(a[x][i].to);
					else q.push_back(a[x][i].to);
					vis[a[x][i].to]=0;
				}
			}
		}
	}
	if(dis[2*n+3]<1e9-1e-9)return true;
	return false;
}
void dinic()
{
	while(spfa())
	{
		int x=2*n+3;
		ans+=dis[2*n+3]*incf[2*n+3];
		while(x!=2*n+1)
		{
			int t=pre[x];
			int p=a[x][t].to;
			a[x][t].v+=incf[2*n+3];
			a[p][b[x][t]].v-=incf[2*n+3];
			x=p;
		}
	}
}
int main()
{
	//freopen("aichemy.in","r",stdin);
	//freopen("aichemy.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&t[i].x,&t[i].y);
	for(int i=1;i<=n;i++)
	{
		a[2*n+1].push_back({i,1,0});
		a[i].push_back({2*n+1,0,0});
		b[2*n+1].push_back(a[i].size()-1);
		b[i].push_back(a[2*n+1].size()-1);
		for(int j=1;j<=n;j++)
		{
			if(t[j].x*t[i].x<0)
			{
				a[i].push_back({j+n,1,sqrt((t[i].x+t[j].x)*(t[i].x+t[j].x)+(t[i].y-t[j].y)*(t[i].y-t[j].y))/2});
				a[j+n].push_back({i,0,-sqrt((t[i].x+t[j].x)*(t[i].x+t[j].x)+(t[i].y-t[j].y)*(t[i].y-t[j].y))/2});
				b[i].push_back(a[j+n].size()-1);
				b[j+n].push_back(a[i].size()-1);
			}
		}
		a[i+n].push_back({2*n+3,1,0});
		a[2*n+3].push_back({i+n,0,0});
		b[i+n].push_back(a[2*n+3].size()-1);
		b[2*n+3].push_back(a[i+n].size()-1);
		a[i].push_back({i+n,1,tabs(t[i].x)});
		a[i+n].push_back({i,0,-tabs(t[i].x)});
		b[i].push_back(a[i+n].size()-1);
		b[i+n].push_back(a[i].size()-1);
	}
	dinic();
	printf("%.7lf",ans);
	return 0;
}
/*
3
1 2
-1 3
-2 0
*/

标签:费用,一个点,int,题解,短路,流量,AT655,include,玉座
From: https://www.cnblogs.com/gmtfff/p/at655.html

相关文章

  • P3997 [SHOI2013]扇形面积并 题解
    理解题意后可以把题目看成一个覆盖线段的问题。对于点在\(-m\)上,看成在\(m\)上。对于\(l<r\),不用处理。对于\(l>r\),将问题看成\((l,m)\)和\((-m+1.r)\)两个区......
  • P5616 [MtOI2019]恶魔之树 题解
    期望就是来搞笑的。由于有最小公倍数,所以可以想到分解质因数,对于多个数求最小公倍数,取每个质因子的最大指数,最后相乘即可。既然都知道了这个,那么就想到先统计每个数的个......
  • CF10E Greedy Change 题解
    一个非常离谱的题。首先有结论,如果有\(w\)使贪心不为最优解,那么比\(w\)小的第一个\(a_i\),用贪心法求面值为\(a_i-1\),除了最后选的一个数\(a_j\)会比原方法多选一......
  • P2161 [SHOI2009]会场预约 题解
    没事打了个Splay,然后调了3h。觉得题解的找前驱后继与删除复杂了点,主要讲一下这的思路。由于平衡树中每一个点代表的区间互不相交,所有平衡树满足\(l,r\)两个值的BST。......
  • P3224 [HNOI2012]永无乡 题解
    典型Splay练习题。开始建\(n\)个Splay,每一次建边用并查集判断是否在一个子图,不在就合并,即把一个Splay的所有点全插入到另一个Splay中,需要合并的点可以用vector存储。但......
  • P1763 埃及分数 题解
    做完后发现很多题解都是有些细节问题的,对于向上与向下取整非常混乱。第一次做迭代加深搜索的题,记录一下。所谓迭代加深搜索,就是在求搜索树的深度的问题中,枚举层数,取最优......
  • P4048 [JSOI2010]冷冻波 题解
    首先很好想到我们应该预处理出来每一个巫妖王能攻击到的精灵。那么这就是一个几何题。对于每一组精灵与巫妖王,设巫妖王坐标为\((x_1,y_1)\),精灵坐标为\((x_2,y_2)\)。......
  • P7221 [JSOI2010] 蔬菜庆典 题解
    本题解在求无解的情况下优化了下。通过分析样例,我们可以发现如果一个节点有多个Dlihc,那么这些Dlihc对应的权值必须一样,否则可以无限延伸下去。因为一号节点没有Tnera......
  • P3195 [HNOI2008]玩具装箱 题解
    首先先写dp方程非常简单\(\mathit{f}_{i}=\min(\mathit{f}_{j}+(\mathit{c}_{i}+i-j-1-L-\mathit{c}_{j})^2)\)(其中\(\mathit{c}_{i}\)表示长度前缀和)然后发现括号......
  • U259394 Gmt丶FFF 的基环树 题解
    题目链接:传送门之所以评黑,是因为实在是太难调了。(又回调了)。对于有$40%$的数据,$n\le3000$,这部分我们可以暴力删边,然后暴力求直径即可。那么对于$100%$的数据:首先......