洛谷 P5061 秘密任务 —

题目：https://www.luogu.org/problemnew/show/P5061

首先，“配合默契”就是连边的意思；

但发现答案不好统计，因为有连边的两个点可以分在一组，也可以不分在一组；

于是正难则反，因为没有连边的两个点一定不在一组，所以连成补图，二分图染色；

如果染色出现矛盾，就是无解——第三问的意思是什么？无解的时候应该也只是某几个连通块染色不合法，在其它连通块中也有配合默契的一对人可以分在同一组啊，为什么输出 m ？

然后背包一下，得到可以选择的人数，直接一个一个加到答案即可，差值最小就是人数最接近 n/2；

然后配合默契的一对人不能在一组的方案数也直接 n^2 统计在一个连通块没有连边但染色不同的点对即可；

虽然出题人的正解并不是二分图，但不太懂那个正解...

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=,mod=1e9+;

int n,m,col[xn],f[xn],cnt,s[xn][],in[xn],tot;

bool sid[xn][xn],cant[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

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

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

bool dfs(int x,int cr,int nw)

{

  col[x]=cr; s[nw][cr]++; in[x]=nw;

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

    {

      if(sid[x][u]||x==u)continue;

      if(!col[u])dfs(u,-cr,nw);

      else if(col[u]==col[x])return ;

    }

  return ;

}

int main()

{

  n=rd(); m=rd();

  for(int i=,x,y;i<=m;i++)x=rd(),y=rd(),sid[x][y]=sid[y][x]=;

  bool flag=;

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

    if(!col[i])

      {

    bool fl=dfs(i,,++cnt);

    if(!fl)flag=,cant[cnt]=;

      }

  if(flag){puts("-1"); printf("%d\n",m); return ;}//m?!

  else

    {

      f[]=;

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

    for(int j=n;j>=;j--)//--!

      {

        if(j>=s[i][])f[j]|=f[j-s[i][]];

        if(j>=s[i][])f[j]|=f[j-s[i][]];

      }

      int ans=,num;

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

    {

      if(!f[i]||!f[n-i])continue;//f[0]=1

      ans++; num=i;

    }

      printf("%d %d\n",ans,upt(pw(,n-num)-pw(,num)));

    }

  int sum=;

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

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

      if(in[i]==in[j]&&sid[i][j]&&(cant[in[i]]||col[i]!=col[j]))sum++;

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

  return ;

}

巴特西

洛谷 P5061 秘密任务 —— 二分图

最新文章

热门文章