BZOJ 3275: Number

• hust_wj 发布于
• 1798 收藏

题目分析： 两个点同时选会有inf的代价，需要满足二分图性质 两个偶数的gcd不为1 两个奇数的平方和不可能是完全平方数，因为奇数可以写成2k+1, 平方模4余1，两个平方的和模4余2且为偶数，而偶数的平方模4余0，所以不可能是平方数 所以两个不能同时选的数一定是一奇一偶，二分图，加上权值跑最小割即可 #include #include #include #include #include #...