展示型网站与营销型网站区别,哪几个做内贸的网站比较好一点,不收费的小说网站排名,node.js 网站开发 公司 广州Description 给你一个无向带权连通图#xff0c;每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。Input 第一行V,E,need分别表示点数#xff0c;边数和需要的白色边数。接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)#xff0c;…Description 给你一个无向带权连通图每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Input 第一行V,E,need分别表示点数边数和需要的白色边数。 接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)边权颜色(0白色1黑色)。 Output 一行表示所求生成树的边权和。 Sample Input 2 2 1 0 1 1 1 0 1 2 0 Sample Output 2 Hint V50000,E100000,所有数据边权为[1,100]中的正整数。 题解 二分$kruskal$ 如果直接$kruskal$求最小生成树,是无法保证白边数量的,那么我们考虑如果改变白边的数量。我们可以把白边全部都加上一个权值,也就是我们二分的值,然后跑最小生成树,同时记录白边数量。当白边数量$need$时,$lmid1$,否则$rmid−1$,更新答案就是这棵生成树的权值和减去所有白边的增量。 证明:我们发现,如果我们给白边增加权值,做最小生成树,由于白边权值增大,导致不容易选白边。记$f(x)$为给白边增加$x$($x$可为负)权值,做最小生成树后,选白边的数量。可以发现,$f(x)$随$x$增大而减小,显然可以二分。其次,我们发现,由于黑边的权值是不变的,与白边权值不相互影响。同样由于白边之间关系相对不变,必然选出的$need$条白边一定是符合题意的。 1 #includemap2 #includectime3 #includecmath4 #includequeue5 #includestack6 #includecstdio7 #includestring8 #includevector9 #includecstring
10 #includecstdlib
11 #includeiostream
12 #includealgorithm
13 #define LL long long
14 #define RE register
15 #define IL inline
16 using namespace std;
17 const int V50000;
18 const int E100000;
19
20 int mid;
21 int v,e,need,ans,cnt,tmp;
22 struct tt
23 {
24 int u,v,c,col;
25 }edge[E5];
26
27 IL int Kruskal();
28 bool comp(const tt a,const tt b) {return a.c(a.col^1)*midb.c(b.col^1)*mid;}
29
30 int set[V5];
31 IL int find(int r) {return set[r]!-1 ? set[r]find(set[r]):r;}
32
33 int main()
34 {
35 scanf(%d%d%d,v,e,need);
36 for (RE int i1;ie;i) scanf(%d%d%d%d,edge[i].u,edge[i].v,edge[i].c,edge[i].col);
37 int l-100,r100;
38 while (lr)
39 {
40 mid(lr)1;
41 if (Kruskal()need) lmid1,anstmp;
42 else rmid-1;
43 }
44 printf(%d\n,ans);
45 return 0;
46 }
47
48 IL int Kruskal()
49 {
50 tmpcnt0;
51 int k0;
52 memset(set,-1,sizeof(set));
53 sort(edge1,edge1e,comp);
54 for (RE int i1;ie;i)
55 {
56 int qfind(edge[i].u);
57 int pfind(edge[i].v);
58 if (p!q)
59 {
60 kedge[i].col^1;
61 set[q]p;
62 cnt;
63 tmpedge[i].c;
64 if (cntv-1) break;
65 }
66 }
67 return k;
68 } BZOJ能过的解法 感谢Hzoi_Maple 由于$COGS$数据会有不满足恰好$need$条白边的情况 打个比方有这样的数据加$0$时大于$need$加$1$就小于$need$了。 这样应该在跑最小生成树的时候把所有的白边都加上加的那个权值结果就是最小生成树的权值和减去$need*$加上的权值多出来的那一部分完全可以当做黑边来看因为数据是$100000$的这样就可以了。来自Hzoi_Maple 排序的时候如果边权相同要把白边放在前面。 要计算当前至多能取多少白边当然要把白边放前面。由于保证有解在$cntneed$且$cnt$取最小值的方案下一定能有黑边把多余的白边代替掉。 1 #includemap2 #includectime3 #includecmath4 #includequeue5 #includestack6 #includecstdio7 #includestring8 #includevector9 #includecstring
10 #includecstdlib
11 #includeiostream
12 #includealgorithm
13 #define LL long long
14 #define RE register
15 #define IL inline
16 using namespace std;
17 const int V50000;
18 const int E100000;
19
20 int mid;
21 int v,e,need,ans,cnt,tmp;
22 struct tt
23 {
24 int u,v,c,col,rc;
25 }edge[E5];
26
27 IL int Kruskal();
28 IL void change();
29 bool comp(const tt a,const tt b) {return a.rcb.rc ? a.colb.col:a.rcb.rc;}
30
31 int set[V5];
32 IL int find(int r) {return set[r]!-1 ? set[r]find(set[r]):r;}
33
34 int main()
35 {
36 scanf(%d%d%d,v,e,need);
37 for (RE int i1;ie;i) scanf(%d%d%d%d,edge[i].u,edge[i].v,edge[i].c,edge[i].col);
38 int l-100,r100;
39 while (lr)
40 {
41 mid(lr)1;
42 if (Kruskal()need) lmid1,anstmp-need*mid;
43 else rmid-1;
44 }
45 printf(%d\n,ans);
46 return 0;
47 }
48
49 IL void change()
50 {
51 for (RE int i1;ie;i) edge[i].rcedge[i].c(edge[i].col^1)*mid;
52 }
53 IL int Kruskal()
54 {
55 change();
56 tmpcnt0;
57 int k0;
58 memset(set,-1,sizeof(set));
59 sort(edge1,edge1e,comp);
60 for (RE int i1;ie;i)
61 {
62 int qfind(edge[i].u);
63 int pfind(edge[i].v);
64 if (p!q)
65 {
66 kedge[i].col^1;
67 set[q]p;
68 cnt;
69 tmpedge[i].rc;
70 if (cntv-1) break;
71 }
72 }
73 return k;
74 } COGS能过的解法 转载于:https://www.cnblogs.com/NaVi-Awson/p/7252243.html
