3.31省选模拟

很久以后,还会是我一个人,站在风里,听着自己的心事

\(5.20k\)提交祭

\(T1\)

转化题意,恰好取出\(k\)条链,使得权值尽可能大

首先贪心的想,每次都选出来最大的即可,然后这样显然不能保证最优吧

首先选一个,肯定是要选最大的,那么我们考虑这次操作可能对下次产生影响

我们第二次选,可能需要撤销一部分第一步的操作,然后选出一条最长链

考虑正确性,我们要假设目前存在更优的选择选另一条链,那还是表示加上一个最大的权值,那么我们这么选的话,肯定能选出来

本质是就是反悔贪心吧,模拟费用流的过程

发现,我对于贪心的证明一直都不是很容易理解,或许思维过于僵化了

当然这道题可以\(wqs\)二分,至于凸性的话,还有种证明方法,如果能把模型转化为费用流形式就满足凸性

#include
#define INF 2147483647
#define MAXN 200005
using namespace std;
vectorlu[MAXN];
vector >rd[MAXN];
int dp1[MAXN],dp2[MAXN],val[MAXN],nxt1[MAXN],nxt2[MAXN];
int n,k,Ans;
void dfs_pre(int now,int fa)
{
	 for(int i=0;idp1[now])
     	 {
     	    nxt2[now]=nxt1[now];
			dp2[now]=dp1[now];
			nxt1[now]=y;
			dp1[now]=dp1[y]+val[y];
		 }
		 else if(dp1[y]+val[y]>dp2[now])
		 {
		 	nxt2[now]=y;
			dp2[now]=dp1[y]+val[y];
		 }
	 }
//	 cout<<"now: "<

#define Eternal_Battle ZXK
#include
#define mod 1000000007
#define int long long
#define MAXN 2000005
using namespace std;
const int up=259;
inline int re() {
	int x = 0, p = 1;
	char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') p = -1; ch = getchar();}
	while(ch <= '9' and ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * p;
}
int p,inv[MAXN],pw[MAXN],dw[MAXN],*C=inv,n,T;
int iv3,iv6,iv15,iv120,c1,c2;
void Init() 
{
	inv[1]=1; 
	for(int i=2;i