滕州 网站 建设,网站建设费用如何入账,旅游网址大全,手表网站海马300米潜水表P2619 [国家集训队2]Tree I 链接 分析#xff1a; 为了确定白边选入的数量#xff0c;所以给白边加一个权值#xff0c;二分这个值#xff0c;然后最小生成树。可以发现白边的数量虽这个值的增大而减小#xff0c;满足单调性。 有一个问题#xff1a;如果在二分过程中给白… P2619 [国家集训队2]Tree I 链接 分析 为了确定白边选入的数量所以给白边加一个权值二分这个值然后最小生成树。可以发现白边的数量虽这个值的增大而减小满足单调性。 有一个问题如果在二分过程中给白边加上mid,白边数比need多加mid1白边数need少。即存在很多相等的白边 和 很多相等的黑边。 如果白边大于need一定是不合法的解之后当加到一个数使这些白边和黑边相等时就可以随意的替换了也使解变得合法了。所以二分的过程ans是可以增大的所以56行要是ans-k*x不能是ans-cntwhite*x 上述情况的样例 4 5 2 0 1 3 0 0 1 4 1 1 2 3 0 1 2 3 1 2 3 3 0 代码 1 #includecstdio2 #includealgorithm3 #includecstring4 #includecmath5 #includeiostream6 #includecctype7 8 using namespace std;9
10 const int N 50100;
11
12 struct Edge{
13 int u,v,w,c;
14 bool operator (const Edge a) const {
15 if (w a.w) return c a.c;
16 return w a.w;
17 }
18 }e[200100];
19 int fa[N];
20 int n,m,k,Ans 0;
21
22 inline char nc() {
23 static char buf[100000],*p1 buf,*p2 buf;
24 return p1p2(p2(p1buf)fread(buf,1,100000,stdin),p1p2)?EOF:*p1;
25 }
26 inline int read() {
27 int x 0,f 1;char ch nc();
28 for (; !isdigit(ch); chnc()) if(ch-) f-1;
29 for (; isdigit(ch); chnc()) xx*10ch-0;
30 return x * f;
31 }
32 int find(int x) {
33 if (x fa[x]) return x;
34 return fa[x] find(fa[x]);
35 }
36 bool check(int x) {
37 for (int i1; im; i) {
38 if (e[i].c 0) e[i].w x;
39 }
40 sort(e1,em1);
41 for (int i1; in; i) fa[i] i;
42 int cnt 0,cntwhite 0,ans 0;
43 for (int i1; im; i) {
44 int fu find(e[i].u),fv find(e[i].v);
45 if (fu fv) continue;
46 fa[fv] fu;
47 ans e[i].w;
48 cnt ;
49 if (e[i].c 0) cntwhite ;
50 if (cnt n-1) break;
51 }
52 for (int i1; im; i) {
53 if (e[i].c 0) e[i].w - x;
54 }
55 if (cntwhite k) return false;
56 ans - x * k;
57 Ans ans;
58 return true;
59 }
60 int main () {
61 n read(),m read(),k read();
62 for (int i1; im; i) {
63 e[i].u read() 1,e[i].v read() 1,e[i].w read(),e[i].c read();
64 }
65 int L -101,R 101;
66 while (L R) {
67 int mid (L R) / 2;
68 if (check(mid)) L mid 1;
69 else R mid - 1;
70 }
71 cout Ans;
72 return 0;
73 } 转载于:https://www.cnblogs.com/mjtcn/p/9096349.html
