[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)

发布于 2018-05-27  150 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)

Description

在有 N 座城市的国度.Alice希望可以开始一场充满传奇的旅行。TA 希可以从一个城市出发开始旅行,每次前往一个相邻的城市,途中不重复得经过恰好 K 座城市,最后抵达另外一个城市并结束旅行。需要注意的是,起点与终点也被考虑为经过的城市,也就是说包括起点和终点在内经过的所有城市都是不能重复的。现在,Alice 希望知道哪些城市对 <u,v> 可以作为合法的旅行起点与终点。

Tag

分类讨论,容斥原理,计数

解决思路

看到\(K\)这么小,第一个想到的就是状态压缩。
可惜这道题与状态压缩并没有什么关系。看到数据这么小,于是我们可以数据分治分类讨论一下。
\(K==2\),直接就是每一条边
\(K==3\),对于合法的\(x-u-y\),我们可以枚举\(x,y\),然后扫描从\(x\)出发的每一条边,\(x->t\),看\(t\)是否与\(y\)直接右边相连。
\(K==4\),对于合法的\(x-u-v-y\),同样是枚举\(x,y\),然后分别扫描从\(x\)出发的边\(x->u\)和\(y\)出发的边\(y->v\),看\(u\)与\(v\)是否直接连通。
\(K==5\),从\(K==5\)开始,情况变得有些复杂。对于合法的路径\(x-p-u-q-y\),我们在最外层枚举\(p\)和\(q\),然后扫描\(p\)的出边看\(p->u\)能不能与\(q\)直接相连,这样我们就处理出若干\(p,u,q\)的三元组。然后我们再扫描\(p\)的出边和\(q\)的出边构造出\(x,y\)?
且住,这里我们无法保证\(x,y\)不是我们之前枚举的\(u\)啊。所以利用容斥原理,我们记对于当前的\(p,q\),\(Cnt[i]\)表示\(i\)这个点作为中间点\(u\)几次,\(sum\)记录这一次的\(Cnt[]\)之和,那么我们在枚举\(x,y\)的时候,只需要判断\(sum-Cnt[x]-Cnt[y]\)是不是大于\(0\)就可以知道是否合法了。
代码表示就是这样

for (int p=1;p<=n;p++)
    for (int q=p+1;q<=n;q++)
    {
        int sum=0;mem(Cnt,0);
        for (int i=Head[p];i!=-1;i=Next[i])
            if ((V[i]!=q)&&(Map[V[i]][q]))
                Cnt[V[i]]++,sum++;
        for (int i=Head[p];i!=-1;i=Next[i])
            if (V[i]!=q)
                for (int j=Head[q];j!=-1;j=Next[j])
                    if ((V[j]!=p)&&(V[i]!=V[j])&&(sum-Cnt[V[i]]-Cnt[V[j]]))
                        Ans[V[i]][V[j]]=Ans[V[j]][V[i]]=1;
    }

\(K==6\),类似\(K==5\)的做法,还是利用容斥。设合法路径为\(x-p-u-v-q-y\),先枚举\(p,q\)并扫描其出边得到\(u,v\),这样就得到了合法的四元组。记\(Cnt[i]\)表示点\(i\)出现在四元组中的次数,\(sum\)记总次数,然后再枚举\(p,q\)的出边得到\(x,y\)。需要注意的是,像上面那样\(Sum-Cnt[x]-Cnt[y]\)是不行的,因为可能\(x-y\)也正好是一对二元组,所以要加上\(x-y\)是否连通,即要判断的应该是\(sum-Cnt[x]-Cnt[y]+Map[x][y]\)是否大于\(0\)
代码是这样的

for (int p=1;p<=n;p++)
    for (int q=p+1;q<=n;q++)
    {
        int sum=0;mem(Cnt,0);
        for (int i=Head[p];i!=-1;i=Next[i])
            if (V[i]!=q)
                for (int j=Head[q];j!=-1;j=Next[j])
                    if ((V[j]!=p)&&(V[i]!=V[j])&&(Map[V[i]][V[j]]))
                        Cnt[V[i]]++,Cnt[V[j]]++,sum++;
        for (int i=Head[p];i!=-1;i=Next[i])
            if (V[i]!=q)
                for (int j=Head[q];j!=-1;j=Next[j])
                    if ((V[j]!=p)&&(V[i]!=V[j])&&(sum-Cnt[V[i]]-Cnt[V[j]]+Map[V[i]][V[j]])) Ans[V[i]][V[j]]=Ans[V[j]][V[i]]=1;
    }

\(K==7\),点数越来越多了。这一次直接枚举复杂度会太高。设合法路径的形态为\(x-p-u-z-v-q-y\)。我们先预处理处所有的三元组\(u-z-v\),记为\(Node[u][v]\)的元素,然后同样还是枚举\(p,q\),再枚举其出边找到\(u,v\),由于我们已经预处理好了所有的三元组,所以我们可以直接得到\(z=Node[u][v]\),然后依然\(sum\)记录三元组数量,\(Cnt[i]\)记录\(i\)出现的次数。但这还要记录两个值,因为若像上面那样减的话,会多减去\(x,y\)作为三元组两端和分别作为三元组一端与中间的情况,所以记\(Cnt1[i][j]\)表示\(i,j\)分别作为三元组两端的次数,记\(Cnt2[i][j]\)表示\(i\)作为三元组一端,\(j\)作为三元组中间的次数。然后依然枚举\(p,q\)的出边得到\(x,y\),若\(sum-Cnt[x]-Cnt[y]+Cnt1[x][y]+Cnt2[x][y]+Cnt2[y][2]\)大于等于\(0\),则合法。
代码长这样

for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) Node[i][j].clear(),Tim1[i][j]=Tim2[i][j]=0;
for (int i=1;i<=n;i++)//预处理出所有三元组
    for (int j=Head[i];j!=-1;j=Next[j])
        for (int k=Head[V[j]];k!=-1;k=Next[k])
            if (V[k]!=i)
                Node[i][V[k]].push_back(V[j]);
int tim=0;//为了防止清空二维数组时耗费大量时间,这里记录一个时间戳,下面的Tim1[][]和Tim2[][]分别对应相应的Cnt1[][]和Cnt2[][]的时间戳
for (int p=1;p<=n;p++)
    for (int q=p+1;q<=n;q++)
    {
        int sum=0;mem(Cnt,0);tim++;
        for (int i=Head[p];i!=-1;i=Next[i])
            if (V[i]!=q)
                for (int j=Head[q];j!=-1;j=Next[j])
                    if ((V[j]!=p)&&(V[i]!=V[j]))
                    {
                        int u=V[i],v=V[j];
                        for (int k=0;k<Node[u][v].size();k++)
                        {
                            int z=Node[u][v][k];
                            if ((z==p)||(z==q)) continue;
                            Cnt[u]++;Cnt[v]++;Cnt[z]++;sum++;
                            if (Tim1[u][v]!=tim) Tim1[u][v]=tim,Cnt1[u][v]=1;
                            else Cnt1[u][v]++;
                            if (Tim2[u][z]!=tim) Tim2[u][z]=tim,Cnt2[u][z]=1;
                            else Cnt2[u][z]++;
                            if (Tim2[v][z]!=tim) Tim2[v][z]=tim,Cnt2[v][z]=1;
                            else Cnt2[v][z]++;
                        }
                    }
            for (int i=Head[p];i!=-1;i=Next[i])
            if (V[i]!=q)
                for (int j=Head[q];j!=-1;j=Next[j])
                    if ((V[j]!=p)&&(V[i]!=V[j]))
                    {
                        int x=V[i],y=V[j];
                        if (sum-Cnt[x]-Cnt[y]+((Tim2[x][y]==tim)?(Cnt2[x][y]):(0))+((Tim2[y][x]==tim)?(Cnt2[y][x]):(0))+((Tim1[x][y]==tim)?(Cnt1[x][y]):(0)))
                            Ans[x][y]=Ans[y][x]=1;
                    }
    }

可以说非常休闲了

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int maxM=5010*2;
const int inf=2147483647;

int n,m;
int edgecnt=0,Head[maxN],Next[maxM],U[maxM],V[maxM];
bool Map[maxN][maxN],Ans[maxN][maxN];
int Cnt[maxN],Cnt1[maxN][maxN],Cnt2[maxN][maxN];
int Tim1[maxN][maxN],Tim2[maxN][maxN];
vector<int> Node[maxN][maxN];

void Add_Edge(int u,int v);
void Do2();
void Do3();
void Do4();
void Do5();
void Do6();
void Do7();

int main()
{
    int TTT;scanf("%d",&TTT);
    while (TTT--)
    {
        edgecnt=0;mem(Head,-1);mem(Map,0);mem(Ans,0);
        int K;
        scanf("%d%d%d",&n,&m,&K);
        for (int i=1;i<=m;i++)
        {
            int u,v;scanf("%d%d",&u,&v);
            if ((Map[u][v])||(u==v)) continue;
            Add_Edge(u,v);Map[u][v]=Map[v][u]=1;
        }
        if (K==2) Do2();
        if (K==3) Do3();
        if (K==4) Do4();
        if (K==5) Do5();
        if (K==6) Do6();
        if (K==7) Do7();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
                printf("%c",(Ans[i][j])?('Y'):('N'));
            printf("\n");
        }
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;U[edgecnt]=u;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;V[edgecnt]=u;U[edgecnt]=v;
    return;
}

void Do2()
{
    for (int i=1;i<=edgecnt;i++) Ans[U[i]][V[i]]=1;
    return;
}

void Do3()
{
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            for (int k=Head[i];k!=-1;k=Next[k])
                if (Map[V[k]][j]) Ans[i][j]=Ans[j][i]=1;
    return;
}

void Do4()
{
    for (int x=1;x<=n;x++)
        for (int y=x+1;y<=n;y++)
            for (int i=Head[x];i!=-1;i=Next[i])
                if (V[i]!=y)
                    for (int j=Head[y];j!=-1;j=Next[j])
                        if ((V[i]!=V[j])&&(V[j]!=x)&&(Map[V[i]][V[j]]))
                            Ans[x][y]=Ans[y][x]=1;
    return;
}

void Do5()
{
    for (int p=1;p<=n;p++)
        for (int q=p+1;q<=n;q++)
        {
            int sum=0;mem(Cnt,0);
            for (int i=Head[p];i!=-1;i=Next[i])
                if ((V[i]!=q)&&(Map[V[i]][q]))
                    Cnt[V[i]]++,sum++;
            for (int i=Head[p];i!=-1;i=Next[i])
                if (V[i]!=q)
                    for (int j=Head[q];j!=-1;j=Next[j])
                        if ((V[j]!=p)&&(V[i]!=V[j])&&(sum-Cnt[V[i]]-Cnt[V[j]]))
                            Ans[V[i]][V[j]]=Ans[V[j]][V[i]]=1;
        }
    return;
}

void Do6()
{
    for (int p=1;p<=n;p++)
        for (int q=p+1;q<=n;q++)
        {
            int sum=0;mem(Cnt,0);
            for (int i=Head[p];i!=-1;i=Next[i])
                if (V[i]!=q)
                    for (int j=Head[q];j!=-1;j=Next[j])
                        if ((V[j]!=p)&&(V[i]!=V[j])&&(Map[V[i]][V[j]]))
                            Cnt[V[i]]++,Cnt[V[j]]++,sum++;
            for (int i=Head[p];i!=-1;i=Next[i])
                if (V[i]!=q)
                    for (int j=Head[q];j!=-1;j=Next[j])
                        if ((V[j]!=p)&&(V[i]!=V[j])&&(sum-Cnt[V[i]]-Cnt[V[j]]+Map[V[i]][V[j]])) Ans[V[i]][V[j]]=Ans[V[j]][V[i]]=1;
        }
    return;
}

void Do7()
{
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) Node[i][j].clear(),Tim1[i][j]=Tim2[i][j]=0;
    for (int i=1;i<=n;i++)
        for (int j=Head[i];j!=-1;j=Next[j])
            for (int k=Head[V[j]];k!=-1;k=Next[k])
                if (V[k]!=i)
                    Node[i][V[k]].push_back(V[j]);
    int tim=0;
    for (int p=1;p<=n;p++)
        for (int q=p+1;q<=n;q++)
        {
            int sum=0;mem(Cnt,0);tim++;
            for (int i=Head[p];i!=-1;i=Next[i])
                if (V[i]!=q)
                    for (int j=Head[q];j!=-1;j=Next[j])
                        if ((V[j]!=p)&&(V[i]!=V[j]))
                        {
                            int u=V[i],v=V[j];
                            for (int k=0;k<Node[u][v].size();k++)
                            {
                                int z=Node[u][v][k];
                                if ((z==p)||(z==q)) continue;
                                Cnt[u]++;Cnt[v]++;Cnt[z]++;sum++;
                                if (Tim1[u][v]!=tim) Tim1[u][v]=tim,Cnt1[u][v]=1;
                                else Cnt1[u][v]++;
                                if (Tim2[u][z]!=tim) Tim2[u][z]=tim,Cnt2[u][z]=1;
                                else Cnt2[u][z]++;
                                if (Tim2[v][z]!=tim) Tim2[v][z]=tim,Cnt2[v][z]=1;
                                else Cnt2[v][z]++;
                            }
                        }

            for (int i=Head[p];i!=-1;i=Next[i])
                if (V[i]!=q)
                    for (int j=Head[q];j!=-1;j=Next[j])
                        if ((V[j]!=p)&&(V[i]!=V[j]))
                        {
                            int x=V[i],y=V[j];
                            if (sum-Cnt[x]-Cnt[y]+((Tim2[x][y]==tim)?(Cnt2[x][y]):(0))+((Tim2[y][x]==tim)?(Cnt2[y][x]):(0))+((Tim1[x][y]==tim)?(Cnt1[x][y]):(0)))
                                Ans[x][y]=Ans[y][x]=1;
                        }
        }
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4086/Luogu3323][SDOI2015]旅行计划(分类讨论,容斥原理,计数)


HNCJ OIer 一枚