JZOJ3845. simple question

Description

dzy has an undirected graph with n points and m edges. Cactus is a undirected graph with each edge in a simple ring at most. He wants to find the maximum number of edges in the generated cactus of the undirected graph.
But dzy thinks this problem is too simple, so he defines "beautiful cactus", that is, if there is a simple path between any two points numbered i, J (i < J) in a cactus, and there is a point with j-i+1 on it, then the cactus is beautiful.
Now he wants to know how many sides there are in the beautiful cactus in this picture. Can you help him?

Input

The first line has two integers n, M. Next, m lines have two integers UI and VI, indicating that there is an undirected edge between the two points. Make sure there are no self rings in the graph.

Output

Only one integer in a row represents the answer.

Sample Input

2 1
1 2

Sample Output

1

Data Constraint

For 10% of the data, n < = 10.
For 30% of the data, n < = 10 ^ 3.
For 100% data, n < = 10 ^ 5, m < = 2n.

Title Solution

First, consider how to satisfy the requirement that there is a simple path between any two points numbered i, J (i < J) with j-i+1 points.
Obviously, the only thing that can be satisfied is a chain, and the number of points on the chain is continuous.
Now we are going to construct the cactus with the most sides.
Two rings cannot intersect, but they can be tangent.
The problem is transformed into a line covering problem,
In a continuous chain [l,r],
There are some line segments xi,yi,l ≤ Xi < Yi ≤ r
It is required that line segments cannot be covered repeatedly. Yes, select as many lines as possible.
A simple dp is enough,
fi indicates the maximum number of edges that have been processed (not necessarily covered by line segments) in the previous i positions.

code

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 100003
#define M 103
#define db double
#define P putchar
#define G getchar
#define inf 998244353
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int nxt[N<<2],to[N<<2],lst[N],tot;
int n,m,x,y,cnt,l,r,f[N],ans;
bool p[N];
struct node
{
    int x,y;
}a[N<<2];
bool cmp(node a,node b)
{
    return a.x<b.x || (a.x==b.x  && a.y<b.y);
}

void ins(int x,int y)
{
    nxt[++tot]=lst[x];
    to[tot]=y;
    lst[x]=tot;
}

int main()
{
    read(n);read(m);
    for(int i=1;i<=m;i++)
    {
        read(x),read(y),ins(x,y),ins(y,x);
        if(x>y)swap(x,y);
        if(x+1==y)p[x]=1;
    }

    for(l=1;r<=n;l=r+1)
    {
        cnt=0;
        for(r=l;p[r];r++);
        for(int i=l;i<=r;i++)
            for(int j=lst[i];j;j=nxt[j])
                if(l<=to[j] && to[j]<=r && abs(to[j]-i)>1)a[++cnt].x=i,a[cnt].y=to[j];
        sort(a+1,a+1+cnt,cmp);
        f[a[0].x=l]=0;
        for(int i=1;i<=cnt;i++)
        {
            for(int j=a[i-1].x+1;j<=a[i].x;j++)
                f[j]=max(f[j],f[j-1]);
            f[a[i].y]=f[a[i].x]+1;
        }
        for(int i=a[cnt].x+1;i<=r;i++)
            f[i]=max(f[i],f[i-1]);
        ans=max(ans,f[r]+r-l+1);
    }

    write(ans);

    return 0;
}

Posted on Thu, 09 Apr 2020 09:29:51 -0700 by mfos