#
这是我们队第二场多校联合的比赛，虽然比赛不是太顺利，但还是出了三题，排名50+。赛前还是按照惯例分题，我看后面，小波波看前面，阿登中间，我先看到1009，发现是个背包问题（貌似又加深了点），就扔给了小波波，小波波说第一题是个图的问题，于是我们交换了题目，我看第一题，小波波看第九题，这个时候阿登说1005是个计算几何，就先开始敲了，看完第一题，我发现实在是没有想法，于是就看了一下当时过得也比较多的1004，看完之后发现是个拆点的最小割，而且比较确定了，由于机器有人在用，我先看了别的题目，后来阿登的代码敲好了，交上去wa,小波波开始敲他的DP,考虑了很多种特殊情况之后，1Y了，然后我开始敲最小割，拆点，半个小时之后也过掉了。这时阿登还在改代码，我和小波波开始想别的可做的题，于是看到了1010，刚开始的时候对题意不是太了解，过了将近2个小时之后才发现clarification里面有人问星星的光线是不是平行光，admin的回答是YES,于是就豁然开朗了，一个简单的公式，秒杀。之后的过程比较无奈，阿登的计算几何题交了好多次都没过，可能是精度的原因，第一题到最后一个小时有40个人过，可是我们却没有想法，赛后问了问，发现原来这道题在FOJ专场出现过类似的题目，囧。难怪被人秒。。。
这次比赛暴露了我们的一个小弱点，就是第一个小时抢题的能力较弱，我记得我们是在1个小时以后才出的第一题，这个以后要加强训练。
摘要: 此题如果一下子想到了思路确实是应该很快出的，这题暴露了我基本功不扎实的弱点，对qsort中cmp函数和sort中cmp函数的使用没有完全弄明白，通过这题终于搞明白了啊，初学者如果只是按网上的写法套个模板还是远远不够的，因为解决的问题是在不断变化的，一定要深入研究其原理，才能遇神杀神，遇佛杀佛。 ...
阅读全文
今天是我们第一次参加多校联合集训的比赛，比赛开始前，我们还是按照以前的惯例进行分题，我看后面，小波波看前面，阿登看中间，大概十分钟以后，我们看了下board,发现1001和1008已经有人过了（快得令人汗颜啊…）,于是我们马上开始看1008，题意大概是给你N个数，这N个数只能是0或者是1，题目让你求出不包含101的数字串有多少个。起初我们想用数学方法去计算，但是发现去重很麻烦，一时卡住了，后来小波波突然想到一个dp的方法，AC了。然后大家开始看1001，小波波想到如果所有的结点被扩展的时候花费的步数是偶数，那么输出YES,否则NO,但是用DFS穷搜所有路径的想法复杂度太高被我否决掉了，既然DFS不行，BFS行不行呢，其实结点只需要最多扩展两次就行了，如果对原图进行一下BFS复杂度大概只需要O(n)，我和阿登合计了一下，觉得可行，然后阿登就开始敲了。我和小波波开始看其他题目，我看了1007，小波波看1005，1005要求good sequences,推公式，既然要都相同或者都不相同，那么对M做一个全排列是满足要求的，还有就是所有数是一样的也满足要求，我想了一下，也没发现什么反例，这个时候阿登的代码敲好了，但是一开始wa,我们把代码发到阿登机器上再检查一下，小波波先写代码，提交，不过一开始wa了，是算法还是特殊数据的问题？这个时候阿登说他找到了源程序里面的Bug,提交，过了。对于1005，我们发现一组特例，就是当n等于1, 其实对它做全排列和所有数字都一样其实是一种情况，另外还有一种M等于2的情况也是特例，改了一下，也过了。我一直在考虑1007其实就是一个比较典型的行列转换的问题，我记得以前在FOJ上做过，刘汝佳的书上也有提到，当时是用双向广搜，但是n,m<10,而这道题n,m<=100，用搜索肯定不行，怎么办呢，把原矩阵的第一列全部处理成0，然后用枚举目标矩阵中的每一列，再列进行排序，如果排序后两个矩阵完全相等，输出YES.这题敲代码也确实比较快，但是交上去却wa了，于是我和小波波一起逐行检查，终于发现原来是一个<=写成<了，囧啊！改了之后就过了。。。无语。我在查代码的时候，阿登看了1009，说是线段树，于是我把代码发到自己机器上，阿登开始写线段树，刚开始过这道题的人很少，就寥寥几个，但是阿登非常确定是线段树，那就敲吧。在我过了1007之后没多少时间，1009也过了。这时比赛还有大概一个小时吧，我们想再开一题，于是就各自看了几道AC率比较低的题目，阿登看了下最后一题说最后一题可以做，就是用链表模拟一下，但是对于取反操作，如果用单链表的话，一次取反操作复杂度是N，操作次数一多肯定超时，这题有点遗憾，我当时再看1003，等我看完最后一题，我觉得其实可以用双向链表的，后来大家也觉得双向链应该是正解，但是却没有时间了，只能赛后再研究下了.
定义：
欧拉回路：每条边恰好只走一次，并能回到出发点的路径
欧拉路径：经过每一条边一次，但是不要求回到起始点
①首先看欧拉回路存在性的判定：
一、无向图
每个顶点的度数都是偶数，则存在欧拉回路。
二、有向图（所有边都是单向的）
每个节顶点的入度都等于出度，则存在欧拉回路。
三.混合图欧拉回路
混合图欧拉回路用的是网络流。
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
②.欧拉路径存在性的判定
一。无向图
一个无向图存在欧拉路径，当且仅当 该图所有顶点的度数为偶数 或者 除了两个度数为奇数外其余的全是偶数。
二。有向图
一个有向图存在欧拉路径，当且仅当 该图所有顶点的度数为零 或者 一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。
三。混合图欧拉路径
其实整篇文章只有这部分是我写的哈，灰常不好意思，只是网上的同志们写的太好了，实在没有必要重复劳动，不知道大家有没有发现，求欧拉路径的第一步一定是求欧拉回路，在混合图上也不例外，如何判断混合图欧拉回路问题的存在性呢？首先，我们用上文所说的方法判断该图是否存在欧拉回路，如果存在，欧拉路径一定存在。如果欧拉回路不存在，那么我们枚举欧拉路径的起点和终点，连接一条无向边，然后再用最大流判断是否存在欧拉回路即可。
OJ上的几道题 ：POJ 1386 HDOJ 3472
网络流
题目描述：已知之前的一些比赛双方和结果，和未来的赛事安排，问DD能否夺冠，不能并列
我们谈心的让未来DD参加的比赛都赢，且我们可以知道未来每个人最多可以赢几场
给所有选手编号，预先统计出所有选手已经胜利的场次，然后对所有还没有进行的比赛，假设其中任意一个选手获胜，并统计胜负关系，（加入每个人胜利的次数在w[]中，每两个选手互相对战胜利的次数在a[][]中）即某两个选手a,b进行比赛a赢b的次数和b赢a的次数，这里要注意的是两个选手进行比赛，你假设任意一个选手获胜都是正确的，待会你会发现其实假设仅仅只是假设。增加超级源超级汇，超级源向每一个结点射出一条容量是这个点胜利场次的边，所有的点向汇点连一条容量是w[ID[DD]]-1的边，显然是为了限制每个点的胜利次数不能大于等于DD.中间任意两个结点根据胜负关系建立一条容量是a[i][j]的边，跑一遍最大流即可，如果满流，说明有可行解，否则无解。
下面来分析一下构图的原理，超级源向所有选手连一条容量是他将要获胜场次的边，比如说是c，说明这个选手有c场胜利要分配，如果这条边上的流量直接流向了汇点，说明该选手获胜，如果流量通过有向边流向了他的对手，说明这个胜利果实被他的对手拿走了，也就是实际上输掉了比赛，所以我才说假设仅仅是假设。再加上有每个点到汇点的限流，跑一遍最大流如果能满流说明比赛可以合理的分配胜负关系使得每个人的胜利场次都不超过DD,如果不能，无解。
这题构图确实很精彩，赞！
摘要:
弄了一天，总算搞懂了扫描线是怎么回事，刚开始的时候在网上搜索，代码基本没有注释，很难看懂，随后搜索到了陈宏的论文，2页纸能写完的东西，他居然可以写那么长，粗略的扫描了一下，感觉原线段和超元线段的定义很不错，其他的实在讲的有点罗嗦就跳过了。鉴于以后还会有同样想要学习扫描线的同学，下面我来简单的介绍一...
阅读全文
摘要: 250 Points枚举每一个要求的数字，求它到左上角的最小步数即可。注意数字可以穿越边界。
#define INF 1000000000int n,m;int cnt(int x,int y){ int res=INF; if(abs...
阅读全文
原来网络流也能二分，今天终于见识了。。。
二分+最大流
题目大意：给定n个人m场比赛，问赢的最多的人最少赢几场
二分答案，增加源汇点，左边一排是比赛点，右边是球员，若有比赛，比赛向俩球员连容量为1的边
源点向比赛连容量为1的边，球员向汇点连容量为二分枚举值的边，判断是最大流是否等于比赛个数
网络流的构图真是个神奇的东西，我承认如果不看网上的解题报告，我真的很难想到，首先是题意不太明确，刚开始我还以为赢的最多的选手胜利的场次必须是最多的。。。但是从样例来看，貌似就算每个人都赢一场也会有冠军出现。。。说说我的理解吧，从超级源点引一条边至代表每场比赛的节点，限制每场比赛的胜利者只有一个人，这个流量如果在射出到某个选手的一条边中，代表这场比赛是他取胜。每个选手到汇点连一条二分枚举的边，就是限制胜利场次的上界，如果最后的最大流等于m,说明这m场比赛的的胜者可以合理的分配，如果不能，说明比赛不能正常进行。又可以分析得出，如果某一个二分值mid满足要求，那么比他大的值一定也满足要求。故可二分枚举答案。（PS:这题的复杂度应该是(10000+10000+2)^2*(m*2+m+n)*log 10000.总觉得要超时啊。。。难道数据弱了？）
int n,m;
struct node2
{
int a,b;
}re[100000];
bool check(int n,int m,int mid)
{
int i;
for(i=0;i<n+m+2;i++)
adj[i]=NULL;
len=0;
int s=n+m;
int t=s+1;
for(i=0;i<m;i++)
insert(s,i,1);
for(i=0;i<n;i++)
insert(m+i,t,mid);
for(i=0;i<m;i++)
{
insert(i,m+re[i].a,1);
insert(i,m+re[i].b,1);
}
return dinic(t+1,s,t)==m;
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf("%d%d",&re[i].a,&re[i].b);
re[i].a--;
re[i].b--;
}
int l=1,r=m;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(n,m,mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
题意就是N个学校，每个学校有一个编号，编号可以重复。现在要求每个学校有一个独立的编号，但是每个学校可以接受的编号有一个范围，在这个范围内，编号每变动1将付出的话费是D。求是否有可行方案并给出最小花费。
显然X部分是所有的学校，Y部分是新的编号，按顺序我们把学校设置成1—N,设置超级源点s,s向每个X侧的节点连一条费用是0，流量是1的边，把他们对应的编号设置成节点N+1- 2*N,X部和Y部的边用计算出来的花费连边，流量是1，Y部每个节点向t连一条费用是0流量是1的边，求最小费用最大流即可。
模板就不贴了，构图部分代码如下：
void creat(int n,int s,int t)
{
flowsum=0;
int a,b,c,d;
int i;
for(i=1;i<=n;i++)
{
insert(s,i,1,0);
insert(i+n,t,1,0);
scanf("%d%d%d%d",&a,&b,&c,&d);
int j;
for(j=b;j<=c;j++)
{
insert(i,j+n,1,abs(j-a)*d);
}
}
}
void init(int n)
{
int i;
for(i=0;i<n;i++)
adj[i]=NULL;
len=0;
}
int main()
{
int n;
int s,t;
scanf("%d",&n);
init(2*n+2);
s=0;
t=2*n+1;
creat(n,s,t);
int ans=mincostflow(t+1,s,t);
if(flowsum!=n)
printf("NIE\n");
else
printf("%d\n",ans);
return 0;
}
题目大意：n个小朋友投票，定义投票的冲突数为好友间发生冲突数加上所有和自己意愿发生冲突的人数，求冲突最少数
分析：增加源汇点，s向所有同意的连容1的边，所有反对的向t连容1的边，若俩人是好友，则相互连容1边
对于经过好友间的流量，表示着冲突，即可用冲突或改变意愿来替代，那么最小割就成了冲突数的定义
看到网上的几个代码都进行了拆点，我觉得似乎没有必要，直接构图，AC.看来感觉是对的，但我有些疑惑的是为什么要把正反两条边都建起来，后来想了一下，其实最小割模型中有个偏序的关系，模型的一侧是包含s的一组结点，右侧是包含t的一组结点，而SET(S)到SET(T)应该是相连的，而如果建成单相边的话，有可能导致S,T之间没有路径存在。而最小割中恰好又只取S->T的边，所以无论关系是怎样的，都可以满足要求，取两个朋友之间的一条边，此题得解。