2019 HL SC day1

　　今天讲的是图论大体上分为：有向图的强连通分量，有向图的完全图：竞赛图，无向图的的割点，割边，点双联通分量，变双联通分量以及圆方树 2-sat问题支配树等等。

大体上都知道是些什么东西但是仍需要写一些东西来好好巩固一下基础。太菜了加油！。

1 有向图的强联通分量写过好多次了判断条件为dfn[x]==low[x] 此时栈中的所有点形成一个强连通分量。

bzoj 最受欢迎的牛：

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=;

int n,m,len,cnt,top,num;

struct wy

{

    int x,y;

}t[MAXN];

int c[MAXN],b[MAXN],out[MAXN];

int lin[MAXN],nex[MAXN],ver[MAXN];

int s[MAXN],dfn[MAXN],low[MAXN],vis[MAXN];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline void dfs(int x)

{

    dfn[x]=low[x]=++cnt;

    s[++top]=x;vis[x]=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(!dfn[tn])

        {

            dfs(tn);

            low[x]=min(low[x],low[tn]);

        }

        else if(vis[tn])low[x]=min(low[x],dfn[tn]);

    }

    //cout<<x<<' '<<dfn[x]<<' '<<low[x]<<endl;

    if(dfn[x]==low[x])

    {

        int y;++num;

        //cout<<x<<endl;

        do

        {

            y=s[top--];

            c[y]=num;++b[num];

            vis[y]=;

        }

        while(y!=x);

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    for(int i=;i<=m;++i)

    {

        t[i].x=read();

        t[i].y=read();

        add(t[i].x,t[i].y);

    }

    for(int i=;i<=n;++i)if(!dfn[i])dfs(i);

    //cout<<num<<endl;

    for(int i=;i<=n;++i)

        for(int j=lin[i];j;j=nex[j])

        {

            int tn=ver[j];

            if(c[tn]==c[i])continue;

            ++out[c[i]];

        }

    int flag=;

    for(int i=;i<=num;++i)

    {

        if(out[i]==&&flag)

        {

            puts("");

            return ;

        }

        if(out[i]==&&flag==)flag=b[i];

    }

    printf("%d\n",flag);

    return ;

}

杀人游戏：

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=;

int n,m,len,cnt,top,num,sum,flag,len1;

int lin[MAXN],ver[MAXN],nex[MAXN],out[MAXN];

int lin1[MAXN],ver1[MAXN],nex1[MAXN];

int vis[MAXN],s[MAXN];

int dfn[MAXN],low[MAXN],b[MAXN],c[MAXN],in[MAXN];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline void add1(int x,int y)

{

    ver1[++len1]=y;

    nex1[len1]=lin1[x];

    lin1[x]=len1;

}

inline void dfs(int x)

{

    dfn[x]=low[x]=++cnt;

    s[++top]=x;vis[x]=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(!dfn[tn])

        {

            dfs(tn);

            low[x]=min(low[x],low[tn]);

        }

        else if(vis[tn])low[x]=min(low[x],dfn[tn]);

    }

    if(dfn[x]==low[x])

    {

        ++num;int y;

        do

        {

            y=s[top];--top;

            c[y]=num;++b[num];

            vis[y]=;

        }

        while(x!=y);

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    for(int i=;i<=m;++i)

    {

        int x,y;

        x=read();y=read();

        add(x,y);

    }

    for(int i=;i<=n;++i)if(!dfn[i])dfs(i);

    //cout<<num<<endl;

    for(int i=;i<=n;++i)

    {

        for(int j=lin[i];j;j=nex[j])

        {

            int tn=ver[j];

            if(c[i]==c[tn])continue;

            //cout<<c[tn]<<' '<<i<<endl;

            add1(c[i],c[tn]);

            ++in[c[tn]];++out[c[i]];

        }

    }

    for(int i=;i<=num;++i)

    {

        if(!in[i])++sum;

        if(!in[i]&&!out[i]&&b[i]==)flag=;

        if(!in[i]&&b[i]==)

        {

            int mark=;

            for(int j=lin1[i];j;j=nex1[j])

            {

                int tn=ver1[j];

                if(in[tn]==)mark=;

            }

            if(!mark)flag=;

        }

    }

    printf("%.6lf\n",(n-sum+flag)*1.0/(n*1.0));

    return ;

}

推荐一写细节非常之多。

炸弹游戏线段树优化建图+强连通分量。

线段树优化建图的话我认为是将一个点向一个区间整体连边可转换成线段树上的连边原因我们不知道哪一条边起到了连接强连通分量的作用。

所以采用线段树优化一下边数至多为 2n+nlogn.

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 5000000000000000000ll

#define l(x) t[x].l

#define r(x) t[x].r

#define mn(x) t[x].mn

#define mx(x) t[x].mx

#define ll long long

#define mod 1000000007

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=;

int n,cnt,top,root,num,len,len1,T,h,w;

ll ans,vmn[MAXN<<],vmx[MAXN<<];

int ru[MAXN<<],q[MAXN<<];

int pos[MAXN],dfn[MAXN<<],low[MAXN<<],s[MAXN<<];

int vis[MAXN<<],c[MAXN<<];

int lin[MAXN<<],ver[MAXN*],nex[MAXN*];

int lin1[MAXN<<],ver1[MAXN*],nex1[MAXN*];

ll a[MAXN],b[MAXN];

struct wy//动态开点线段树 优化建图

{

    int l,r;

    ll mn,mx;

}t[MAXN<<];

inline void add(int x,int y)

{

    ver[++len]=y;nex[len]=lin[x];lin[x]=len;

}

inline void add1(int x,int y)

{

    ver1[++len1]=y;nex1[len1]=lin1[x];lin1[x]=len1;

}

inline void tarjan(int x)

{

    dfn[x]=low[x]=++w;

    s[++top]=x;vis[x]=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(!dfn[tn])

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

        }

        else if(vis[tn])low[x]=min(low[x],dfn[tn]);

    }

    if(dfn[x]==low[x])

    {

        ++num;int y;

        vmn[num]=INF;vmx[num]=-INF;

        do

        {

            y=s[top--];

            vis[y]=;c[y]=num;

            vmn[num]=min(vmn[num],mn(y));

            vmx[num]=max(vmx[num],mx(y));

        }

        while(x!=y);

    }

}

inline void build(int &p,int l,int r)

{

    if(!p)p=++cnt;

    if(l==r)

    {

        pos[l]=p;

        mn(p)=a[l];mx(p)=a[l];

        return;

    }

    int mid=(l+r)>>;

    build(l(p),l,mid);

    build(r(p),mid+,r);

    mn(p)=min(mn(l(p)),mn(r(p)));

    mx(p)=max(mx(l(p)),mx(r(p)));

    add(p,l(p));add(p,r(p));

}

inline void change(int p,int L,int R,int l,int r,int x)

{

    if(L<=l&&R>=r)

    {

        add(x,p);

        return;

    }

    int mid=(l+r)>>;

    if(L<=mid)change(l(p),L,R,l,mid,x);

    if(R>mid)change(r(p),L,R,mid+,r,x);

}

inline void topsort()

{

    while(h++<T)

    {

        int x=q[h];

        for(int i=lin1[x];i;i=nex1[i])

        {

            int tn=ver1[i];

            --ru[tn];

            vmn[tn]=min(vmn[tn],mn(x));

            vmx[tn]=max(vmx[tn],mx(x));

            if(!ru[tn])q[++T]=tn;

        }

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();

    for(int i=;i<=n;++i)a[i]=read(),b[i]=read();

    build(root,,n);

    for(int i=;i<=n;++i)

    {

        int l=lower_bound(a+,a++n,a[i]-b[i])-a;//这个一定不会越界

        int r=upper_bound(a+,a++n,a[i]+b[i])-a-;//这个有可能会越界但是不会出错

        //cout<<l<<' '<<r<<endl;

        //cout<<pos[i]<<endl;

        change(root,l,r,,n,pos[i]);

    }

    //cout<<cnt<<endl;

    for(int i=;i<=cnt;++i)if(!dfn[i])tarjan(i);

    //printf("%d\n",num);

    //cout<<(ll)num<<endl;

    for(int i=;i<=cnt;++i)

    {

        for(int j=lin[i];j;j=nex[j])

        {

            int tn=ver[j];

            if(c[i]==c[tn])continue;

            add1(c[tn],c[i]);++ru[c[i]];

        }

    }

    for(int i=;i<=num;++i)if(!ru[i])q[++T]=c[i];

    topsort();

    for(int i=;i<=n;++i)

    {

        int l=lower_bound(a+,a++n,vmn[c[pos[i]]])-a;

        int r=upper_bound(a+,a++n,vmx[c[pos[i]]])-a-;

        ans+=(ll)(r-l+)*(ll)i%mod;

    }

    printf("%lld\n",ans%mod);

    return ;

}

割点：BLO 以前的代码。

//#include<bits/stdc++.h>

#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<ctime>

#include<queue>

#include<stack>

#include<vector>

#include<cctype>

#include<utility>

#include<algorithm>

#include<cstring>

#include<string>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<cstdlib>

#define INF 2147483646

#define ll long long

#define db double

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

inline void put(ll x)

{

    x<?putchar('-'),x=-x:;

    ll num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const ll MAXN=;

ll n,m,num;

ll ans[MAXN],dfn[MAXN],low[MAXN],cut[MAXN];

ll sz[MAXN];//s[i]表示以i为根节点的子树大小

ll lin[MAXN<<],nex[MAXN<<],ver[MAXN<<],len;

inline void add(ll x,ll y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline ll min(ll x,ll y){return x>y?y:x;}

void tarjan(ll x)

{

    dfn[x]=low[x]=++num;

    sz[x]=;ll flag=,sum=;

    for(ll i=lin[x];i;i=nex[i])

    {

        ll tn=ver[i];

        if(!dfn[tn])

        {

            tarjan(tn);

            sz[x]+=sz[tn];

            low[x]=min(low[x],low[tn]);

            if(low[tn]==dfn[x])

            {

                flag++;

                if(x!=||flag>)

                {

                    cut[x]=;sum+=sz[tn];

                    ans[x]+=sz[tn]*(n-sz[tn]-);

                }

            }

        }

        else low[x]=min(low[x],dfn[tn]);

    }

    if(cut[x])ans[x]+=(n-sum-)*sum;

    return;

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    for(ll i=;i<=m;++i)

    {

        ll x,y;

        x=read();y=read();

        add(x,y);add(y,x);

    }

    tarjan();

    for(ll i=;i<=n;++i)put(ans[i]+(n-)*);

    return ;

}

bzoj 3331 圆方树+树上差分非常简单。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 5000000000000000000ll

#define l(x) t[x].l

#define r(x) t[x].r

#define mn(x) t[x].mn

#define mx(x) t[x].mx

#define ll long long

#define mod 1000000007

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=,maxn=MAXN<<;

int n,m,k,len,top,num,cnt,T;

int dfn[MAXN],low[MAXN],s[MAXN];

int lin[maxn],ver[maxn],nex[maxn];

int f[MAXN<<][],d[MAXN<<],c[MAXN<<];

vector<int>g[MAXN];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

void tarjan(int x)

{

    low[x]=dfn[x]=++cnt;

    s[++top]=x;

    for(unsigned int i=;i<g[x].size();++i)

    {

        int tn=g[x][i];

        if(!dfn[tn])

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

            if(dfn[x]==low[tn])

            {

                ++num;

                for(int j=;j!=tn;--top)

                {

                    j=s[top];

                    add(num,j);

                    add(j,num);

                }

                add(num,x);

                add(x,num);

            }

        }

        else low[x]=min(low[x],dfn[tn]);

    }

}

inline void dfs(int x,int father)

{

    d[x]=d[father]+;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(tn==father)continue;

        f[tn][]=x;

        for(int j=;j<=T;++j)f[tn][j]=f[f[tn][j-]][j-];

        dfs(tn,x);

    }

}

inline int LCA(int x,int y)

{

    if(d[x]<d[y])swap(x,y);

    for(int i=T;i>=;--i)

        if(d[f[x][i]]>=d[y])x=f[x][i];

    if(x==y)return x;

    for(int i=T;i>=;--i)

        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

    return f[x][];

}

inline void dfs(int x)

{

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(tn==f[x][])continue;

        dfs(tn);

        c[x]+=c[tn];

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();k=read();

    for(int i=;i<=m;++i)

    {

        int x,y;

        x=read();y=read();

        g[x].push_back(y);

        g[y].push_back(x);

    }

    num=n;tarjan();

    //cout<<num<<endl;

    T=(int)(log((n+num)*1.0)/log(2.0))+;

    dfs(,);

    //for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i),--top;

    for(int i=;i<=k;++i)

    {

        int x,y;

        x=read();y=read();

        int lca=LCA(x,y);

        ++c[x];++c[y];

        --c[lca];

        if(f[lca][])--c[f[lca][]];

    }

    dfs();

    for(int i=;i<=n;++i)printf("%d\n",c[i]);

    return ;

}

luogu 4630 铁人两项

圆方树 + 特殊性质 +树形dp 想的还不是很成熟。

总之符合路径的一定是s 到 f 路径上的圆点和方点采用树形dp O(n)解决。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 1000000000

#define ll long long

#define mod 1000000007

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=,maxn=MAXN<<;

int n,m,k,len,top,num,cnt,sz;

ll ans;

int dfn[MAXN],low[MAXN],s[MAXN],w[MAXN<<];

int lin[maxn],ver[maxn],nex[maxn],b[MAXN<<];

vector<int>g[MAXN];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

void tarjan(int x)

{

    low[x]=dfn[x]=++cnt;

    s[++top]=x;++sz;

    for(unsigned int i=;i<g[x].size();++i)

    {

        int tn=g[x][i];

        if(!dfn[tn])

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

            if(dfn[x]==low[tn])

            {

                ++num;

                for(int j=;j!=tn;--top)

                {

                    j=s[top];

                    add(num,j);

                    add(j,num);

                    ++w[num];

                }

                add(num,x);

                add(x,num);

                ++w[num];

            }

        }

        else low[x]=min(low[x],dfn[tn]);

    }

}

inline void dfs(int x,int father)

{

    b[x]=x<=n;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(tn==father)continue;

        dfs(tn,x);

        ans+=2ll*w[x]*b[x]*b[tn];

        b[x]+=b[tn];

    }

    ans+=2ll*w[x]*b[x]*(sz-b[x]);

    return;

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    for(int i=;i<=n;++i)w[i]=-;

    for(int i=;i<=m;++i)

    {

        int x,y;

        x=read();y=read();

        g[x].push_back(y);

        g[y].push_back(x);

    }

    num=n;

    for(int i=;i<=n;++i)

        if(!dfn[i])

        {

            sz=;

            tarjan(i);--top;

            dfs(i,);

        }

    printf("%lld\n",ans);

    return ;

}

luogu 3225 矿场搭建
点双连通分量其实也是割点的裸题很有意思。

//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<cstring>

#include<string>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<cctype>

#include<utility>

#include<set>

#include<bitset>

#include<queue>

#include<stack>

#include<deque>

#include<map>

#include<vector>

#include<ctime>

#define INF 2147483646

#define ll long long

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

inline void put(int x)

{

    x<?putchar('-'),x=-x:;

    int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=;

int n,len,num,root,c,cnt,sum,m,w;

ll ans;

int low[MAXN],dfn[MAXN],cut[MAXN],vis[MAXN];

int lin[MAXN<<],nex[MAXN<<],ver[MAXN<<];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline int max(int x,int y){return x>y?x:y;}

inline int min(int x,int y){return x>y?y:x;}

void tarjan(int x)

{

    dfn[x]=low[x]=++num;

    int flag=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(dfn[tn]){low[x]=min(low[x],dfn[tn]);continue;}

        else

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

            if(dfn[x]==low[tn])

            {

                ++flag;

                if(flag>||x!=root)cut[x]=;

            }

        }

    }

}

void dfs(int x)

{

    vis[x]=cnt;++sum;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(cut[tn]&&vis[tn]!=cnt)

        {

            vis[tn]=cnt;

            ++c;

        }

        if(!vis[tn]&&!cut[tn])dfs(tn);

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    for(int T=;;++T)

    {

        n=read();

        if(!n)break;

        memset(cut,,sizeof(cut));

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        memset(lin,,sizeof(lin));

        memset(vis,,sizeof(vis));

        len=;num=;cnt=;ans=;m=;w=;

        for(int i=;i<=n;++i)

        {

            int x,y;

            x=read();y=read();

            m=max(m,max(x,y));

            add(x,y);add(y,x);

        }

        for(int i=;i<=m;++i)if(!dfn[i])root=i,tarjan(i);

        for(int i=;i<=m;++i)

        {

            if(vis[i]||cut[i])continue;

            ++cnt;sum=;c=;

            dfs(i);

            if(!c)ans=ans*(sum-)*sum/,w+=;

            if(c==)ans*=sum,w+=;

            if(c==);

        }

        printf("Case %d: %d %lld\n",T,w,ans);

    }

    return ;

}

bzoj 3495 2-sat模型需要前缀和优化建图很有意思。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 1000000000

#define ll long long

#define mod 1000000007

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

const int MAXN=,maxn=MAXN<<;

int n,m,k,len,cnt,top,num,flag;

int c[MAXN<<];

int lin[maxn],ver[maxn],nex[maxn];

int s[MAXN<<],dfn[MAXN<<],low[MAXN<<],vis[MAXN<<];

inline void add(int x,int y)

{

    ver[++len]=y;

    nex[len]=lin[x];

    lin[x]=len;

}

inline void tarjan(int x)

{

    dfn[x]=low[x]=++cnt;

    s[++top]=x;vis[x]=;

    for(int i=lin[x];i;i=nex[i])

    {

        int tn=ver[i];

        if(!dfn[tn])

        {

            tarjan(tn);

            low[x]=min(low[x],low[tn]);

        }

        else if(vis[tn])low[x]=min(low[x],dfn[tn]);

    }

    if(dfn[x]==low[x])

    {

        ++num;int y;

        do

        {

            y=s[top--];

            vis[y]=;c[y]=num;

        }

        while(x!=y);

    }

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();k=read();

    for(int i=;i<=m;++i)

    {

        int x,y;

        x=read();y=read();//x选 x+n不选

        add(x+n,y);add(y+n,x);

    }

    for(int i=;i<=k;++i)

    {

        int w;

        w=read();

        for(int j=;j<=w;++j)s[j]=read();

        for(int j=;j<=w;++j)add(s[j]+*n,s[j-]+*n);//前缀和

        for(int j=w-;j>=;--j)add(s[j]+*n,s[j+]+*n);//后缀和

        for(int j=;j<=w;++j)

        {

            if(j>)add(s[j],s[j-]+*n);

            if(j<w)add(s[j],s[j+]+*n);

        }

    }

    for(int i=;i<=n;++i)add(i+*n,i+n),add(i+*n,i+n);

    for(int i=;i<=*n;++i)if(!dfn[i])tarjan(i);

    for(int i=;i<=n;++i)if(c[i]==c[i+n])flag=;

    if(flag)puts("NIE");else puts("TAK");

    return ;

}

巴特西

2019 HL SC day1

最新文章

热门文章