wordpress搭建付费网站,国外设计工作室,追波设计网站,如何修改网站源文件题目意思#xff1a;给出n个点#xff0c;m条边#xff0c;边分为两种#xff0c;一种是A公司的#xff0c;一种是B公司的。边上有权值#xff0c; 问用n-1条边把n个点连起来的最小费用是多少#xff0c;其中A公司的边刚好有k条。题目保证有解。 题解#xff1a;题目意…题目意思给出n个点m条边边分为两种一种是A公司的一种是B公司的。边上有权值 问用n-1条边把n个点连起来的最小费用是多少其中A公司的边刚好有k条。题目保证有解。 题解题目意思很简单就是求MST且A公司要有且仅有k条边在树中刚开始做的时候用贪心的方式求 最小生成树结果WA后来看了下别人的题解二分出一个最大值delta使得A公司的边加上这个值后再 求MST时A公司的边有大于等于k条然后答案就是cost of MST - k * delta。思想就是用一个delta去 逼近答案。当delta越大的时候A公司的边就越少反之越多。所以二分delta可以找到使得A公司刚好取K条边的要求。 #include iostream
#include cstdio
#include algorithm
using namespace std;
struct node
{int u,v,cost;bool operator (node a)const{return cost a.cost;}
}arr[2][100005];
int father[100005];
int n,m,k,num[2],mincost;
int find(int x){if( x ! father[x])return father[x] find(father[x]);return father[x];
}
int union_set(int x,int y){x find(x);y find(y);if( x ! y){father[x] y;return 1;}return 0;
}
bool check(int delta){int tel k,Union n-k-1;int nn n,i,j;mincost 0;for( i 0; i n; i)father[i] i;i j 0;while( nn 1 ){if( j num[1] ( i num[0] || arr[0][i].cost delta arr[1][j].cost)){if( union_set(arr[1][j].u,arr[1][j].v ) ){mincost arr[1][j].cost;nn--;Union--;}j;}else{if( union_set(arr[0][i].u,arr[0][i].v ) ){mincost arr[0][i].cost delta;nn--;tel --;}i;}}return tel 0;
}
int main(){struct node tmp;int cas 1;int u,v,cost,x;int l,r,mid,m;freopen(in.txt,r,stdin);while( ~scanf(%d%d%d,n,m,k)){num[0] num[1] r 0;for(int i 0; i m; i){father[i] i;scanf(%d%d%d%d,tmp.u,tmp.v,tmp.cost,x);arr[x][num[x]] tmp;}for( int i 0; i 2; i)sort(arr[i],arr[i]num[i]);l -110,r 110;int res;while( l r){mid (lr)1;if( check(mid) ){res mincost;m mid;l mid 1;}else r mid - 1;}printf(Case %d: %d\n,cas,res - m*k);}
}转载于:https://www.cnblogs.com/LUO257316/p/3221701.html
