题意:
对于一个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");}
}