学步园

点击打开链接 Konig定理：二分图的最小顶点覆盖数 = 二分图的最大匹配数 题意： 在N*N的网络中有K颗小行星。小行星i的位置是(Ri, Ci)。现在有一个强力的武器能够用一发光束将一整行或一整列的小行星消灭。想要利用这个武器消灭所有的小行星最少需要几发光束？ 分析： 以小行星的左右坐标建立二分图，就可以看出是求二分图的最小顶点覆盖数。 #include <cstdio> #include <cstring> #include <vector> #in...

题意： 给定一个字符串，从任意位置把它切为两半，得到两条子串 定义 子串1为s1，子串2为s2，子串1的反串为s3，子串2的反串为s4 现在从s1 s2 s3 s4中任意取出两个串组合，问有多少种不同的组合方法 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <set> #include <map> #include <string> #include <stack&...

Kind of a Blur Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 642   Accepted: 137 Description Image blurring occurs when the object being captured is out of the camera’s focus. The top two figures on the right are an example of an image and its blurred version. Restoring the original image given only the blurred version is one of the most interesting topics in image ...

点击打开链接 求顶点1到其他点的最短距离的最长距离。。 测试。。dijkstra + 优先队列 #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <set> #include <map> #include <string> #include <stack> #include <queue> #include <vector> #define for0(a,b) for(a=0;a<b;++a) #define for...

题意： 矮人虽小却喜欢乘坐巨大的轿车，车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了集中到聚餐地点，矮人A 要么开车到矮人B 家中，留下自己的轿车在矮人B 家，然后乘坐B 的轿车同行；要么直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K 辆轿车。给你一张加权无向图，描述了N 个矮人的家和聚餐地点，求出所有矮人开车最短总路程。 单...

题意：有n个村庄，村庄在不同坐标和海拔，现在要对所有村庄供水，只要两个村庄之间有一条路即可，          建造水管距离为坐标之间的欧几里德距离（好象是叫欧几里德距离吧），费用为海拔之差          现在要求方案使得费用与距离的比值最小 很显然，这个题目是要求一棵最优比率生成树， 0-1分数规划，0-1分数规划是分数规划的一种特殊情况，分数规划适用于求解最优化问题的，对于求最大的对应解，该理论也有效 这是从网上...

poj 2391 Ombrophobic Bovines, 最大流, 拆点, 二分 dinic /* * Author: yew1eb * Created Time: 2014年10月31日 星期五 15时39分22秒 * File Name: poj2391.cpp */ #include <ctime> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <s...

http://www.spoj.com/problems/PROFIT/ 最大权闭合子图：点权之和最大的闭合图。 建图：每一条有向边变为容量为inf，源S到正权点v(wv>0)的边容量wv，负权点v(wv<0)到汇T的边容量−wv，零权点v(wv=0)不与源和汇相连。然后求最小割(SUM-最大流)即为答案。 /* * Author: yew1eb * Created Time: 2014年10月31日 星期五 15时39分22秒 * File Name: spoj1476 maximum profit.cpp */ #include <ctime> #include ...

Prime Test Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 24514   Accepted: 5730 Case Time Limit: 4000MS Description Given a big integer number, you are required to find out whether it's a prime number. Input The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 254). Outp...

Circulation pipe Time Limit: 4 Seconds      Memory Limit: 65536 KB Darkgy is a transport pipe master. One day, due to some strange redstone signal, an Iron pipe changed its direction and make a part of the pipe system become a circulation pipe. The circulation pipe consists of L unit pipe numbered from 0 to L-1. Every K ticks, an item will input into pipe 0, and it will be transported in pipe...