【BZOJ1064】[NOI2008] 假面舞会（图上DFS）

点此看题面

大致题意： 有\(k\)种面具（\(k\)是一个未知数且\(k≥3\),每种面具可能有多个），已知戴第\(i\)种面具的人能看到第\(i+1\)种面具上的编号，特殊的，戴第\(k\)种面具的人能看到第\(1\)种面具上的编号，现在用\(x\)和\(y\)来表示戴着第\(x\)号的面具的人能看到第\(y\)号面具的编号，给你\(m\)组\(x\)和\(y\)（信息可能并不完整），请你求出至多和至少有多少个面具。

题解

这道题可以近似地看作一个有向图，但是有向图在这道题目中是极难操作的，因此我们可以用一个简(xuan)单(xue)的小技巧：

add(x,y,1),add(y,x,-1);//将从x到y的有向边分成从x到y的权值为1的边和从y到x的权值为-1的边，虽说依然是有向图，但操作起来与无向图差不多，可以从两个方向走

有了这个铺垫，后面的过程就会省力许多。

其实，我们可以对这道题中的图进行一个分类讨论：

第一种情况是图中只存在环。

如果是个有向图，找环是个很麻烦的过程，但由于我们之前已经把这张图改成了无向图，找环就非常方便啦！

在找环的过程中，我们可以轻松计算出环的长度（用当前值减去上一次访问该节点时的值，然后取绝对值即可，具体实现见代码）。

此时，我们可以得出一个十分显然的结论：面具的种类数是所有环长的gcd的一个因数（证明？我也不知道，感性理解一下即可）。

因此，最终面具的种数的最大值应为所有环长的gcd，最小值应为该gcd大于等于3的最小因数。

第二种情况则是图中不存在环，而是由若干棵树（这里我们把链也当作一棵树）组成。

这个时候的答案就更好推了，最大值就是最大的树的深度，最小值就是3，当然要注意判断最大值是否小于3，小于3要输出-1。

那不就好了吗？直接上代码！

等等。。。如果原图中既有环又有树（链）呢？那该怎么办？

答案是没关系！当作只有环来做就可以了，因为树在这种情况中可以忽略不计！

代码

#include<bits/stdc++.h>

#define N 100000

#define M 1000000

using namespace std;

int n,m,ans=0,ee=0,Min,Max,sum,lnk[N+5],vis[N+5],s[N+5];

struct edge

{

    int to,nxt,val;

}e[2*M+5];

inline char tc()

{

    static char ff[100000],*A=ff,*B=ff;

    return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

    x=0;int f=1;char ch;

    while(!isdigit(ch=tc())) if(ch=='-') f=-1;

    while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

    x*=f;

}

inline void write(int x)

{

    if(x<0) putchar('-'),x=-x;

    if(x>9) write(x/10);

    putchar(x%10+'0');

}

inline void add(int x,int y,int z)

{

    e[++ee].to=y,e[ee].nxt=lnk[x],e[ee].val=z,lnk[x]=ee;

}

inline int gcd(int x,int y)

{

    return y?gcd(y,x%y):x;

}

inline void dfs(int x)//用dfs对原图进行遍历，记录是环长gcd和最大树的深度

{

    vis[x]=1;//标记已访问

    for(register int i=lnk[x];i;i=e[i].nxt)

    {

    	if(vis[e[i].to]) ans=gcd(s[x]-s[e[i].to]+e[i].val,ans);//说明有环，并更新环长gcd

		else s[e[i].to]=s[x]+e[i].val,Min=min(Min,s[e[i].to]),Max=max(Max,s[e[i].to]),dfs(e[i].to);//更新最大树的深度，并继续往下dfs

	}

}

int main()

{

	register int i;int x,y;

    for(read(n),read(m),i=1;i<=m;++i)

        read(x),read(y),add(x,y,1),add(y,x,-1);

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

        if(!vis[i]) Min=Max=0,dfs(i),sum+=Max-Min+1;//若当前节点没有访问过，则对其进行dfs

    if(ans<0) ans=-ans;//ans在一波操作后可能会小于0，若其小于0则要将其改为正数

    if(ans)//ans不为0说明有环

    {

        if(ans<3) return puts("-1 -1"),0;//ans小于3，说明无解，直接输出-1并退出程序

        write(ans),putchar(' ');

        for(i=3;i<=ans;i++)

            if(!(ans%i)) return write(i),0;//寻找环长gcd大于3的最小因数

    }

    if(sum<3) puts("-1 -1");//判断最大深度是否小于3

    else write(sum),putchar(' '),putchar('3');//输出答案

    return 0;

}

巴特西

【BZOJ1064】[NOI2008] 假面舞会（图上DFS）

题解

代码

最新文章

热门文章