A clique is a complete graph, in which there is an edge between every pair of the vertices. Given a graph with N vertices and M edges, your task is to count the number of cliques with a specific size S in the graph. Input The first line is the number of test cases. For each test case, the first line contains 3 integers N,M and S (N ≤ 100,M ≤ 1000,2 ≤ S ≤ 10), each of the following M lines contains 2 integers u and v (1 ≤ u < v ≤ N), which means there is an edge between verti 继续阅读 >>


楚东方 17/10/26 23:52:12
Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4i4. Now, you need to write 继续阅读 >>


楚东方 17/10/26 23:44:30
HDU-1002 大数A+B import java.math.BigDecimal; import java.math.BigInteger; import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T; T = in.nextInt(); for(int cas = 1;cas <= T;cas++ ) { System.out.println("Case "+cas+":"); BigInteger a = in.nextBigInteger(); BigInteger b = in. 继续阅读 >>


楚东方 17/10/25 23:06:51
二分图最大匹配问题。 【建模方法】 在二分图的基础上增加源S和汇T。 1、S向X集合中每个顶点连一条容量为1的有向边。 2、Y集合中每个顶点向T连一条容量为1的有向边。 3、XY集合之间的边都设为从A集合中的点到B集合之中的点,容量为1的有向边。 求网络最大流,流量就是匹配数,所有满流边是一组可行解。 【建模分析】 基本的二分图最大匹配,可以直接用匈牙利算法或Hopcroft_Karp算法解决,更一般的方法是网络最大流。 最大权闭合图 【问题分析】 最大权闭合图问题,可以转化成最小割问题,进而用最大流解决。 【建模方法】 把每个实验看作二分图X集合中的顶点,每个设备看作二分图Y集合中的顶点,增加源S和汇T。 1、从S向每个Xi连接一条容量为该点收入的有向边。 2、从Yi向T连接一条容量为该点支出的有向边。 3、如果一个实验i需要设备j,连接一条从Xi到Yj容量为无穷大的有向边。 统计出所有实验的收入只和Total,求网络最大流Maxflow,最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点 继续阅读 >>


楚东方 17/10/19 09:25:57
题目链接 大牛思路: 【问题分析】 二分图点权最大独立集,转化为最小割模型,从而用最大流解决。 【建模方法】 首先把棋盘黑白染色,使相邻格子颜色不同,所有黑色格子看做二分图X集合中顶点,白色格子看做Y集合顶点,建立附加源S汇T。 1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。 2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。 3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。 求出网络最大流,要求的结果就是所有格子中数值之和减去最大流量。 【建模分析】 这是一个二分图最大点权独立集问题,就是找出图中一些点,使得这些点之间没有边相连,这些点的权值之和最大。独立集与覆盖集是互补的,求最大点权独立集可以转化为求最小点权覆盖集(最小点权支配集)。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。 对于一个网络,除去冗余点(不存在一条ST路径经过的点),每个顶点都在一个从S到T的路径上 继续阅读 >>


楚东方 17/10/18 23:12:56
题目链接 先从终点BFS到起点,并记录下其到终点的距离,然后从起点BFS到终点,并优先选取边权值小的. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9+10; const int maxn = 100005; struct node { int to; int col; }; vector<node> mm[maxn]; int inque[maxn]; int d[maxn]; int vis[maxn]; int ans[maxn]; int n,m; node nt; struct poin { int x; int step; }; void bfs() { //init inque ans d memset(inque,0,sizeof(inque)); memset(d,0,sizeof(d)); poin cur, 继续阅读 >>


楚东方 17/10/18 15:48:10
Play on Words Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8780    Accepted Submission(s): 3015 Problem Description Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.  There is a large number of magnetic plates 继续阅读 >>


楚东方 17/10/17 23:23:18
1659: [Usaco2006 Mar]Lights Out 关灯 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 315  Solved: 81 [Submit][Status][Discuss] Description 奶牛们喜欢在黑暗中睡觉。每天晚上,他们的牲口棚有L(3<=L<=50)盏灯,他们想让亮着的灯尽可能的少。他们知道按钮开关的位置,但喜闻乐见的是他们并没有手指。你得到了一个长度为T(1<=T<=7)的插槽用以帮助奶牛们改变灯的状态。 Input 第一行,两个整数L和T。第二行给出一个长度为L的01串表示初始灯的状态,0表示灯是灭的,1表示灯是亮的。第三行给出一个长度为T的01串,表示你获得的插槽。 Output 第一行输出一个整数K,表示在满足亮着的灯最少的情况下,你要用插槽操作的次数。第二行到第K+1行,每行一个整数表示你的插槽使用的位置。 "K最小的解, 继续阅读 >>


楚东方 17/10/16 17:46:14
Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1894    Accepted Submission(s): 631 Problem Description There are N bombs needing exploding. Each bomb has three attributes: exploding radius ri, position (xi,yi) and lighting-cost ci which means you need to pay ci cost making it explode. If a un-lighting bomb is in or on the b 继续阅读 >>


楚东方 17/10/16 01:21:42
传递 Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1476    Accepted Submission(s): 672 Problem Description 我们称一个有向图G是传递的,当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c。 我们称图G是一个竞赛图,当且仅当它是一个有向图且它的基图是完全图。换句 话说,将完全图每条边定向将得到一个竞赛图。 下图展示的是一个有4个顶点的竞赛图。 现在,给你两个有向图P = (V,Ep)和Q = (V,Ee),满足: 1.   EP与Ee没有公共边; 2.  (V,Ep⋃Ee)是一个竞赛图。 你的任务是:判定是否P,Q同时为传递的。 &nb 继续阅读 >>


楚东方 17/10/16 00:12:15