最小费用最大流代码

Standard
class Node{
public:
	int f,n,c,w;
	Node *pr,*inv;
}*Adj[Nx];
inline void add(int u,int v,int c,int w){
Node *p=new Node;
	p->f=u,p->n=v,p->c=c,p->w=w;
	p->pr=Adj[u];
	Adj[u]=p;
	  p=new Node;
	p->f=v,p->n=u,p->c=0,p->w=-w;
	p->pr=Adj[v];
	Adj[v]=p;
	
	Adj[v]->inv=Adj[u];
	Adj[u]->inv=Adj[v];
}
Node *pr[Nx];
class Queue{
public:
	int li[Nx*100],h,t,MC[1000],Min[1000];
	bool Inq[Nx];
	bool spfa(){
		h=t=1;
		memset(MC,15,sizeof(MC));
		memset(Min,15,sizeof(Min));
		MC[S]=0;
		li[t++]=S;
		Inq[S]=true;
		while(hpr)
				if(p->c>0 && MC[p->n]>MC[H]+p->w){
					pr[p->n]=p;
					MC[p->n]=MC[H]+p->w;
					Min[p->n]=min(Min[H],p->c);
					if(!Inq[p->n]){
						Inq[p->n]=true;
						li[t++]=p->n;
					}
				}
			Inq[li[h++]]=false;
		}
		if(MC[T]==Inf)
			return false;
	Node *now=pr[T];
		MaxFlow+=Min[T];
		while(1){
			Cost+=Min[T]*now->w;
			now->c-=Min[T];
			now->inv->c+=Min[T];
			if(now->f==0)
				break;
			now=pr[now->f];
		}
		return true;
	}
}Q;

近期状态感想

Standard

NOI是在2013.7.14日开始,如今还剩1个多月的时间

做了几次比赛,APIO打酱油,才深切的发现各种不足,深感差距大,压力!
即使没有可能,但是为何要气馁,过程要比结果有意义的多!

[Contest Hunter]Katharon # 1 题解

Standard

比赛链接

内容提要:

  • Preprefix Sum
    红果果的线段树,只是交的时候用iostreamT了
  • 防御准备
    斜率优化动态规划,注意凸包的维护顺序
  • 国王奇遇记
  • 千钧一发
  • 决战

Preprefix Sum

在线段树中加入LSum标记表示前缀和,然后随便搞。

防御准备

1D/1D动态规划优化,容易得到决策是单调递减的,我采用的是斜率优化时间复杂度O(N),和经典问题不同的地方是这个问题动态维护凸包是逆时针的,而经典问题是顺时针的,所以二者用叉积判断方位会恰恰相反(只考虑两条边,如果考虑三条边的方位就没有变化)

f[i]=min( f[j]+ Cost(i,j) ) + A[i](A[i]是修建防御塔的费用)

经过转化得到
f[i]=min(↓↓↓↓) + A[i]
f[j]+((j-i)^2-j+i)/2
f[j]+(j^2-2ij+i^2-j+i)/2
f[j]+(j^2-j -2ij +i^2+i)/2
f[j]+(j^2-j)/2 -ij  +(i^2+i)/2

设Y=f[j]+(j^2-j)/2 X=j ,然后。。。就是经典问题,具体教程见《1D/1D动态规划优化初步》

国王奇遇记

千钧一发

决战

[APIO2012] 派遣

Standard

去年此时听说了左偏树,以为会很大神,现在看看,发现也是蛮简单的.

关于左偏树和可合并堆,网上有很多的资料,可自行查阅.

题目  题目大意:

给你一棵有根树,每个节点有两个属性:花费和领导力,现在要求选任意一棵子树中的点,使得(这棵子树中尽量选点而总花费不超过M能选的最多的点)*(这颗子树树根的领导力)最大

枚举树根是很显然的,但是选点呢?

容易想到把树中的点按照花费排序,然后尽量取小的,这样一定是最多的,但是这样怎么做呢?

每个节点开一棵左偏树,注意是大根堆,如果是小根堆尽量选小的点时需要删除,维护起来很麻烦,而大根堆的话,只需要比较如果堆的总和比M大,显然最大的那个点是没用的,所以就把它删掉,就这样删删删直到堆的和小于等于M,然后堆的大小就是最优值,每次递归回来合并一下就行了。

还有要注意一点,有两个点的数据是个 链+杂边 深度是99999,栈里面一定要少放东西(尤其是STL的东西),否则会爆栈爆到死。

APIO2013 结束

Standard

这次比赛又打酱油了,总分300,一共28分,第一题应该25分,第三题3分

其实我的比赛素养很差,原因如下:

  • 比赛环境不佳
    完全不会用VC++,也不会用DEV-CPP 调试,比赛时这些问题没办法解决,我们用了两年的MinGWStudio,对其他的IDE很不熟悉,没有办法调试只能用命令行gdb调试,我们一行对于这种问题浪费了大量的时间,极大的影响了心情。
  • 比赛策略不佳
    T1的30%是容易看出来的(但是没有考虑死循环的问题只有25),但是T2只是扫了一眼,根本没有看完就跳过了,而搞T3的时候不知怎么想的按照顺序从1开始搞,到第二个点就没搞出来,比赛时有些混乱,后来再看发现也是蛮简单的,除了卡ModifiedDijkstra以外应该都可以搞出来的,但是事实上只过了第一个点,而7,8两个点更是没看完就放弃了,是缺乏自信么?

虽然酱油的很彻底,但是没有理由灰心丧气,比赛时心态的影响还是很大的,剩下整整两个月的时间去改变,让我们拭目以待吧。

网络流问题类型

Standard

最大流问题

最小费用最大流

有容量下限的网络流

平面图求最小割

BJOI2006 狼抓兔子,NOI2010 海拔

最大权闭合子图

代表的问题有:太空飞行计划,NOI2009 植物大战僵尸

关于闭合图等等的概念详见国家集训队员胡博涛2007年的论文

做法:

  1. 新建两点s,t,分别表示源和汇,从s向所有点权为正的点连一条流量为该权的边,从所有点权为负的点连一条流量为 负该权 的边,我们要求的最优值就是 所有正值-新图从s到t的最大流

求最大权闭合子图可以这么理解:

  • 一个闭合子图对应一个“割”划分的S集合(包含源点的集合)
  • 最大流求出的是 不再最优的S集合中的正权值和 – 在最优的S集合中的负权值和
  • 我们要求 在最优的S集合中的(正权值和+负权值和)
  • 所以我们要求的是 所有正权值和-最大流

用网络流算法求解线性规划问题

代表的问题有:NOI2008志愿者招募  ZJOI2013防守战线

二分图最大匹配

二分图 最大点权独立集/最小点权覆盖集

hehe
hehe