【问题分析】
二分图最大独立集,转化为二分图最大匹配,从而用最大流解决。
【建模方法】
首先把棋盘黑白染色,使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点,可用的白色格子看做Y集合顶点。建立附加源S汇T,从S向X集合中每个顶点连接一条容量为1的有向边,从Y集合中每个顶点向T连接一条容量为1的有向边。从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。求出网络最大流,要求的结果就是可用格子的数量减去最大流量。
【建模分析】
用网络流的方法解决棋盘上的问题,一般都要对棋盘黑白染色,使之成为一个二分图。放尽可能多的不能互相攻击的骑士,就是一个二分图最大独立集问题。有关二分图最大独立集问题,更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
该题规模比较大,需要用效率较高的网络最大流算法解决。
基础概念:
独立集:
独立集是指图的顶点集的一个子集,该子集的导出子图不含边.如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集.一个图中包含顶点数目最多的独立集称为最大独立集。最大独立集 一定是极大独立集,但是极大独立集不一定是最大的独立集。
支配集:
与独立集相对应的就是支配集,支配集也是图顶点集的一个子集,设S 是图G 的一个支配集,则对于图中的任意一个顶点u,要么属于集合s, 要么与s 中的顶点相邻。 在s中除去任何元素后s不再是支配集,则支配集s是极小支配集。称G的所有支配集中顶点个数最 少的支配集为最小支配集,最小支配集中的顶点个数成为支配数。
最小点的覆盖:
最小点的覆盖也是图的顶点集的一个子集,如果我们选中一个点,则称这个点将以他为端点的所有边都覆盖了。将图中所有的边都覆盖所用顶点数最少,这个集合就是最小的点的覆盖。
最大团:
图G的顶点的子集,设D是最大团,则D中任意两点相邻。若u,v是最大团,则u,v有边相连,其补图u,v没有边相连,所以图G的最大团=其补图的最大独立集。
一些性质:
最大独立集+最小覆盖集=V
最大团=补图的最大独立集
最小覆盖集=最大匹配
posted @
2011-10-17 22:03 小阮 阅读(750) |
评论 (0) |
编辑 收藏
【问题分析】
网络优化问题,用最小费用最大流解决。
【建模方法】
把每天分为二分图两个集合中的顶点Xi,Yi,建立附加源S汇T。
1、从S向每个Xi连一条容量为ri,费用为0的有向边。
2、从每个Yi向T连一条容量为ri,费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大,费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大,费用为s的有向边。
求网络最小费用最大流,费用流值就是要求的最小总花费。
【建模分析】
这个问题的主要约束条件是每天的餐巾够用,而餐巾的来源可能是最新购买,也可能是前几天送洗,今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部,或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理,建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾,其数量为ri,所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾,数量为ri,与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天(Xi->Xi+1),不需要花费,送到快洗部(Xi->Yi+m),费用为f,送到慢洗部(Xi->Yi+n),费用为s。每天需要的餐巾除了刚刚洗好的餐巾,还可能是新购买的(S->Yi),费用为p。
在网络上求出的最小费用最大流,满足了问题的约束条件(因为在这个图上最大流一定可以使与T连接的边全部满流,其他边只要有可行流就满足条件),而且还可以保证总费用最小,就是我们的优化目标。
posted @
2011-10-17 21:36 小阮 阅读(463) |
评论 (0) |
编辑 收藏
摘要: 题意: 给定一个字符串, 求最长回文串分析: 求一个后缀和一个反过来写的后缀的最长公共前缀。具体的做法是:将整个字符串反过来写在原字符串后面,中间用一个特殊的字符隔开。问题变成求这个新的字符串的某两个后缀的最长公共前缀.
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlight...
阅读全文
posted @
2011-06-30 23:34 小阮 阅读(1677) |
评论 (0) |
编辑 收藏
题意: 给定一个字符串, 求不相同的子串的个数.
分析:每个子串其实都是一个后缀的前缀, 原题等价于求: 所有后缀之间不相等前缀个数.
所有后缀按照 suffix(sa[1]), suffix(sa[2]), suffix(sa[3]), ... suffix(sa[n])排序,
每新加入一个后缀suffix(sa[k]), 就增加 n - sa[k] + 1 个前缀, 这些前缀中, 又有height[k]个与前一个后缀相同.
所有只是增加个 n-sa[k]+1-height[k];
整理下求和公示.
#include <stdio>
#include <cstring>
![](/Images/OutliningIndicators/None.gif)
using namespace std;
![](/Images/OutliningIndicators/None.gif)
const int maxn = 1003
![](/Images/OutliningIndicators/None.gif)
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
![](/Images/OutliningIndicators/None.gif)
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int c0(int *r,int a,int b)
{
return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int c12(int k,int *r,int a,int b)
{
if(k==2)
return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else
return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i=0;i<n;i++) wv[i]=r[a[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
return;
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dc3(int *r,int *sa,int n,int m)
{
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
if(p<tbc) dc3(rn,san,tbc,p);
else for(i=0;i<tbc;i++) san[rn[i]]=i;
for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
if(n%3==1) wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
for(i=0,j=0,p=0;i<ta && j<tbc;p++)
sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
for(;i<ta;p++) sa[p]=wa[i++];
for(;j<tbc;p++) sa[p]=wb[j++];
return;
}
![](/Images/OutliningIndicators/None.gif)
int rank[maxn],height[maxn];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
![](/Images/OutliningIndicators/None.gif)
char s[maxn];
int r[maxn*3],sa[maxn*3];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,n,t,ans;
scanf("%d",&t);
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t-->0)
{
scanf("%s",s);
n=strlen(s);
for(i=0;i<n;i++) r[i]=s[i];
r[n]=0;
dc3(r,sa,n+1,128);
calheight(r,sa,n);
ans=n*(n+1)/2;
for(i=1;i<=n;i++) ans-=height[i];
printf("%d\n",ans);
}
return 0;
}
![](/Images/OutliningIndicators/None.gif)
posted @
2011-06-30 21:19 小阮 阅读(614) |
评论 (0) |
编辑 收藏
摘要: 先求凸包, 最大三角形的三个顶点一定在凸包的点上.
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->//Rotating Calipers algorithm#include <stdio.h>#includ...
阅读全文
posted @
2011-06-30 20:37 小阮 阅读(2034) |
评论 (0) |
编辑 收藏
并查集提供的操作:
1. 合并两个集合。
2. 判断两个元素是否在同一个集合里边。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=1001;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class UFS
{
public:
int F[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
tUFS()
{
for (int i=1;i<MAXN;i++)F[i]=-i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int findroot(int a)
{
int r=a,t;
while (F[r]>0) r=F[r];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (F[a]>0)
{t=F[a];F[a]=r;a=t;}
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void Union(int a,int b)
{
F[findroot(a)]=findroot(b);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool Judge(int a,int b)
{
return F[findroot(a)]==F[findroot(b)];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int getroot(int a)
{
return -F[findroot(a)];
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2011-05-03 20:27 小阮 阅读(273) |
评论 (0) |
编辑 收藏
[次短路径]
次短路径可以看作是k短路径问题的一种特殊情况,求k短路径有Yen算法等较为复杂的方法,对于次短路径,可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。
我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径,首先应求出S的单源最短路径。遍历有向图,标记出可以在最短路径上的边,加入集合K。然后枚举删除集合K中每条边,求从S到T的最短路径,记录每次求出的路径长度值,其最小值就是次短路径的长度。
在这里我们以为次短路径长度可以等于最短路径长度,如果想等,也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径,则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。
用Dijkstra+堆求单源最短路径,则每次求最短路径时间复杂度为O(N*log(N+M) + M),所以总的时间复杂度为O(N*M*log(N+M) + M^2)。该估计是较为悲观的,因为一般来说,在最短路径上的边的条数要远远小于M,所以实际效果要比预想的好。
[次小生成树]
类比上述次短路径求法,很容易想到一个“枚举删除最小生成树上的每条边,再求最小生成树”的直观解法。如果用Prim+堆,每次最小生成树时间复杂度为O(N*log(N+M) + M),枚举删除有O(N)条边,时间复杂度就是O(N^2*log(N+M) + N*M),当图很稠密时,接近O(N^3)。这种方法简易直观,但我们有一个更简单,而且效率更高的O(N^2+M)的解法,下面介绍这种方法。
首先求出原图最小生成树,记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v),加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边),把它删掉,计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值,就是次小生成树。
具体实现时,更简单的方法是从每个节点i遍历整个最小生成树,定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值,然后对于添加每条不在最小生成树中的边(i,j),新的生成树权值之和就是MinST + w(i,j) – F[j],记录其最小值,则为次小生成树。
该算法的时间复杂度为O(N^2 + M)。由于只用求一次最小生成树,可以用最简单的Prim,时间复杂度为O(N^2)。算法的瓶颈不在求最小生成树,而在O(N^2+M)的枚举加边修改,所以用更好的最小生成树算法是没有必要的。
[次短路径与次小生成树的例题]
HAOI 2005 路由选择问题
直接求次短路径。
pku 3255 Roadblocks
稍微特殊的次短路径,允许边重复走。
Ural 1416 Confidential
求次小生成树的问题、
pku 1679 The Unique MST
判断最小生成树是否唯一。
http://www.byvoid.com/blog/2-sp-mst/
posted @
2011-05-03 20:21 小阮 阅读(447) |
评论 (0) |
编辑 收藏
根据差乘
double polygonArea(TPolygon p, int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
//已知多边形各顶点的坐标,求其面积
double area;
int i;
area = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1;i <= n;i++)
{
area += (p.p[i - 1].x * p.p[i % n].y - p.p[i % n].x * p.p[i - 1].y);
}
return area / 2;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2011-04-27 21:29 小阮 阅读(476) |
评论 (0) |
编辑 收藏
摘要: 题意:二面平面,给N个点,求最大三角形。分析:先求凸包降低数据规模,最大三角形肯定是凸包的点,然后枚举凸包的各点求三角形。
#include <stdio.h>#include <stdlib.h>#include <math.h>const int MAXN = 50005;int&nbs...
阅读全文
posted @
2011-04-26 20:55 小阮 阅读(568) |
评论 (0) |
编辑 收藏
1、首先需要一个内存池,目的在于:
·减少频繁的分配和释放,提高性能的同时,还能避免内存碎片的问题;
·能够存储变长的数据,不要很傻瓜地只能预分配一个最大长度;
·基于SLAB算法实现内存池是一个好的思路:分配不同大小的多个块,请求时返回大于请求长度的最小块即可,对于容器而言,处理固定块的分配和回收,相当容易实现。当然,还要记得需要设计成线程安全的,自旋锁比较好,使用读写自旋锁就更好了。
·分配内容的增长管理是一个问题,比如第一次需要1KB空间,随着数据源源不断的写入,第二次就需要4KB空间了。扩充空间容易实现,可是扩充的时候必然 涉及数据拷贝。甚至,扩充的需求很大,上百兆的数据,这样就不好办了。暂时没更好的想法,可以像STL一样,指数级增长的分配策略,拷贝数据虽不可避免, 但是起码重分配的几率越来越小了。
·上面提到的,如果是上百兆的数据扩展需要,采用内存映射文件来管理是一个好的办法:映射文件后,虽然占了很大的虚拟内存,但是物理内存仅在写入的时候才会被分配,加上madvice()来加上顺序写的优化建议后,物理内存的消耗也会变小。
·用string或者vector去管理内存并不明智,虽然很简单,但服务器软件开发中不适合使用STL,特别是对稳定性和性能要求很高的情况下。
2、第二个需要考虑的是对象池,与内存池类似:
·减少对象的分配和释放。其实C++对象也就是struct,把构造和析构脱离出来手动初始化和清理,保持对同一个缓冲区的循环利用,也就不难了。
·可以设计为一个对象池只能存放一种对象,则对象池的实现实际就是固定内存块的池化管理,非常简单。毕竟,对象的数量非常有限。
3、第三个需要的是队列:
·如果可以预料到极限的处理能力,采用固定大小的环形队列来作为缓冲区是比较不错的。一个生产者一个消费者是常见的应用场景,环形队列有其经典的“锁无关”算法,在一个线程读一个线程写的场景下,实现简单,性能还高,还不涉及资源的分配和释放。好啊,实在是好!
·涉及多个生产者消费者的时候,tbb::concurent_queue是不错的选择,线程安全,并发性也好,就是不知道资源的分配释放是否也管理得足够好。
4、第四个需要的是映射表,或者说hash表:
·因为epoll是事件触发的,而一系列的流程可能是分散在多个事件中的,因此,必须保留下中间状态,使得下一个事件触发的时候,能够接着上次处理的位置继续处理。要简单的话,STL的hash_map还行,不过得自己处理锁的问题,多线程环境下使用起来很麻烦。
·多线程环境下的hash表,最好的还是tbb::concurent_hash_map。
5、核心的线程是事件线程:
·事件线程是调用epoll_wait()等待事件的线程。例子代码里面,一个线程干了所有的事情,而需要开发一个高性能的服务器的时候,事件线程应该专注于事件本身的处理,将触发事件的socket句柄放到对应的处理队列中去,由具体的处理线程负责具体的工作。
6、accept()单独一个线程:
·服务端的socket句柄(就是调用bind()和listen()的这个)最好在单独的一个线程里面做accept(),阻塞还是非阻塞都无所谓,相比整个服务器的通讯,用户接入的动作只是很小一部分。而且,accept()不放在事件线程的循环里面,减少了判断。
7、接收线程单独一个:
·接收线程从发生EPOLLIN事件的队列中取出socket句柄,然后在这个句柄上调用recv接收数据,直到缓冲区没有数据为止。接收到的数据写入以socket为键的hash表中,hash表中有一个自增长的缓冲区,保存了客户端发过来的数据。
·这样的处理方式适合于客户端发来的数据很小的应用,比如HTTP服务器之类;假设是文件上传的服务器,则接受线程会一直处理某个连接的海量数据,其他客户端的数据处理产生了饥饿。所以,如果是文件上传服务器一类的场景,就不能这样设计。
8、发送线程单独一个:
·发送线程从发送队列获取需要发送数据的SOCKET句柄,在这些句柄上调用send()将数据发到客户端。队列中指保存了SOCKET句柄,具体的信息 还需要通过socket句柄在hash表中查找,定位到具体的对象。如同上面所讲,客户端信息的对象不但有一个变长的接收数据缓冲区,还有一个变长的发送 数据缓冲区。具体的工作线程发送数据的时候并不直接调用send()函数,而是将数据写到发送数据缓冲区,然后把SOCKET句柄放到发送线程队列。
·SOCKET句柄放到发送线程队列的另一种情况是:事件线程中发生了EPOLLOUT事件,说明TCP的发送缓冲区又有了可用的空间,这个时候可以把SOCKET句柄放到发送线程队列,一边触发send()的调用;
·需要注意的是:发送线程发送大量数据的时候,当频繁调用send()直到TCP的发送缓冲区满后,便无法再发送了。这个时候如果循环等待,则其他用户的 发送工作受到影响;如果不继续发送,则EPOLL的ET模式可能不会再产生事件。解决这个问题的办法是在发送线程内再建立队列,或者在用户信息对象上设置 标志,等到线程空闲的时候,再去继续发送这些未发送完成的数据。
9、需要一个定时器线程:
·一位将epoll使用的高手说道:“单纯靠epoll来管理描述符不泄露几乎是不可能的。完全解决方案很简单,就是对每个fd设置超时时间,如果超过timeout的时间,这个fd没有活跃过,就close掉”。
·所以,定时器线程定期轮训整个hash表,检查socket是否在规定的时间内未活动。未活动的SOCKET认为是超时,然后服务器主动关闭句柄,回收资源。
10、多个工作线程:
·工作线程由接收线程去触发:每次接收线程收到数据后,将有数据的SOCKET句柄放入一个工作队列中;工作线程再从工作队列获取SOCKET句柄,查询hash表,定位到用户信息对象,处理业务逻辑。
·工作线程如果需要发送数据,先把数据写入用户信息对象的发送缓冲区,然后把SOCKET句柄放到发送线程队列中去。
·对于任务队列,接收线程是生产者,多个工作线程是消费者;对于发送线程队列,多个工作线程是生产者,发送线程是消费者。在这里需要注意锁的问题,如果采用tbb::concurrent_queue,会轻松很多。
11、仅仅只用scoket句柄作为hash表的键,并不够:
·假设这样一种情况:事件线程刚把某SOCKET因发生EPOLLIN事件放入了接收队列,可是随即客户端异常断开了,事件线程又因为EPOLLERR事 件删除了hash表中的这一项。假设接收队列很长,发生异常的SOCKET还在队列中,等到接收线程处理到这个SOCKET的时候,并不能通过 SOCKET句柄索引到hash表中的对象。
·索引不到的情况也好处理,难点就在于,这个SOCKET句柄立即被另一个客户端使用了,接入线程为这个SCOKET建立了hash表中的某个对象。此时,句柄相同的两个SOCKET,其实已经是不同的两个客户端了。极端情况下,这种情况是可能发生的。
·解决的办法是,使用socket fd + sequence为hash表的键,sequence由接入线程在每次accept()后将一个整型值累加而得到。这样,就算SOCKET句柄被重用,也不会发生问题了。
12、监控,需要考虑:
·框架中最容易出问题的是工作线程:工作线程的处理速度太慢,就会使得各个队列暴涨,最终导致服务器崩溃。因此必须要限制每个队列允许的最大大小,且需要监视每个工作线程的处理时间,超过这个时间就应该采用某个办法结束掉工作线程。
posted @
2011-04-21 21:40 小阮 阅读(942) |
评论 (0) |
编辑 收藏