【纪中集训2019.3.29】循环流

题目

描述

对于一个\(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;
}

【纪中集训2019.3.29】循环流

原文：https://www.cnblogs.com/Paul-Guderian/p/10635397.html