SPOJ-Highways(HIGH)【行列式、Kirchhoff矩阵】

晚上看了会儿线代。

行列式的算法好多。可以根据2×2的矩阵行列式计算方法递归。可以用排列、逆序对的神方法算。

效率比较高的应该是基于行变换的一种算法。

A为一个方阵。

(a). 若A的某一行的倍数加到另一行得矩阵B,则detB=detA.

(b). 若A的两行互换得矩阵B,则detB=-detA.

(c). 若A的某行乘以k倍得到矩阵B,则detB=k*detA.

如果A为三角阵,则detA等于A的主对角线上元素的乘积。

那么我们只需要通过(a)(b)两种变换得到三角阵,计算m=主对角线上元素的乘积。

如果进行了n次(b)操作,那么detA=(-1)^n * m.

可以发现和高斯消元法还是有一些联系的。这种计算行列式的复杂度是O(n^3)。

 

这道题的题意就是求无向图的生成树个数。

用行列式计算。先构造Kirchhoff矩阵。

NOI2007《生成树计数》中有涉及到Kirchhoff矩阵。详细证明戳进来

按照这个方法构造。剩下的就是计算行列式了。

可以用double储存。这样(b)操作方便一些。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double a[20][20];
#define eps 1e-15
inline int dcmp(double p){
        if(fabs(p)<eps)return 0;
        return p>eps?1:-1;
}inline void gauss(int n){
	double tmp=1.0,an=1.0,p;
	for(int i=1,pos;i<=n;i++){
		for(pos=i;(!dcmp(a[pos][i]))&&pos<=n;pos++);
		if(pos>n)	continue;
		for(int j=i;j<=n;j++) swap(a[pos][j],a[i][j]);
		for(int j=i+1;j<=n;j++){
			if(dcmp(a[j][i])){
				if(dcmp(a[i][i])==0||dcmp(a[j][i])==0){	printf("0\n");	return;}
				tmp*=(p=a[i][i]/a[j][i]);
				for(int k=i;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k]*p;
			}
		}
	}for(int i=1;i<=n;i++)	an=an*a[i][i];
	if(n&1)	an*=-1;
	printf("%.0lf\n",fabs(an/tmp));
}int main(){
	int n,m,x,y,tc;	scanf("%d",&tc);
	while(tc--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	a[i][j]=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			a[x][y]=a[y][x]=-1;
			a[x][x]+=1;	a[y][y]+=1;
		}gauss(n-1);
	}return 0;
}

BZOJ1898: [Zjoi2004]Swamp 沼泽鳄鱼【矩阵乘法】

如果没有鳄鱼的话。就是求邻接矩阵的k次幂了。

有鳄鱼的话。比如在第i个时刻第j个点上有鳄鱼。那么把第i-1时刻的矩阵中[1..n][j]置零,第i时刻的矩阵中[j][1..n]置零。很好想通。

注意到T=2、3、4。lcm是12。那么整个周期就是12。K/12的用快速幂。K%12的暴力求。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,s,e,k,nf,fb[52][52]={0},p[52];
struct mtx{
	int num[52][52];
	mtx(){	memset(num,0,sizeof(num));}
}M[12],org;
mtx mul(mtx a,mtx b){
	mtx c;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%10000;
	return c;
}mtx pow(mtx a,int b){
	mtx c;
	for(int i=0;i<n;i++)	c.num[i][i]=1;
	while(b){
		if(b&1)	c=mul(c,a);
		b>>=1;
		a=mul(a,a);
	}return c;
}inline void clear1(int x,int y){
	for(int i=0;i<n;i++)	M[x].num[y][i]=0;
}inline void clear2(int x,int y){
	for(int i=0;i<n;i++)	M[x].num[i][y]=0;
}int main(){
	scanf("%d%d%d%d%d",&n,&m,&s,&e,&k);
	int x,y,t;
	for(int i=0;i<m;i++){
		scanf("%d%d",&x,&y);
		for(int j=0;j<12;j++)	M[j].num[x][y]=M[j].num[y][x]=1;
	}scanf("%d",&nf);
	for(int i=0;i<nf;i++){
		scanf("%d",&t);
		for(int j=0;j<t;j++)	scanf("%d",&p[j]);
		for(int j=0;j<12;j++)	fb[j][p[j%t]]=1;
	}for(int j=0;j<12;j++)
		for(int i=0;i<n;i++)	if(fb[j][i])	clear1(j,i),clear2((j+11)%12,i);
	for(int i=1;i<12;i++)	M[i]=mul(M[i-1],M[i]);
	if(k%12)	cout << mul(pow(M[11],k/12),M[k%12-1]).num[s][e] << endl;
	else		cout << pow(M[11],k/12).num[s][e] << endl;
	return 0;
}
 

BZOJ2756: [SCOI2012]奇怪的游戏【】

泥煤怎么会全WA呢。

回来再调。

备忘一下。

BZOJ2653: middle(陈立杰)【可持久化线段树+二分】

题意:给定一个序列,每次询问左端点在[a,b]中,右端点在[c,d]中的子序列中,最大的中位数。强制在线。

前几天做到与这道题有一点点类似的。那道题是给定一个序列,求多少个子序列的中位数大于等于给定值M。

这两道题中的中位数的定义都是一样的。设序列S从大到小排序后为S[1..k],中位数为M=S[k/2向上取整]。

那就意味着,在序列S中,大于等于M的数大于等于k/2。如果把序列S转化为T,T[i]=1(S[i]>=M),-1(S[i]<M),则ΣT[i]一定非负。

同理,如果对于任意一个M。将序列S转化为T之后,如果ΣT[i]非负。那么这个序列的中位数一定大于等于M。

 

回到这道题。我们可以先考虑一个弱版:只询问一次。

有了上面那道题的经验。对于M<M',如果发现中位数大于等于M',那一定也大于等于M。所以有单调性,很容易就想到了二分。二分M。得到T[]。因为要求了左端点和右端点。所以,如果能在满足要求的情况下找到这一段ΣT[i..j](i∈[a,b],j∈[c,d])非负,那么中位数一定就大于等于M了。所以,我们只需要求出符合要求的最大子序列和,看是不是非负即可。

感觉回到了GSS。线段树维护lmax,rmax,sum即可。因为有a<b<c<d,所以[a,b],[c,d]是互不包含的。最大连续子序列和就是[a,b]的rmax+(b,c)的sum+[c,d]的lmax。

另外n个数都是要离散化的这是必然的。二分的时候二分下标。

现在感觉已经很明了了。这样的话。二分logn。重建序列T和线段树nlogn。总复杂度是O(nlog^2n)。可以很好的解决一次询问。= =

 

多个询问怎么办。O(nqlog^2n)作死?其实瓶颈在这:为什么每次都要重建线段树?根本就不需要。

假设离散化的时候数值是从小到大排序的。那我们可以这么想,二分到M时,排序后的下标第1~M-1位上都是-1。第M~n位上都是1。然后还是跟上面一样的方法判定。

这就要用到函数式编程的思想。在原来的基础上不做修改,继续建树,也就是函数式线段树。

具体来说:初始的树,每个位置都是1。序列从小到大插入主席树时,修改第i棵树的时候,第i-1大的数的位置上改为-1。这样以此类推,就有n棵不同版本的线段树。

二分到M时,就在第M棵线段树上查询。可以保证此时下标为1~M-1的位置上的数都是-1。其余位置上都是1。这样就可以进行查询了。

这样就没问题了。二分logn。建函数式线段树nlogn。查询一次logn。总复杂度(nlogn+qlog^2n)。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	int sum,lmax,rmax;
	node(){};
	node(int s,int l,int r):sum(s),lmax(l),rmax(r){}; 
}seg[5000000],z;
int lc[5000000],rc[5000000],T[30000],q[4],ans=0,tot=0,n,Q;
pair<int,int>a[30000];
char buf[4000000],*pt=buf,*o=buf;
inline int getint(){
    int s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}
inline void print(int x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}*o++='\n';
}
inline node operator + (const node &a,const node &b){
	return node(a.sum+b.sum,max(a.lmax,a.sum+b.lmax),max(b.rmax,b.sum+a.rmax));
}void build(int l,int r,int &rt){
	rt=++tot;
	if(l==r){	seg[rt]=node(1,1,1);	return;}
	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}void modify(int p,int k,int v,int l,int r,int &rt){
	rt=++tot;
	lc[rt]=lc[p];	rc[rt]=rc[p];
	if(l==r){	seg[rt]=node(v,v,v);	return;}
	int m=l+r>>1;
	if(k<=m)	modify(lc[p],k,v,l,m,lc[rt]);
	else		modify(rc[p],k,v,m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}node ask(int L,int R,int l,int r,int rt){
	if(L>R)	return node(0,0,0); 
	if(L==l&&r==R)	return seg[rt];
	int m=l+r>>1;
	if(R<=m)	return ask(L,R,l,m,lc[rt]);
	else if(L>m)	return ask(L,R,m+1,r,rc[rt]);
	else	return ask(L,m,l,m,lc[rt])+ask(m+1,R,m+1,r,rc[rt]);
}inline int check(int k){
	return ask(q[0],q[1],0,n-1,T[k]).rmax+ask(q[1]+1,q[2]-1,0,n-1,T[k]).sum+ask(q[2],q[3],0,n-1,T[k]).lmax>=0;
}int main(){
	fread(buf,1,4000000,stdin);	n=getint();
	for(int i=0;i<n;i++)	a[a[i].second=i].first=getint();
	sort(a,a+n);			build(0,n-1,T[0]);
	for(int i=1;i<n;i++)	modify(T[i-1],a[i-1].second,-1,0,n-1,T[i]);
	Q=getint();
	while(Q--){
		q[0]=(getint()+ans)%n;	q[1]=(getint()+ans)%n;	q[2]=(getint()+ans)%n;	q[3]=(getint()+ans)%n;
		sort(q,q+4);
		int l=0,r=n-1,mid;
		while(l<=r)	if(check(mid=l+r>>1))	l=mid+1;	else	r=mid-1;
		print(ans=a[l-1].first);
	}return fwrite(buf,1,o-buf,stdout),0;
}

SPOJ-QTREE3(PT07J)【dfs序+可持久化线段树】

题意:给定一颗树。询问一个子树中第k大的节点。

 

【终于在0:02的时候A掉了=。=】

这几天复习一下数据结构。先复习POJ2104。写可持久化线段树练手先。

然后到了这道题。其实也蛮裸的。

先求出dfs序。记录每个节点开始和结束的时间戳。然后就相当于每个点开始到结束这个区间里求第2*k大。

然后就是一个主席树了。

根据JC大神的指点结束的时间戳不用占位置了,根据下一个开始的时间戳减一就行。这样可以省一半的空间,也可以省很多时间。

由于spoj太慢加了一个read。后来一不小心就A了。速度还行吧。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int w[200010],lc[2100010],rc[4100010],bin[100010],p[200010],n1[200010],h[100010],ee=0,tot;
int id[100010],sum[2100010],T[100010],num[100010],begin[100010],end[100010],n,c=0;
void read(int &x){
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-48;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}void dfs(int u,int fa){
	num[begin[u]=++c]=w[u];
	for(int i=h[u];~i;i=n1[i])	if(p[i]!=fa)	dfs(p[i],u);
	end[u]=c;
}void build(int l,int r,int &rt){
	rt=++tot;	sum[rt]=0;	if(l==r)	return;	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
}void modify(int p,int v,int l,int r,int &rt){
	rt=++tot;	sum[rt]=sum[p]+1;	lc[rt]=lc[p];	rc[rt]=rc[p];	
	if(l==r)	return;	int m=l+r>>1;
	if(v<=m)	modify(lc[p],v,l,m,lc[rt]);
	else		modify(rc[p],v,m+1,r,rc[rt]);
}int ask(int L,int R,int l,int r,int k){
	if(l==r)	return l;	int cnt=sum[lc[R]]-sum[lc[L]],m=l+r>>1;
	if(k<=cnt)	return ask(lc[L],lc[R],l,m,k);
	else		return ask(rc[L],rc[R],m+1,r,k-cnt);
}int main(){
	read(n);	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++)	read(w[i]),bin[i]=w[i];
	sort(bin+1,bin+n+1);
	int x,y;
	for(int i=1;i<=n;i++){	w[i]=lower_bound(bin+1,bin+n+1,w[i])-bin;id[w[i]]=i;}
	for(int i=1;i<n;i++)	read(x),read(y),ae(x,y);
	dfs(1,0);	build(1,n,T[0]);
	for(int i=1;i<=n;i++)	modify(T[i-1],num[i],1,n,T[i]);
	int	q;	read(q);
	while(q--){
		read(x);read(y);
		printf("%d\n",id[ask(T[begin[x]-1],T[end[x]],1,n,y)]);
	}return 0;
}

 

 

BZOJ2730: [HNOI2012]矿场搭建【tarjan求割点】

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

很容易的想到如果是割点塌掉的情况。

如果这个割点把整张图分裂了,那么就要保证每块里面都要装一个救援出口。

所以可以 这样做,先求出割点。然后dfs剩下的块。如果一个块只连接到了一个割点,那么这个块里面要有一个救援出口。否则就不用了。

如果没割点的话,要两个出口。不然有可能出口塌了= =。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[50010],n1[50010],h[10010],v[10010],dfn[10010],low[10010],b[10010];
int s[50010],c[50010],tmp[50010],m,n,ee,tot,col;long long An1,An2;
void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
}void dfs(int u){
	v[u]=1;dfn[u]=low[u]=++tot;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		dfs(p[i]);
		low[u]=min(low[u],low[p[i]]);
		if(low[p[i]]>=dfn[u])	b[u]++;
	}else	low[u]=min(low[u],dfn[p[i]]);
}void dfs2(int u){
	v[u]=1,s[col]++;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		if(!b[p[i]])	dfs2(p[i]);
		else	if(c[p[i]]!=col)	c[p[i]]=col,tmp[col]++;
	}
}void init(){
	memset(h,-1,sizeof(h));
	memset(v,0,sizeof(v));
	memset(b,0,sizeof(b));
	memset(v,0,sizeof(v));
	memset(c,0,sizeof(c));
	memset(s,0,sizeof(s));
	memset(tmp,0,sizeof(tmp));
	n=ee=tot=col=An1=0;An2=1;
}int main(){
	int tc=0;
	while(scanf("%d",&m),m){
		int x,y;init();
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			ae(x,y);ae(y,x);
			n=max(n,max(x,y));
		}for(int i=1;i<=n;i++)	if(!v[i]){
			dfs(i);b[i]--;
		}memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++)	if(!v[i]&&!b[i]){
			col++;dfs2(i);
			if(tmp[col]==1)	An1++,An2*=1ll*s[col];
		}if(col==1)	An1=2,An2=1ll*n*(n-1)>>1;
		printf("Case %d: %lld %lld\n",++tc,An1,An2);
	}return 0;
}

BSOJ3686 -- 【USACO 2011 November Gold】Above the Median【树状数组统计】

 

Description

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair. 

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

Input

* Line 1: Two space-separated integers: N and X.
* Lines 2..N+1: Line i+1 contains the single integer H_i.

Output

* Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

Sample Input

4 6
10
5
6
2

INPUT DETAILS:

FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

Sample Output

7

OUTPUT DETAILS:

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

题意:统计有几个连续子段的中位数(A[1..k]从大到小排序后A[k/2向上取整])大于等于给定值m。

 

应该还是比较好搞的。

把大于等于m的标记为1。小于m的标记为-1。

我们就只需要统计连续子段和非负的个数。

树状数组搞即可。

(新本本好好用。呵呵呵。)

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210000,d=100010;
int n,m,a[100010],bit[maxn+10]; 
void modify(int x){
	for(;x<=maxn;x+=x&-x)	bit[x]++;
}
int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r+=bit[x];
	return r;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>=m)	a[i]=1;	else a[i]=-1;
	}
	int sum=0;
	long long An=0;
	modify(d);
	for(int i=1;i<=n;i++){
		sum+=a[i];
		An+=1ll*ask(sum+d);
		modify(sum+d);
	}
	cout << An << endl;
	return 0;
}

 

 

BSOJ3411-【USACO 2009 January Gold】Safe Path【dijkstra+左偏树】

Safe Travel
Time Limit: 20000 ms Memory Limit: 65536 KB

Description
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:

Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output
3
3
6

 

由于题目说了1到没个点的最短路是唯一的。那么这些最短路组成的一棵树-Shortest Path Tree也是唯一的。

dijkstra+heap跑一遍。处理出dist数组。建好SPT。树根当然是1。

对于一个结点u。它的父亲设为p。那么根据题意,从1到u的次短路不能经过<p,u>这条边。

①先沿着SPT的边从1走到v。然后通过一条不是SPT的边,走到u本身。

②先沿着SPT的边从1走到v。然后通过一条不是SPT的边,走到u在SPT中的子孙,再沿着SPT上的边就可以走到u了。

 

考虑给每个节点挂一个可并堆。(二项堆写起来略烦,还是学习了左偏树)

 

先解决叶子节点u。

叶子节点肯定是上述的第①种情况。

那么把u出发的不是SPT的边<v,u,w>放入一个小根堆中。那么Ans[u]=min{dist[v]+w}。就是堆顶元素。

 

然后处理非叶子节点u'。

同样,把u'出发的不是SPT的边<v,u',w>放入一个小根堆中。

因为有情况②的存在,所以节点u'的堆要和它所有的儿子v'的堆合并。v'堆合并时要先加上<v',u'>的边权。然后再取出最大值。

 

为了方便起见,处理节点u时,添加非SPT中的边时,可以把key设为dist[v]+w(v,u)+dist[u]。

如果到了处理u'时取出这个答案的话,Ans[u']=key-dist[u']。(dist[u]-dist[u']就是上述的加上的边权,这样就不用每次合并的时候逐一加了)

 

还有就是要注意。如果堆顶选出来的这条非SPT边<u,v>,LCA(u,v)在是当前节点的祖先。那就不可行了。这样必定要经过<p,u>边。不合题意。所以不停地删,直到堆顶元素符合。

左偏树中删除堆顶节点的简单办法就是Merge(rt.l,rt.r)了~

 





#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110000,maxm = 510000,inf = 1061109657;
struct node{
    int x,dis;
    node(){};
    node(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (node b)const{
        return dis < b.dis;
    }
}H[maxn];
int pos[maxn]={0},rt[maxm],An[maxn],dfn[maxn],path[maxn],size = 0,ee = 0,cnt = 0;
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn],D[maxn],tot = 0,n,m;
struct lt{
    int l,r,d,id;
}L[maxm];
inline void sw(int a,int b){
    pos[H[a].x] = b;
    pos[H[b].x] = a;
    swap(H[a],H[b]);
}
#define pt (x >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void up(int x){
    if(x == 1)  return;
    if(H[x] < H[pt])    sw(x,pt),up(pt);
}
void down(int x){
    int s = x;
    if(ls <= size && H[ls] < H[x])  s = ls;
    if(rs <= size && H[rs] < H[s])  s = rs;
    if(s != x)  sw(x,s),down(s);
}
void del(int x){
    sw(x,size);
    size --;
    up(x);
    down(x);
}
void ins(node a){
    H[++ size] = a;
    pos[a.x] = size;
    up(size);
}
void dijkstra(int s){
    size = d[s] = 0;
    ins(node(s,0));
    while(size){
        node u = H[1];
        pos[H[1].x] = 0;
        del(1);
        if(vis[u.x])    continue;
        vis[u.x] = 1;
        for(int i = h[u.x];~i;i = n1[i])    if(!vis[p[i]])
            if(u.dis + w[i] < d[p[i]]){
                d[p[i]] = u.dis + w[i];
                path[p[i]] = u.x;
                if(pos[p[i]]){
                    H[pos[p[i]]].dis = d[p[i]];
                    up(pos[p[i]]);
                }else   ins(node(p[i],d[p[i]]));
            }
    }
}
inline void ae(int a,int b,int c){
    p[ee] = b;  w[ee] = c;  n1[ee] = h[a];  h[a] = ee ++;
    p[ee] = a;  w[ee] = c;  n1[ee] = h[b];  h[b] = ee ++;
}
int merge(int a,int b){
    if(!a || !b)    return max(a,b);
    if(L[a].d > L[b].d) swap(a,b);
    L[a].r = merge(L[a].r,b);
    if(D[L[a].r] > D[L[a].l])   swap(L[a].l,L[a].r);
    if(L[a].r == 0) D[a] = 0;
    else     D[a] = D[L[a].r] + 1;
    return a;
}
void dfs(int u,int fa){
    dfn[u] = ++ tot;
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] == u){
            dfs(p[i],u);
            rt[u] = merge(rt[u],rt[p[i]]);
        }
    }
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] != u){
            L[++ cnt] = (lt){0,0,d[u]+w[i]+d[p[i]],p[i]};
            rt[u] = merge(rt[u],cnt);
        }
    }
    while(rt[u] && dfn[L[rt[u]].id] >= dfn[u])
        rt[u] = merge(L[rt[u]].l,L[rt[u]].r);
    An[u] = rt[u] ? L[rt[u]].d - d[u] : -1;
}
    
int main(){
    memset(h,0xff,sizeof(h));
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i = 1;i <= m;i ++){
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);
    }
    memset(d,63,sizeof(d));
    dijkstra(1);
    dfs(1,0);
    for(int i = 2;i <= n;i ++)  printf("%d\n",An[i]);
    return 0;
}

 

 

BSOJ3701--【USACO 2012 Open】Bookshelf

Description
When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years, he has collected N books (1 <= N <= 2,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on. Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000). The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Please help FJ compute the minimum possible height for the entire set of bookshelves.
Input
* Line 1: Two space-separated integers: N and L.

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i) and W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Output
* Line 1: The minimum possible total height for the set of bookshelves.
Sample Input
5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books. Each shelf can have total width at most 10.
Sample Output
21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7), the second containing books 2..4 (height 13, width 9), and the third containing book 5 (height 3, width 8).

【Silver难度】:N<=2000

很容易就看出DP了。

令C[i]表示放到第i本书的最小代价。

很明显C[i] = min{max{H[j+1..i]} + C[j]}。(sigma{L[j+1..i]}<=L,0<=j<i)。

那么O(N^2)这道题就过了。

【Gold难度】:N<=100000

目前已被虐傻

BZOJ2466: [中山市选2009]树【高斯消元解异或方程组】

经典的开关问题的树上的版本。

还是赤果果的高斯消元。

多了一个细节是求出sigma(x[i])的最小值。

先跑高斯消元。得到倒三角矩阵之后。考虑到n=100。而且不确定位应该不会太多。(不然怎么过啊哦擦)。所以可以把每种解都跑出来。保留最小值。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[110][110],x[110],n,An = 1000000009;
void dfs(int k,int sum){
    if(sum >= An) return;
    if(k == 0){
        An = min(An,sum);
        return;
    }
    if(a[k][k]){
        int p = a[k][n + 1];
        for(int i = k + 1;i <= n;i ++)
            if(a[k][i]) p ^= x[i];
        x[k] = p;
        if(x[k])    dfs(k - 1,sum + 1);
        else    dfs(k - 1,sum);
    }else{
        x[k] = 0;
        dfs(k - 1,sum);
        x[k] = 1;
        dfs(k - 1,sum + 1);
        x[k] = 0;
    }
}        
void solve(){
    for(int k = 1;k <= n;k ++){
        int f = 0;
        for(int i = k;i <= n;i ++)
            if(a[i][k]){
                for(int j = 1;j <= n + 1;j ++)  swap(a[i][j],a[k][j]);
                f = 1;
                break;
            }
        if(!f)  continue;
        for(int i = k + 1;i <= n;i ++)  if(a[i][k])
            for(int j = 1;j <= n + 1;j ++)  a[i][j] ^= a[k][j];
    }
    An = 1000000009;
    dfs(n,0);
    cout << An << endl;
}
int main(){
    while(scanf("%d",&n),n){
        int u,v;
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        for(int i = 1;i < n;i ++){
            scanf("%d%d",&u,&v);
            a[u][v] = a[v][u] = 1;
        }
        for(int i = 1;i <= n;i ++)  a[i][i] = a[i][n + 1] = 1;
        solve();
    }
    return 0;
}