中石油 1380 森林扩张-白红宇

中石油 1380 森林扩张

阅读量：5342 次

发布时间：2019-06-15

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

森林扩张

时间限制: 1 Sec

内存限制: 256 MB

提交: 124

解决: 22

[ ][ ][ ]

题目描述

小L走进了一片森林。这片森林由n个点和m条边组成，每个点都有一个大小ai。小L不小心在森林里迷路了，于是TA决定给森林添上几条边，把整片森林连成一棵树，就能走出去了，在点i与点j间连一条边需要花费ai+aj的代价。此外，小L还发现每个点上最多只能添一条边。小L想知道能不能走出森林，如果能的话，最小代价是多少。

输入

第一行两个整数n和m，表示森林的点数与边数。接下来一行，n个以空格分隔的整数，表示每个点的大小。接下来m行，每行两个正整数，描述森林的一条边。保证给出的图是一片森林。

输出

假如不能把森林变成一棵树，输出−1，否则输出最小代价。

样例输入

5 2

1 2 5 3 4

1 3

2 4

样例输出

提示

在点1与点2间加入一条边，点4与点5间加入一条边，总代价是1 + 2 + 3 + 4 = 10。

对于30%的数据，所有点的点权都相同；

对于100%的数据，0 ≤ m < n ≤ 105, 0 ≤ ai ≤ 109，保证给出的图是一片森林（可能是一棵完整的树）。

题解如下：

所有点的点权都相同。问题退化为询问可行性。注意到我们需要加恰好n−1−m条边，就需要2∗(n−1−m)个点，假如点数不够，那么一定不行。否则呢？考虑把所有度大于1的点连成一条链，然后把度为1的点挂上去，只要叶子数量小于剩下的点度之和就行了，我们发现保证上面的条件之后这个条件也是满足的，于是一定可行。 O(n)

由上面的判定条件，只要每个连通块都选至少一个点，剩下的点不管怎么选都能构成一棵树。排序贪心即可。 O(nlogn)

就是每一个联通块都要选出一个点来跟其它点对接，这个点一定是联通块内权值最小的点，若联通块的个数是k个，则还需要连接k-2个点，然后找到剩下的k-2小的点，最后相加就ok。-1的情况就是n<2*(n-m-1)。

代码实现：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #define ll long long#define mset(a,x) memset(a,x,sizeof(a))using namespace std;const double PI=acos(-1);const int inf=0x3f3f3f3f;const double esp=1e-6;const int maxn=1e6+5;const int mod=1e9+7;int dir[4][2]={0,1,1,0,0,-1,-1,0};ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}ll lcm(ll a,ll b){return a/gcd(a,b)*b;}ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}ll Fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n;n=n*n;}return r;}ll upd(ll x,ll v){x=x+v>=mod?x+v-mod:x+v;return x;}int n,m;int a[maxn],pre[maxn];vector 
                
                  p[maxn];int find(int x){ if(pre[x]==x) return pre[x]; return pre[x]=find(pre[x]);}void join(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) { pre[fx]=fy; }}int main(){ int i,j,k,x,y,z; while(~scanf("%d%d",&n,&m)) { for(i=0;i<=n;i++) pre[i]=i,p[i].clear(); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=0;i

转载于:https://www.cnblogs.com/buzaijian/p/8849169.html

你可能感兴趣的文章