2017icpc乌鲁木齐网络赛Colored Graph (构造)

题目

  https://nanti.jisuanke.com/t/16958

题意

  给定一个n(n<=500)个点的无向图,给每条边黑白染色,输出同色三角形最少的个数和对应的方案

分析

  首先考虑给定一个染色完毕的无向图,如何求同色三角形的个数

  同色三角形的个数=总的个数-异色三角形的个数

  而一个异色三角形对应两个异色角,所以我们可以通过算异色角的个数来计算异色三角形的个数

  而异色角是有一个固定的点i引出去的n-1条边所决定的

  设某个点i有$x_i$条1边,有$n-1-x_i$条2边

  可以发现异色角的个数是$\sum {x_i*(n-1-x_i)}$

  那自然我们希望每个点引出去的1边和2边数量尽可能相同

  对于偶数,可以根据样例的规律构造两个n/2的团,然后对连即可

  对于奇数,发现4k+1的时候边数是偶数,此时可以使得每个点两种颜色边数相同,而4k+3的时候有唯一的一个点不能满足

  关于奇数的构造可以每4个点往上加,构造即可

时间: 09-12

2017icpc乌鲁木齐网络赛Colored Graph (构造)的相关文章

2017icpc 乌鲁木齐网络赛

A .Banana Bananas are the favoured food of monkeys. In the forest, there is a Banana Company that provides bananas from different places. The company has two lists. The first list records the types of bananas preferred by different monkeys, and the s

2016大连网络赛 Sparse Graph

Sparse Graph Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if

【后缀数组】【RMQ】HDU 6194 - string string string (2017ICPC沈阳网络赛)

string string string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I

2017ICPC沈阳网络赛 HDU 6025 -- card card card(最大子段和)

card card card Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1230    Accepted Submission(s): 549 Problem Description As a fan of Doudizhu, WYJ likes collecting playing cards very much. One day

2017乌鲁木齐网络赛 J题 Our Journey of Dalian Ends ( 最小费用最大流 )

题目链接 题意 : 给出一副图,大连是起点,终点是西安,要求你求出从起点到终点且经过中转点上海的最小花费是多少? 分析 : 最短路是最小费用最大流的一个特例,所以有些包含中转限制或者经过点次数有限制的最短路问题都可以考虑使用最小费用最大流来建图解决. 首先对于每个点都只能经过一次这个限制,在网络流中是比较常见的一个限制,只要将所有的点由一拆二且两点间连容量为 1 且花费为 0 的边. 这题的建图很巧妙,是将中转点作为汇点,提示到了这里不如停下来想想如何建图? 然后抽象出一个超级源点,然后将起点和

2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛

Banana Bananas are the favoured food of monkeys. In the forest, there is a Banana Company that provides bananas from different places. The company has two lists. The first list records the types of bananas preferred by different monkeys, and the seco

CCPC 2017 网络赛

1001.我们的想法是,先构造n个要删掉的点,然后不断给图加边,使得每条边的其中一个点在n个点之中. 我们要使n个点之外的点尽量多,并且每次删掉的点在n个点之外. 贪心的决策是,每次操作,前n个点的度和令外的最大度的点度数相同. 然后删掉这个点之后,之后的操作,剩余的点也满足这个要求.所以度数最大的点必定与n个点有边. 于是可以这样构造,增加n批点(i = 1~n),每次增加n/i个点的,每个增加的点连出i条边到n个点. 这样,n个点每次增加的最大度数不超过1.但每次删点的时候(按n~1批的顺序

2015沈阳网络赛1003 Minimum Cut 树链剖分 数组维护前缀和进行区间增减

2015沈阳网络赛1003  Minimum Cut   树链剖分 数组维护前缀和进行区间增减 Minimum Cut Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 65535/102400 K (Java/Others)Total Submission(s): 0    Accepted Submission(s): 0 Problem Description Given a simple unweighted graph G 

HDU6706 CCPC 2019网络赛 huntian oy 推式子+杜教筛

CCPC 2019 网络赛 HDU 6706 huntian oy 标签 奇奇怪怪的数论结论 杜教筛 前言 我的csdn和博客园是同步的,欢迎来访danzh-博客园~ 简明题意 给定n,a,b,求: \[\sum_{i=1}^n\sum_{j=1}^igcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)\] 思路 首先有一个结论: \[gcd(i^a-j^a,i^b-j^b)=i^{gcd(a,b)}-j^{gcd(a,b)}\] 上面的结论对于i,j互质是成立的