题解 小P的生成树

发布时间:2022-07-05 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了题解 小P的生成树脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

传送门

完全没有思路

  • 复数的和求最值:假设已知最值复数的单位向量,那要构成这个最值向量就要使各复数在该方向向量上的投影之和最大 对于两个复数,可以求出它们在方向向量上的投影相等时的方向向量 枚举复数可以得到许多方向向量,这些向量会将单位划分成许多区间,这些区间中各复数的投影大小关系不变 于是可以在每个区间中随便选一个单位向量,取每个向量的投影长正常求最值,最后对每个区间的结果求最值即可
  • 对于生成树:生成树的形态只与各边边权的相对大小有关,而与具体权值无关(即只需要能将边排序)

对于这题,对每个区间跑个最大生成树就好

Code:
#include <bITs/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define reg register int
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, m;
struct Edge{int From, to, a, b; double val;}e[N];

namespace force{
	bool vis[15];
	void solve() {
		int lim=1<<;m;
		double ans=0;
		for (int s=1,s2,cnt; s<lim; ++s) {
			s2=s; cnt=0;
			ll suma=0, sumb=0;
			double sum=0;
			do {++cnt; s2&amp;=s2-1;} while (s2);
			if (cnt!=n-1) goto jump;
			for (int i=1; i<=n; ++i) vis[i]=0;
			for (int i=0; i<m; ++i) if (s&(1<<i)) {
				vis[e[i+1].from]=vis[e[i+1].to]=1;
				suma+=e[i+1].a, sumb+=e[i+1].b;
			}
			sum=sqrt(suma*suma+sumb*sumb);
			if (sum<ans) goto jump;
			for (int i=1; i<=n; ++i) if (!vis[i]) goto jump;
			// cout<<"sum: "<<sum<<' '<<bitset<10>(s)<<endl;
			ans=sum;
			jump: ;
		}
		PRintf("%.6lfn", ans);
		exit(0);
	}
}

namespace task1{
	int fa[N], ans;
	inline int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}
	void solve() {
		int sum=0;
		for (int i=1; i<=n; ++i) fa[i]=i;
		sort(e+1, e+m+1, [](edge a, edge b){return a.a>b.a;});
		int tot=0;
		for (int i=1; i<=m&&tot<n-1; ++i) {
			int F1=find(e[i].from), f2=find(e[i].to);
			if (f1!=f2) {
				fa[f1]=f2;
				sum+=e[i].a;
				++tot;
			}
		}
		ans=abs(sum);
		sum=0;
		for (int i=1; i<=n; ++i) fa[i]=i;
		sort(e+1, e+m+1, [](edge a, edge b){return a.a<b.a;});
		tot=0;
		for (int i=1; i<=m&&tot<n-1; ++i) {
			int f1=find(e[i].from), f2=find(e[i].to);
			if (f1!=f2) {
				fa[f1]=f2;
				sum+=e[i].a;
				++tot;
			}
		}
		ans=max(ans, abs(sum));
		double tem=ans;
		printf("%.6lfn", tem);
		exit(0);
	}
}

namespace task{
	int fa[N], top;
	const double pi=acos(-1.0);
	double alpha[N];
	inline double calc(double x1, double x2, double y1, double y2) {return (x1-x2)/(y2-y1);}
	inline int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}
	double kruskal(double base) {
		for (int i=1; i<=n; ++i) fa[i]=i;
		for (int i=1; i<=m; ++i) e[i].val=e[i].a*cos(base)+e[i].b*sin(base);
		sort(e+1, e+m+1, [](edge a, edge b){return a.val>b.val;});
		int tot=0; ll suma=0, sumb=0;
		for (int i=1; i<=m&&tot<n-1; ++i) {
			int f1=find(e[i].from), f2=find(e[i].to);
			if (f1!=f2) {
				fa[f1]=f2;
				suma+=e[i].a, sumb+=e[i].b;
				++tot;
			}
		}
		// cout<<"sum: "<<suma<<' '<<sumb<<endl;
		return sqrt(suma*suma+sumb*sumb);
	}
	void solve() {
		alpha[++top]=90; alpha[++top]=270;
		for (int i=1; i<=m; ++i)
			for (int j=i+1; j<=m; ++j) if (e[i].a!=e[j].a && e[i].b!=e[j].b) {
				double t=atan2(e[i].a-e[j].a, e[i].b-e[j].b);
				// cout<<"t: "<<t<<endl;
				alpha[++top]=t; alpha[++top]=(t+pi);
			}
		sort(alpha+1, alpha+top+1);
		double ans=0;
		for (int i=2; i<=top; ++i) ans=max(ans, kruskal((alpha[i-1]+alpha[i])/2));
		ans=max(ans, kruskal(0));
		printf("%.6lfn", ans);
		exit(0);
	}
}

signed main()
{
	freoPEn("mst.in", "r", stdin);
	freopen("mst.out", "w", stdout);

	n=read(); m=read();
	bool itgt=1;
	for (int i=1,u,v,a,b; i<=m; ++i) {
		u=read(); v=read(); a=read(); b=read();
		e[i].from=u; e[i].to=v; e[i].a=a; e[i].b=b;
		if (b) itgt=0;
	}
	// if (itgt) task1::solve();
	// else force::solve();
	task::solve();

	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的题解 小P的生成树全部内容,希望文章能够帮你解决题解 小P的生成树所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。