有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小

参考：

参考说的太详细了，还配了图，读不懂的应该不存在吧，已经没什么好说的了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=250;const int M=1e4+5;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int u,v,c,t,w;}e[M];struct point{ int x,y;};int n,m,fa[N];point ans=(point){INF,INF};inline bool cmp(node a,node b){ return a.w
            
             tmp||(maxn==tmp&&ans.x>now.x))ans=now; return now;}inline point getmag(point a,point b){ point s; s.x=b.x-a.x;s.y=b.y-a.y; return s;}inline int multiX(point a,point b){ return a.x*b.y-b.x*a.y;}void work(point l,point r){ for(int i=1;i<=m;i++) e[i].w=e[i].t*(r.x-l.x)+e[i].c*(l.y-r.y); sort(e+1,e+m+1,cmp); point mid=kruscal(); if(multiX(getmag(mid,l),getmag(mid,r))>=0)return; work(l,mid);work(mid,r);}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ e[i].u=read(),e[i].v=read(); e[i].c=read(),e[i].t=read(); } for(int i=1;i<=m;i++)e[i].w=e[i].c; sort(e+1,e+m+1,cmp); point p1=kruscal(); for(int i=1;i<=m;i++)e[i].w=e[i].t; sort(e+1,e+m+1,cmp); point p2=kruscal(); work(p1,p2); printf("%d %d\n",ans.x,ans.y); return 0;}
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客： +

+++++++++++++++++++++++++++++++++++++++++++