脚本宝典收集整理的这篇文章主要介绍了题解 小P的生成树,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
传送门
完全没有思路
对于这题,对每个区间跑个最大生成树就好
#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&=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,请注明来意。