当前位置: 代码迷 >> 综合 >> 【构造】【细节】CodeForces990D Graph And Its Complement
  详细解决方案

【构造】【细节】CodeForces990D Graph And Its Complement

热度:96   发布时间:2023-09-27 07:32:14.0

题意:

对于一个N个点的无向图,给出两个值a、b
求是否存在一个图,原来有a个联通块
并且将每条存在的边删除,不存在的边脸上后,有b个联通快。
如果存在则输出。


分析:

有一个很重要的结论,存在这个图的充要条件为:a=1或b=1(之后要除去两个特殊情况,非常恶心)

证明很简单,如果当前有不为1个联通块,那么把边反转之后,则每两个不属于同一个联通块的点必有一条边相连(原来根本就不连通,所以更不可能有直接边)。这样一来,原来在同一个联通块的点,都会连向至少一个同一个点(即原来和它不在一个联通块的),所以原来在同一个联通块内的点,在经过反转操作后,仍然联通。并且,原来的两个联通块之间,现在必有边相连,所以整个图就成了一个联通块。

很显然,a和b的关系不是绝对的。即我们可以交换a和b,并且同时交换两个图。
现在我们使得a不为1,b为1。

现在构造很简单了,只需要随便练一些边使得联通块个数为a即可。比较简单的方式是顺序连边(即1连2,2连3……知道剩余的联通块个数等于a为止)

有两个特殊情况:
N=2时,若a=b=1,无解。
N=3时,若a=b=1,无解。
这两个特例是由于点数太少,无法完成之前的证明(但是相当难发现啊!)(不过还好我运气不错,wa了之后手跑数据就是跑的这两个)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1010
using namespace std;
int n,a,b,m;
int w[MAXN][MAXN];
int main(){bool flag=0;SF("%d%d%d",&n,&a,&b);  if(a>1&&b>1){PF("NO\n"); return 0;}if((n==3||n==2)&&a==1&&b==1){PF("NO\n");return 0;   }PF("YES\n");if(a>b){swap(a,b);flag=1;}for(int i=max(b,1);i<n;i++){w[i][i+1]=1;w[i+1][i]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j){PF("0");continue;}PF("%d",w[i][j]^flag^1);    }PF("\n");}
}
  相关解决方案