题目
描述
对于一个 \(n\) 个点的循环流网络, 只存在容量为 \(1\) 或者 \(2\) 的边;
满足容量为 \(1\) 的边有 \(a\) 条, 容量为 \(2\) 的边有 \(b\) 条;
询问是否存在这样的容量网络;
范围
$1 \le T \le 127449 ?, ?2 \le n \le 50 ?, ?0 \le a,b \le 50 $ ;
题解
出题人故意把范围出得比较小来迷惑选手也不是没有可能...;
分类构造, 主要是要仔细一点;
没有 \(n==1\) 的情况;
\(n==2\)
\(a + 2 b\) 必须要为偶数, 否则无解, 记 \(mid = \frac{a+2b}{2}\);
如果 \(a=0\), 必选要有 \(b \% 2 = 0\) , 否则无解;
如果 \(b>0\) 那么一定可以通过先选 \(2\) 边, 再选 \(1\) 边的方法达到 \(mid\), 即有解;
$n>2 $
\(a+b<n\), 图一定不连通, 无解;
\(a+b=n\), 连通的图只能是一个环, 如果只存在一种类型的边才有解;
\(a+b> n\)
\(a=1\), 剩下的全都是偶数度数, 此时一定无解;
\(a \neq 1 ,b = 1\), 可以将两条反向的 \(1\) 和 \(2\) 边合成为一个 \(1\) 边, 注意到 \(a>=n\);
\(a \neq 1 ,b \neq 1\), 可以将 \(a 和 b\) 组成 \(min(a,n) 和 min(b,n)\) 的两个平衡的图, 合起来有解;
所以另外需要再说明如何让 \(a(>=n)\) 条相同的 \(1\) 或 \(2\) 边有解, 只需要考虑 \(a<2n\) 的情况;
\(a==n\) 直接构造成环;
\(a==n+1\) 直接构造成一个 \(n-1\) 环和一个 \(2\) 元环, 且两者有一个点重复;
\(a>n+1\) 有 \(a-n>2\), 先构成一个 \(n\) 元环, 由于 \(n>=3\) 且 \(2x+3y\) 可以有任意正整数, 所以随便补上一些 \(2\) 元环和 \(3\) 元环就好了;
模拟赛的时候大样例比较水, 以为自己随便就过了, 然后只有 20, 下次注意这类题....;
- #include<bits/stdc++.h>
- using namespace std;
- int C,T;
- int main(){
- freopen("flow.in","r",stdin);
- freopen("flow.out","w",stdout);
- scanf("%d%d",&C,&T);
- while(T--){
- int n,a,b;
- scanf("%d%d%d",&n,&a,&b);
- if(n==2){
- if(!a&&!b){puts("0");continue;}// 如果两个都没有则一定无法构成, 否则其中一个一定有;
- if(a&1){puts("0");continue;}// 如果 1 边为奇数, 那么一定不存在 mid = (a+2b)/2, 否则存在;
- if(!a&&(b&1)){puts("0");continue;}// 如果没有 1 边, 那么 2 边的个数必须要是偶数才能达到 mid;
- puts("1");// 否则一定可以先选 2, 再选 1 填到 mid;
- }else{
- if(a==1){puts("0");continue;}// 如果 1 边只有一个一定无法构成, 否则 1 边的个数为 0 或者 >=2;
- if(a+b<n){puts("0");continue;}// 如果两条边的和无法构成一个环显然无解;
- if(a+b==n&&a&&b){puts("0");continue;}// 当相等时一定是一个环, 如果同时存在两种边则一定无解;
- puts("1");// 否则有 a+b>n>=3, 分以下情况去证明:
- // 首先明确 2 和 3 可以构成所有 >=2 的整数;
- //1 : b == 1 , 可以将反向的 1 + 2 -> 1 , 1 边的个数 >= n>= 3, ;
- //2 : b>= 2 , 此时很容易可以分别将 a(已经讨论了 a==1) 和 b 分别成环, 再组合起来, 最小是 a+b-1>=n 的, 可以覆盖;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3007196.html