网站 制作 报价,做网站网站的推广是不是犯罪的,天猫代运营公司,网站建设制作鸿运通题解 最小乘积生成树#xff01; 我们把#xff0c;x的总和和y的总和作为x坐标和y左边#xff0c;画在坐标系上 我们选择两个初始点#xff0c;一个是最靠近y轴的A#xff0c;也就是x总和最小#xff0c;一个是最靠近x轴的B#xff0c;也就是y总和最小 连接两条直线 我们把x的总和和y的总和作为x坐标和y左边画在坐标系上 我们选择两个初始点一个是最靠近y轴的A也就是x总和最小一个是最靠近x轴的B也就是y总和最小 连接两条直线在这条直线上面的点都不用考虑了 我们选一个离直线最远的点C且在直线下方我们用叉积考虑这个东西也就是……面积最大我们如果用最小生成树的话只要让面积是负的就好了 推一下式子发现是\((A.y - B.y) * C.x (B.x - A.x) * C.y\)我们发现就是把边设置成\((A.y - B.y) * E[i].c (B.x - A.x) * E[i].t\)做一遍最小生成树 找到C点后递归处理A,C和C,B即可 边界是两点连线下方没有点也就是叉积大于等于0 代码 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include ctime
#include vector
#include set
//#define ivorysi
#define eps 1e-8
#define mo 974711
#define pb push_back
#define mp make_pair
#define pii pairint,int
#define fi first
#define se second
#define MAXN 10005
#define space putchar( )
#define enter putchar(\n)
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
const int64 MOD 1000000007;
templateclass T
void read(T res) {res 0;char c getchar();T f 1;while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {res res * 10 c - 0;c getchar();}res * f;
}
templateclass T
void out(T x) {if(x 0) putchar(-);if(x 10) {out(x / 10);}putchar(0 x % 10);
}
int N,M;
struct Point {int64 x,y;int64 v;Point(){};Point(int64 _x,int64 _y) {x _x;y _y;v x * y;}friend bool operator (const Point a,const Point b) {return a.v b.v || (a.v b.v a.x b.x);}
}ans;
struct Edge {int u,v;int64 c,t,w;Edge(){}Edge(int _u,int _v,int64 _c,int64 _t) {u _u;v _v;c _c;t _t;}friend bool operator (const Edge a,const Edge b) {return a.w b.w || (a.w b.w a.c b.c);}
}E[MAXN];
int fa[205];
int getfa(int u) {return fa[u] u ? u : fa[u] getfa(fa[u]);
}
Point kruskal() {sort(E 1,E M 1);Point res Point(0,0);for(int i 1 ; i N ; i) fa[i] i;for(int i 1 ; i M ; i) {if(getfa(E[i].u) ! getfa(E[i].v)) {fa[getfa(E[i].u)] getfa(E[i].v);res.x E[i].c;res.y E[i].t;}}res.v res.x * res.y;if(res ans) ans res;return res;
}
void Work(Point A,Point B) {for(int i 1 ; i M ; i) {E[i].w (A.y - B.y) * E[i].c (B.x - A.x) * E[i].t;}Point r kruskal();if((A.x - r.x) * (B.y - r.y) - (A.y - r.y) * (B.x - r.x) 0) return;Work(A,r);Work(r,B);
}
void Solve() {read(N);read(M);int u,v;int64 c,t;for(int i 1 ; i M ; i) {read(u);read(v);read(c);read(t);u;v;E[i] Edge(u,v,c,t);}ans.v 1e18;for(int i 1 ; i M ; i) {E[i].w E[i].c;}Point A kruskal();for(int i 1 ; i M ; i) {E[i].w E[i].t;}Point B kruskal();Work(A,B);printf(%lld %lld\n,ans.x,ans.y);
}
int main() {
#ifdef ivorysifreopen(f1.in,r,stdin);
#endifSolve();return 0;
} 转载于:https://www.cnblogs.com/ivorysi/p/9071158.html
