转载

$Luogu$ $P3524$ $[POI2011]IMP-Party$

链接

背景

\(18th\) \(Polish\) \(Olympiad\) \(in\) \(Informatics\) \(Round3\) \(Day1\) \(A\) 题, \(Luogu\) \(P3524/BZOJ2530\)

题意

给定一张 \(n\) 个点 \(m\) 条边的图,保证图中有一个 \(\frac{2}{3}n\) 大小的团。求出其中任意 \(\frac{1}{3}n\) 个点的编号,按递增顺序排列。有 \(SPJ\)

解法

\(O(n^2)\) 标记两点间没有边的点的编号。具体来说,每次枚举一个未标记的点 \(i\) ,找到第一个编号比其大且未标记的不连通的点 \(j\) ,标记 \(i\)\(j\) 两个点,枚举下一个点。
标记完后,按递增顺序输出前 \(\frac{1}{3}n\) 个未标记的点即可。

细节

\(1.\) 标记 \(i\)\(j\) 两个点,一定要枚举下一个点。(注意!!!)

代码

$View$ $Code$
//省略头文件
using namespace std;
inline int read()
{
    int ret=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch='0'&&ch<='9')
    {
        ret=(ret<<1)+(ret<<3)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,m,x,y,cnt;
bool vis[3005],g[3005][3005];
int main()
{
    n=read();
    m=read();
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        g[x][y]=1;
        g[y][x]=1;
    }
    for(register int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(register int j=i+1;j<=n;j++)
            {
                if((!vis[j])&&(!g[i][j]))
                {
                    vis[i]=1;
                    vis[j]=1;
                    break;
                }
            }
        }
    }
    int std=n/3;
    for(register int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            printf("%d ",i);
            cnt++;
        }
        if(cnt==std)
            return 0;
    }
    return 0;
}

转载于:https://www.cnblogs.com/Peter0701/p/11342748.html

正文到此结束
本文目录