素材网站无水印,wordpress数据库域名表,做网站需要花钱吗,模板建站平台正题
题目链接:https://jzoj.net/senior/#main/show/3845 题目大意
美丽的仙人掌定义为#xff1a; 一个仙人掌#xff0c;第iii到jjj号点(ij)(ij)(ij)一定存在一条经过了j−i1j-i1j−i1个点的简单路径。
给出一张无向图#xff0c;选出最多的边使得它是一个…正题
题目链接:https://jzoj.net/senior/#main/show/3845 题目大意
美丽的仙人掌定义为 一个仙人掌第iii到jjj号点(ij)(ij)(ij)一定存在一条经过了j−i1j-i1j−i1个点的简单路径。
给出一张无向图选出最多的边使得它是一个美丽的仙人掌。 解题思路
首先这张图的基础是一条链贯穿1∼n1\sim n1∼n然后我们在上面加边我们发现若i∼ji\sim ji∼j之间加了边那么他们之间就不能再加边了问题转换为给出若干条线段选择出最多的使它们互不重叠。
fif_ifi表示到第iii个时的最多线段那么有fimax{fi−1,fj1(j−i)}f_imax\{f_{i-1},f_j1(j-i)\}fimax{fi−1,fj1(j−i)} codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e510;
int n,m,f[N],ans;
bool v[N];
vectorint q[N];
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);if(xy) swap(x,y);if(xy-1!v[y]) ans,v[y]1;else q[y].push_back(x);}for(int i1;in;i){f[i]f[i-1];for(int j0;jq[i].size();j)f[i]max(f[i],f[q[i][j]]1);}printf(%d,f[n]ans);
}
