好的做网站的公司/网站推广seo方法

题目链接

引用链接

题目大意

给出一个图，图中有n个点，m条边，图中每条边非黑即白。要求：求这张图的最小生成树，且满足刚好有k条白边。

题目思路

我最开始是这么想的：不是要满足白边条数吗？我先把白边给连到目标个数 k ，之后再连黑边。我用的 kruskal算法，

我想sort 之后一定满足连的白边最短，黑边最短，加起来肯定就是最优解。然后我被狠狠地打脸了，为什么这样不行？

我们来看看这张图。

如果你和我最开始思路一样，先选白边，那么权值为 1,2,4,9,10的边会被先选走，最后选黑边就不得不选 99 。

这样选无疑没有白边选 1,2,4,10,12，黑边选 5 来的小。所以刚刚那个解法是个错解。

正解

你说有白边的限制？？我先不去管它就行了。

用kruskal跑过一遍之后，我们确实得到了一个最小生成树。只不过，这个最小生成树可能不满足白边要求。

我们用一个计数器，记录我们跑kruskal时选中的白边条数wg。

那么我们将会面临两种情况：

Ⅰ、k > wg ，这个时候说明白边选少了。

Ⅱ、k < wg ， 恰恰相反，这个时候说明白边选多了。

对于情况Ⅰ，选少了必然是因为白边权值整体过大引起的，导致一部分黑边排在了前面，抢占了白边的位置。

而对于情况Ⅱ，选多了必然是因为白边权值整体过小引起的，导致一部分过多的白边涌进了数组前方而被选中。

怎么处理这两种情况？

如果白边整体权值太小，我们就把所有白边的权值加上一个正值，让整体权值变大。

反之，白边整体权值过大，我们就把所有白边的权值加上一个负值。让整体权值变小。

我们把加上的这个值暂叫做偏移量，用mid表示。

显然就是需要二分处理

易错警示

1：每跑一次最小生成树都需要初始化一次fa[ ]数组

2：由于我们每次都会给所有白边加上mid，所以在跑完kruskal后要把所有白边恢复原状。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,ans,fa[50010],cnt,cas,sum;
struct stu
{int l,r,len,num;
}e[100001];
void init()//初始化
{for(int i=0;i<n;i++)//注意要从0开始{fa[i]=i;}
}
bool cmp(struct stu a,struct stu b)//按权值排序，权值相等则a在前面
{if(a.len!=b.len)return a.len<b.len;return a.num<b.num;
}
int findd(int x)//找祖宗函数
{if(x==fa[x])return x;return fa[x]=findd(fa[x]);
}
bool kus(int x)//最小生成树
{cnt=0,sum=0;for(int i=1;i<=m;i++)//给电信公司电缆增加权值{if(e[i].num==0){e[i].len=e[i].len+x;}}sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){int x=findd(e[i].l);int y=findd(e[i].r);if(x!=y){sum=sum+e[i].len;fa[x]=y;if(e[i].num==0){cnt++;}}}for(int i=1;i<=m;i++)//恢复原貌{if(e[i].num==0){e[i].len=e[i].len-x;}}return cnt>=k;
}
int main()
{while(scanf("%d%d%d",&n,&m,&k)!=-1){for(int i=1;i<=m;i++){scanf("%d%d%d%d",&e[i].l,&e[i].r,&e[i].len,&e[i].num);}int l=-100,r=100;//二分while(l<=r){init();//每一次都要初始化int mid=(l+r)/2;if(kus(mid))//已经有至少k条边,则可以增大权值{l=mid+1;ans=sum-k*mid;}else{r=mid-1;}}printf("Case %d: %d\n",++cas,ans);}return 0;
}