2011年2月13日
摘要: 这两天又重新看了一下有关并查集的题目，相关的可以参考大牛的博客
http://hi.baidu.com/czyuan_acm/blog/item/531c07afdc7d6fc57cd92ab1.html
以下是自己的一点总结。
数据结构——并查集的应用
并查集是一种简单的数据结构，相对于其他数据结构来说，编程难度很小，也很灵活，适当的find函数与Union函数便可以解决很多问题。
...
阅读全文
2010年8月9日
1227图论，
给出一些点和点之间的无向边，问能否找到一条有向路径其长度大于等于指定长度
分析:如果图中有环路，则一定可以（有环路说明可以绕着该环一直走）
或者存在一条长度大于等于指定长度的一条通路。
竟然发现自己不会在图中找环，写了近两个小时都没把这个找环的内容处理好。
还是从网上荡下来一个。
从每个点开始做一遍dfs找到最大若有点回到该点则说明有环路，
要么就dfs出一条最长的通路。
1
#include<cstdio>
2#include<cstring>
3using namespace std;
4#define MN 101
5int map[MN][MN];
6int flag[MN];
7int n,root,cost,f;
8void dfs(int x,int s)
9
{
10
if(f)
11 return ;
12 if(s>=cost)
13
{
14 f=1;
15 return ;
16
}
17 for(int i=1;i<=n;i++)
18 {
19 if(!flag[i]&&map[x][i])
20 {
21 int tmp=map[x][i];
22 map[x][i]=map[i][x]=0; //选择了该条边在最长路上
23 flag[i]=1;
24 if(i==root) //有环路
25 {
26 f=1;
27 return ;
28 }
29 dfs(i,s+tmp);
30 map[x][i]=map[i][x]=tmp; //不选择这条边在最长路上
31 flag[i]=0;
32 if(f)
33 return;
34 }
35 }
36
}
37int main()
38{
39 int m,i,a,b,d;
40 while(scanf("%d%d%d",&n,&m,&cost)!=EOF)
41 {
42 memset(flag,0,sizeof(flag));
43 memset(map,0,sizeof(map));
44 f=0;
45 for(i=0;i<m;i++)
46 {
47 scanf("%d%d%d",&a,&b,&d);
48 if(!map[a][b])
49 map[a][b]=map[b][a]=d;
50 else
51 f=1;
52 }
53 for(i=1;i<=n&&!f;i++)
54 {
55 memset(flag,0,sizeof(flag));
56 root=i;
57 dfs(i,0);
58 }
59 if(f)
60 puts("YES");
61 else
62 puts("NO");
63 }
64 return 0;
65}
2010年7月31日
网络流
很多问题都可以转化成网络流问题，如运输货物时的物流问题，水流问题，匹配问题等等。网络是一个各条边都有权值和方向的图。
网络流问题，一般情况下我们会把各种网络问题抽象成网络流问题，网络流是满足以下性质的网络：每一条边拥有一个最大的容量c，即该条边可以容纳的最大流量，f是流过该边的实际流量，且总有f<=c。对于图中每个顶点（源点和汇点除外）都有流出的流量等于流入的流量。图中只有一个源点一个汇点，且对于源点来说其流入量为0，对于汇点来说流出量为0，源点的流出量等于汇点的流入量，对于最大流问题既是要找出流入汇点的最大流量值。
求最大流的算法：
EK算法：EK算法中涉及的三个关键词：残留网络，增广路，割。
残留网络，假定我们已经找到了一个可行的流，那么对于每条边如果流量小于容量则表示该条边有剩余，以流的流量我们也可以看成是反向的残留，得到一个残留网络。
增广路：在残留网络中如果可以找到一条从源点到汇点的路，即为增广路，我们就可以将流值增加这条增广路上的最小边。
EK算法就是在残留网络中寻找增广路使得流值不断增大，直至达到最大为止。
Ek算法由于在寻找增广路时具有盲目性，算法效率不高。
Dinic算法：基于EK算法的思想，再从源点到汇点做bfs来寻找路时，对各点标一个层次值表示从源点到该点所需的最小步数，然后在这些层次的基础上做dfs，dfs的时候只能到其下一层的点，且容量需要比已流流量大，然后重复上述过程即可得到解。
最大流和最小割，如果我们想要把一个网络分成两部分，一部分包含源点s，另一部分包含汇点t，我们把这个集合之间，从源集合到汇集合之间的正向流量之和，称为是网络的割，而一个网络的割中最小的那个，我们称之为最小割。
最大流最小割定理：一个网络的最小割等于最大流。
最小费用最大流：在保证最大流的情形下，网络中的边，可能不只有流量还有费用，那么如果我们一方面希望网络拥有最大流，另一方面我们要求费用达到最小，这就是一个费用流的问题了，对于费用流的问题，事实上我们可以这么考虑，首先我们必须要找到的是最大流，另一方面我们需要费用最小，而在找最大流的时候我们总是在寻找增广路来增广，来使得我们能得到一个比现在更大的流，那么另一方面要求费用最小，所以我们可以在寻找增广路的时候找一条费用最小路来增广，而费用我们也可以看成是距离类的东西，也就是这样的话，我们可以用最短路，来找出这样一个最小费用的路来进行增广，而不断增广，即可得到最大流，这样我们就可以得到最小费用最大流。
网络流和费用流中经常会涉及到拆点的操作，将一个点分成入和出，来拆成两个点。例如联合训练赛的第六场第一个题目tour，给出一张图，要求将这个图划分成几个集合，要求每个集合的点的个数大于等于2，要求这个集合所有点可以构成一个环。图中的每条边都有一个边权，最后找到各个集合的总花费为所有构成环的边的权之和。要求这个花费最小。分析题目可以知道，我们最后分成各个集合之后一定是每个点的出度和入度都为1，所以这个题经过拆点之后就是最小权匹配问题，用km算法即可解决，当然我们也可以将它转化成一费用流问题，将图中的每个节点都拆成入和出两个点，增加源和汇，源点到进入的点连一条费用为0，流量为1的边，从出点到汇连一条费用为0，流量为1的边，原图中的边都练成费用为边权，流量为1的边 ，最后只要求这个网络的最小费用流即可。另外对于一些题是点权而不是边权的题目，也可以通过拆点来将点权转化成边权。所以拆点的想法在网络流中十分重要。
2010年7月18日星期六
Question1：n个人围着一个桌子坐，每个人都有一个需求，假如一个人的需求是1，2，就表示他希望1，2坐在他的两边，若每个人的需要都可以满足，则我们需要求出 最少移动几个人可以达到每个人的要求都满足的状态（假定一开始的座位顺序为1，2，3，4，……，n）
分析：我们可以通过dfs找到一条闭合的回路即最终的状态，要想求出最少移动人数实际上就要找出最小的错排数，由于是圆桌旋转会出现另外的最优状态，所以一方面我们可以通过从每一个位置开始做起始点求一遍错排数，然后求出最小的错排数即为结果，但是这样做的复杂度是O(n^2)在题目（10^6）的数据范围下时间是难以承受的。
策略：分析中提到我们需要找出以各个点做起始点不同的错排的数目，事实上我们只要记录每个点它在哪一个位置在起始状态下是正确排的就可以了，这样的话我们就可以得到在不同起始状态下正确点的个数，即可以得到错排数。所以我们只需要扫描一遍，若一个点离它正确位置为k，即它在旋转了k个数的状态下是正确排列的，所以cnt[k]++,最后n-max(cnt[k])即为题目的解。
讲题人：rupxup
Question2：对于a,b,e,f整四个整数求最小的整数c使得存在d满足a/b<c/d<e/f.
分析：由题目可知事实上在c最小的情况下，也可以找到一个最小的d，这两个问题是相通的，我们先看两种特殊的情况：
a：a/b<1<e/f则存在c=1，d=1为题的解。
b：a/b=0，则存在c=1,d=f/e的下取整+1为题的解。
策略：对于上述两种特殊情况可以直接给出解，需要看其它情况可不可能转化成这两种特殊的情况，1.对于1<a/b<e/f,对于这种情况我们可以通过将等式两边同时减去这个整数来转化，可能出现上述a那种特殊状态，则得解c=1+k*d,d=1,即c=1+k;也有可能得到下述情况2.
2.对于a/b<e/f<1的情况可以通过求倒数之后化作1的情况，故1，2两种非特殊情况可以相互转化而且必然会转化到某一个特殊的状态，不断的在减，如果中间没有达到特殊状态a，也一定会达到特殊状态b的。
讲题人：rupxup
Question3:一只蚂蚁在一个木棍上爬，若这个蚂蚁的速度为v，木棍每分钟长长m，（相对的长长，向两端长长，蚂蚁的相对位置会保持，如原先在1/2处长长后蚂蚁还是在木棍1/2处），给出v和m和原始木棍长l，问是否蚂蚁是否有可能从最开始的一端爬到另一端。
题解：蚂蚁在木棍上的比例是不变的，只要蚂蚁在前进的过程中速度大于0，比例总是在增加，它就一定能爬到另一端。
讲题人：Abbie
Question4：给出原来有V升水，淘衣服上的洗衣粉，最多可以把洗衣粉分成n份，每次淘完还会残留b升脏水，问最多淘多少次，可以使得残留最少。
题解：事实上n次的时候残留最少，这是一个不断稀释的过程，用同样多的水稀释溶液，这个次数进行的越多，最后的溶液越稀。
PS：其实洗衣服可以多淘几次少用水的。
讲题人：Abbie
Question5：笔记本放置问题，给你一个方桌，一个矩形，问最少覆盖多少桌面能把这个矩形放到桌面上。
策略：让矩形的中心位于方桌的一个角上所覆盖的面积会最小。
讲题人：Abbie
Question6：一遍dfs求强联通分量。我们在求强联通分量时，一般是把原图做一遍dfs，记录下各个点的访问结束时间，然后以访问结束时间的降序，将反向图做一遍dfs。下面是一种可以一遍dfs求出强联通分量的算法。
相关内容：我们在求一个图中的割点割边时，用一个数组dep表示点的访问时间，数组low表示其儿子可以到达的最浅位置，若low[v]>=dep[u](其实也是low[u]>=dep[u])时该点是割点，这么说实际上割点的low和dep相等，我们考虑一个图，若一个点是割点，则说明其儿子可以到达的最小深度也为它，这么说事实上它的这些儿子是可以通过它相互可达的。所以对于一个割点构成的分量若low值都等于割点的dep值，则这可以构成一个强联通分量。
PS:不是太懂。
讲题人：brent
Question7:单调队列在dp中的运用。
一些时候我们的dp方程中会出现一个值与它之前的多个值相关，这时候很多情况下会出现重复计算问题，比如每个数与它上个状态的它的前面所有状态有关，则我们每次都要从头来枚举这些值，事实上我们进行了比较之后可以记录当前的最优值，下次只需要比较最优值和新增值即可。对于有限定如和它前k个数有关，我们就可以用单调队列，来使用O(1)的时间来随时得到这个最大值。
讲题人：czz
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 100005
int tree[20][MAX]; //表示每一层每个位置的值
int sorted[MAX]; //已排好序的序列
int toleft[20][MAX]; //表示它在一个子区间内从1到i有多少个数会被分到左边
void build(int l,int r,int dep) //建树
{
if(l==r) return;
int mid,i,same,lpos,rpos;
mid=(l+r)>>1;
for(i=l,same=0;i<=r;i++)
same+=(tree[dep][i]<sorted[mid]);
same=mid-l+1-same; //same表示和中间的数大小一样且会被分到左边的数的个数
for(i=l,lpos=l,rpos=mid+1;i<=r;i++)
{
if(tree[dep][i]<sorted[mid]) //比中间的数小，显然应该放在左边
tree[dep+1][lpos++]=tree[dep][i];
else if(tree[dep][i]==sorted[mid]&&same) //和中间的数一样大，但是same不为0，即还可以放一样的，则放在左边
{
tree[dep+1][lpos++]=tree[dep][i];
same--;
}
else //比中间的数大，显然要放在右边
tree[dep+1][rpos++]=tree[dep][i];
toleft[dep][i]=toleft[dep][l-1]+lpos-l; //从1到i被放在左边的数的个数
}
build(l,mid,dep+1); //递归的去做
build(mid+1,r,dep+1);
}
//查询某个区间第K大数，L,R是大区间，l和r是要查询的小区间
int query(int L,int R,int l,int r,int dep,int k)
{
//关键是newl和newr的计算，要仔细
if(l==r) return tree[dep][l];
int mid,i,newl,newr,cnt;
mid=(L+R)>>1;
cnt=toleft[dep][r]-toleft[dep][l-1];
if(cnt>=k) //有大于或等于k个数倍放在左边，则上左边去找
{
//L+在要查询的这段区间之前，这些数被放到左边几个
newl=L+toleft[dep][l-1]-toleft[dep][L-1];
//做端点加上会被放到左边的这几个数-1，就是右端点
newr=newl+cnt-1;
return query(L,mid,newl,newr,dep+1,k);
}
else
{ //先找出右端点通过右端点得到左端点。
newr=r+toleft[dep][R]-toleft[dep][r];
newl=newr-(r-l-cnt);
return query(mid+1,R,newl,newr,dep+1,k-cnt);
}
}
int main()
{
int n,q,i,a;
while(scanf("%d%d",&n,&q)!=EOF)
{
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++)
{
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0);
for(i=0;i<q;i++)
{
int b,k;
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",query(1,n,a,b,0,k));
}
}
return 0;
}
摘要: /*混合图的欧拉回路 混合图欧拉回路原来混合图欧拉回路用的是网络流。把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>...
阅读全文
2010年7月12日
求割边割点
对于一个连通图，删去某个点（删去一个点即把该点和与该点相邻接的边都删去）的集合得到的图将不再连通，删去该集合的任意子集该图依然连通，则称其为该图的一个点割集，若该集合只有一个点组成，则称其为割点。
同样对于一个连通图删去某个边的集合（删去一条边仅删去该条边即可）得到的图将不再连通，删去该边集合的任意子集该图依然连通，则称其为该图的边割集，若该集合只有一条边组成，则称其为割边即桥。
求割边割点最直接的方法就是按照定义，删去点或边然后对图进行遍历，看是否仍连通，但要求一个图的割点割边对整个图的每个点和每条边都需要做一下试探，时间复杂度太高。
求割边割点的过程，以某一个点开始做dfs，采用数组low[i],dep[i]表示一个节点可以到达的除其父亲外的最早被访问的点，dep表示该点的深度。
若有节点u有子节点v，且low[v]>=dep[u]则点u是割点。
若有low[v]>dep[u]则边(u,v)为割边.
1int low[MAX],dep[MAX],mark[MAX],cutpoint[MAX];
2void dfs(int s,int father,int depth)
3{
4 int u,v,tot=0;
5 mark[s]=1;
6 low[s]=dep[s]=depth;
7 for(int i=0;i<mp[s].size();i++)
8 {
9 v=mp[s][i];
10 if(mark[v]==1&&v!=father&&dep[v]<low[s])
11 low[s]=dep[v];
12 else if(mark[v]==0)
13 {
14 tot++;
15 dfs(v,s,depth+1)
16 if(low[v]<low[s])
17 low[s]=low[v];
18 if((s==root&&tot>1)||(s!=root&&low[v]>=dep[s]))
19 cutpoint[s]=1;
20 if(low[v]>dep[s])
21 //标记边（s，v）为割边
22 }
23 }
24 mark[s]=2;
25}
26
27
2010年5月23日
/*3514. River Pollution
Accepted
2010 5 23
一道用线段树求矩形并的题目。
http://acm.tju.edu.cn/toj/showp.php?pid=3514
题目：受污染的河流会污染到它周围的村庄，给出河流的坐标求受污染的村庄的总数。
求矩形的并的方法：
将矩形的平行于y轴或者说平行于列的边，按照x从小到大排列。
然后求面积时，就分别求所到的边，与上一个边在y轴上覆盖了多长，用这个长度乘以
这两条边之间的x轴上的距离，搜索所有的边，就可以求的矩形并的面积。
在我们求在y轴上覆盖了多长的时候，可以用线段树来处理。当数据过大或不一定为整数时
还需要加上离散化。
ps:因为一小点错，错了一下午，刷了一片wrong answer。还好最后这个小问题还是被我给发现了。
坚持就是胜利啊。*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct seg
{
int x,y1,y2;
int flag;
seg(){}
seg(int _x,int _y1,int _y2,int _f): x(_x),y1(_y1), y2(_y2), flag(_f){}
bool operator < ( const seg& a) const
{
return x < a.x;
}
}Edge[40005];
int f[600005];
int m[600005];
void update(int left,int right,int step)
{
if(left==right-1)
{
if(f[step]>0)
m[step]=1;
else
m[step]=0;
return ;
}
if(f[step]>0)
m[step]=right-left;
else
m[step]=m[2*step]+m[step*2+1];
}
void Buildtree(int left,int right,int l,int r,int c,int step)
{
if(left==right-1)
{
f[step]+=c;
update(left,right,step);
return ;
}
if(left==l&&right==r)
{
f[step]+=c;
update(left,right,step);
return ;
}
else
{
int mid=(left+right)>>1;
if(r<=mid)
Buildtree(left,mid,l,r,c,2*step);
else if(l>=mid)
Buildtree(mid,right,l,r,c,2*step+1);
else
{
Buildtree(left,mid,l,mid,c,2*step);
Buildtree(mid,right,mid,r,c,2*step+1);
}
update(left,right,step);
return ;
}
}
int main()
{
int t,n,x1,y1,x2,y2,i,j,my,pre;
long long ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(f,0,sizeof(f));
memset(m,0,sizeof(m));
j=my=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==x2)
{
if(y1>y2) swap(y1,y2);
Edge[j++]=seg(x1-1,y1,y2,1);
Edge[j++]=seg(x1+1,y1,y2,-1);
}
else if(y1==y2)
{
if(x1>x2) swap(x1,x2);
Edge[j++]=seg(x1,y1-1,y1+1,1);
Edge[j++]=seg(x2,y1-1,y1+1,-1);
}
my=max(y2,my);
}
sort(Edge,Edge+j);
ans=0;
pre=Edge[0].x;
for(i=0;i<j;i++)
{
ans+=m[1]*(Edge[i].x-pre);
Buildtree(0,my+2,Edge[i].y1,Edge[i].y2,Edge[i].flag,1);
pre=Edge[i].x;
}
cout<<ans<<endl;
}
return 0;
}
2010年5月13日
摘要: 1924 jungle road
#include<iostream>#include<cstring>using namespace std; int path[30][30];int cost[30];int flag[30];int prim(int n){ &nb...
阅读全文