codeforce 605B. Lazy Student-白红宇

codeforce 605B. Lazy Student

阅读量：4606 次

发布时间：2019-06-09

本文共 1100 字，大约阅读时间需要 3 分钟。

题意：n点，m条边。m条边里面标记为1的最小生成树的边，0为非最小生成树的边。给了每条边的权，如果能构成一个最小生成树则输出图，否则-1。

思路：先按权值小，为生成数边的顺序排序。（根据kruskal）再添加每条0边。这里假定（1，3），（2，4）构成环。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 #include
                 
                  13 using namespace std;14 #define CL(x,v); memset(x,v,sizeof(x));15 #define INF 0x3f3f3f3f16 #define LL long long17 const int SIGMA_SIZE = 26;18 const int MAXNODE = 111000;19 const int MAXS = 150 + 10;20 21 int n,m;22 struct node23 {24 int u,v,o;25 bool operator <(const node &b)const26 {27 if(u==b.u)28 return v>b.v;29 return u
                  
                   e)48 return 0;49 b[a[i].o]=x;50 c[a[i].o]=y;51 if(--x==0)52 {53 y+=1;54 x=y-2;55 }56 }57 }58 return 1;59 }60 int main()61 {62 scanf("%d%d",&n,&m);63 for(int i=1; i<=m; i++)64 {65 scanf("%d%d",&a[i].u,&a[i].v);66 a[i].o=i;67 }68 sort(a+1,a+1+m);69 if(fun())70 {71 for(int i=1; i<=m; i++)72 {73 cout<
                   
                    <<" "<
                    
                     <

View Code

转载于:https://www.cnblogs.com/ITUPC/p/5040992.html

你可能感兴趣的文章