个人网站如何制作教程,洒长春菩网站建设,如何免费做视频二维码永久,东风多利卡道路清障车做网站所谓wqs#xff0c;就是windwhisper说#xff1a;“qs” #xff08;逃#xff09;
解析
很神奇的科技。 四两拨千斤的解决一些本来可能不太好解决的问题。 经典模型#xff1a;有若干个物品#xff0c;要求选出 mmm 个#xff0c;选的时候带有限制#xff0c;求最优… 所谓wqs就是windwhisper说“qs” 逃
解析
很神奇的科技。 四两拨千斤的解决一些本来可能不太好解决的问题。 经典模型有若干个物品要求选出 mmm 个选的时候带有限制求最优的方案。 这个正常 dp 常常需要加一维记录个数复杂度 O(n2)O(n^2)O(n2) 难以通过。 设 f(x)f(x)f(x) 表示选 xxx 个元素的最优答案那么 wqs 二分使用的前提是 f(x)f(x)f(x) 具有凸性。 换句话说所有的点 (i,f(i))(i,f(i))(i,f(i)) 共同形成一个凸包。
以下以上凸包为例下凸包同理 考虑对这个凸包做一条斜率为 kkk 的切线切于点 (x,f(x))(x,f(x))(x,f(x))。 如何找到这条切线呢 注意到切线在 yyy 轴上的截距必然是最大的。 设截距 Df(x)−kxDf(x)-kxDf(x)−kx我们就使要对于所有 xxx求出 DDD 的最大值。 注意到 −kx-kx−kx 这一项那么我们只需要把每个物品的价值减去 kkk然后直接求最大值即可。 如果这个切点不在我们需要的 mmm 处由于这个切点横坐标是随 kkk 单调的所以我们可以二分寻找直到可以切到 mmm 的 kkk 为止。 找到正确的 kkk求出对应的 DDD 后f(x)f(x)f(x) 就等于 DkxDkxDkx也就不难得到了。
一些细节 切点很坐标关于 kkk 的函数并不是连续的因此可能需要最后一步强制选 mmm 个来算出答案对应的我们也最好把恰好取 mmm 个的情况归到大于 mmm 个的那边。如果我们把相等的情况归于大于那么在物品权值相等的时候我们就需要把特殊物品优先这样如果我们强制抛弃才不会出现选不够 mmm 个的情况。 例题 给出一张图求出在满足 111 的度数恰好为 mmm 的情况下的最小生成树。 显然最小生成树权值关于 111 的度数是一个凸函数。 那么我们就二分一个 kkk令所有和 111 相连的边权值减去 kkk跑一边最小生成树看 111 的度数和 mmm 大小关系即可。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N1e6100;
const int M1e6100;
const int mod1e9;int n,m,s,k;struct edge{int x,y,w,op,id;
}e[N];
bool cmp(edge x,edge y){if(x.w!y.w) return x.wy.w;else return x.opy.op;
}
int fa[N];
int find(int x){return xfa[x]?x:fa[x]find(fa[x]);
}
ll ans;
int q[N],num;
int check(int val,int op0){ans0;//printf(\nval%d op%d\n,val,op);for(int i1;im;i){e[i].op?e[i].wval:0;}for(int i1;in;i) fa[i]i;sort(e1,e1m,cmp);int on,d0;for(int i1;o1im;i){int xfind(e[i].x),yfind(e[i].y);//printf((%d %d) val%d\n,e[i].x,e[i].y,e[i].w);if(xy) continue;if(opdke[i].op) continue;//printf( ok\n);--o;de[i].op;fa[x]y;anse[i].w;if(op) q[num]e[i].id; }ans-d*val;if(o1){printf(-1\n);exit(0);}for(int i1;im;i){e[i].op?e[i].w-val:0;}return d;
}signed main(){#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);#endifnread();mread();s1;kread();for(int i1;im;i){int xread(),yread(),wread();e[i](edge){x,y,w,xs||ys,i};}int st-4e4,ed4e4;while(sted){int mid(sted1)1,numcheck(mid);if(numk) stmid;else edmid-1;//printf(mid%d num%d\n,mid,num);}if(st-4e4) printf(-1\n);else{int nmcheck(st,1);//printf(st%d num%d\n,st,num);printf(%d\n,num);for(int i1;inum;i) printf(%d ,q[i]);}return 0;
}
/*
5 6 1 3
1 2 2
1 4 5
1 5 5
1 3 2
3 5 4
2 4 4
*/
