2395: [Balkan 2011]Timeismoney
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 304 Solved: 169 [Submit][Status][Discuss] Description
有n个城市(编号从0..n-1),m条公路(双向的),从中选择n-1条边,使得任意的两个城市能够连通,一条边需要的c的费用和t的时间,定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和,你的任务是求一个方案使得v最小
Input
第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c Output
【output】timeismoney.out 仅一行两个整数sumc,sumt,(sumc表示使得v最小时的费用和,sumc表示最小的时间和) 如果存在多个解使得sumc*sumt相等,输出sumc最小的 Sample Input
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
Sample Output
279 501
HINT
【数据规模】
1<=N<=200
1<=m<=10000
0<=a,b<=n-1
0<=t,c<=255
有5%的数据m=n-1
有40%的数据有t=c
对于100%的数据如上所述
最小乘积生成树模板题。
最小乘积生成树: 每条边有两个权值最小的生成树是最小乘积生成树。
我们把最接近坐标轴。
因此我们需要求出所有这些点构成的凸包的左下部分,从中找一个最大的。
怎么求凸包的左下部分呢? 用分治法。
1.首先分别求出(靠近原点一侧);
2.然后递归下去分别求离最远的点。。。
3.最后整个左下凸包上的点就都求出来了。
如何求离线段点呢?
离最大,用叉积算面积,,即让最小:
有关的量,是常数;
我们要让前面那一部分最小,那么把所有边权赋值为,然后求最小生成树就把点求出来了~
边界就是。
using namespace std;int n,m,f[205];struct edge{int x,y,t,c;LL v;}e[100005];struct Point{LL x,y;}ans,A,B;bool cmp(edge a,edge b){return a.v<b.v;}int Getfather(int x){return f[x]==x?x:f[x]=Getfather(f[x]);}Point Kruscal(){Point p=(Point){0,0};sort(e+1,e+1+m,cmp);for (int i=1;i<=n;i++)f[i]=i;int now=1;for (int i=1;i<=m;i++){int fx=Getfather(e[i].x),fy=Getfather(e[i].y);if (fx==fy) continue;p.x+=e[i].c,p.y+=e[i].t;f[fx]=fy;now++;if (now==n) break;}if ((ans.x*ans.y==p.x*p.y&&p.x<ans.x)||ans.x*ans.y>p.x*p.y)ans=p;return p;}LL Cross(Point a,Point b,Point c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}void Solve(Point a,Point b){LL y=a.y-b.y,x=b.x-a.x;for (int i=1;i<=m;i++)e[i].v=1LL*e[i].c*y+1LL*e[i].t*x;Point p=Kruscal();if (Cross(p,a,b)>=0) return;Solve(a,p);Solve(p,b);}int main(){ans.x=1e9,ans.y=1e9;scanf(“%d%d”,&n,&m);for (int i=1;i<=m;i++)scanf(“%d%d%d%d”,&e[i].x,&e[i].y,&e[i].c,&e[i].t),e[i].x++,e[i].y++,e[i].v=e[i].c;A=Kruscal();for (int i=1;i<=m;i++)e[i].v=e[i].t;B=Kruscal();Solve(A,B);printf(“%lld %lld\n”,ans.x,ans.y);return 0;}
如果你曾歌颂黎明,那么也请你拥抱黑夜