1787: [Ahoi2008]Meet 紧急集合

2013年3月25日 14:53

http://www.lydsy.com/JudgeOnline/problem.php?id=1787

RunID User Problem Result Memory Time Language Code_Length Submit_Time
375404 Liu_Ts 1787 Accepted 45732 kb 7584 ms C++ 2039 B 2013-03-25 11:25:27

 

题意

一棵树,每次询问给三个点,求一个点使得到这三个点的距离和最小。

题解

理解一下,可知答案必定在这三个点中,某两个点的LCA上,

于是枚举a,b;a,c;b,c的LCA。

最后发现这三个LCA有规律,有两个一定相同,但是不会用。

LCA写的RMQ比较慢啊

 

#include<cstring>
#include<climits>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500001,M=1000001,Q=2000002;

int q[Q],d[N],tot,n,k,v[M],next[M],head[N],num[N],m;

struct SegmentTree
{
	int m[6000002];
	void update(int x)
	{
		int l=x<<1,r=l+1;
		m[x]=m[l];
		if(d[m[x]]>d[m[r]])
			m[x]=m[r];
	}
	void build(int x,int s,int t)
	{
		if(s==t)
		{
			m[x]=q[s];return;
		}
		int mid=s+t>>1;
		build(x<<1,s,mid);build((x<<1)+1,mid+1,t);
		update(x);
	}
	int get(int x,int s,int t,int ll,int rr)
	{
		if(ll<=s&&t<=rr)	return m[x];
		int t1=0,t2=0,mid=s+t>>1;
		if(ll<=mid)	t1=get(x<<1,s,mid,ll,rr);
		if(rr>mid)	t2=get((x<<1)+1,mid+1,t,ll,rr);
		if(d[t1]<d[t2])	return t1;
		else return t2; 
	}
}a;
void add(int x,int y)
{
	v[++k]=y;next[k]=head[x];head[x]=k;
}
void dfs(int x,int fa,int deep)
{
	q[++q[0]]=x;num[x]=q[0];d[x]=deep;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dfs(v[i],x,deep+1),q[++q[0]]=x;
}
int lca(int x,int y)
{
	if(num[x]>num[y])	swap(x,y);
	return a.get(1,1,q[0],num[x],num[y]);	
}
int main()
{
	scanf("%d%d",&n,&m);int x,y,z;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0,0);d[0]=INT_MAX;
	a.build(1,1,q[0]);
	int p,q;
	while(m--)
	{
		int ans,sum=INT_MAX;
		scanf("%d%d%d",&x,&y,&z);
		int s=d[x]+d[y]+d[z];
		p=lca(x,y);q=lca(p,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		p=lca(x,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		p=lca(y,z);
		if(s-d[q]*2-d[p]<sum)
			sum=s-d[q]*2-d[p],ans=p;
		printf("%d %d\n",ans,sum);
	}
}

Tags: bzoj AHOI
评论(0) 阅读(819)

1774: [Usaco2009 Dec]Toll 过路费

2013年3月22日 15:19

http://www.lydsy.com/JudgeOnline/problem.php?id=1774

RunID User Problem Result Memory Time Language Code_Length Submit_Time
373994 Liu_Ts 1774 Accepted 1300 kb 304 ms C++/Edit 1013 B 2013-03-22 14:42:09

 

题意

一个图,每条边有边权,每个点也有点权,

定义两个点之间的费用为,两点之间的路径长度加上路径上最大的一个点权。

询问任意两个点对的最小费用。

题解

一看到是求任意点对的费用,就要floyd

然后floyd的性质保证当过渡点循环到k时,所有经过的点的编号<=k;

于是,我们按点权从小到大排序后,floyd。

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=251;
int f[N][N],ans[N][N],num[N],n,m,p;
struct node
{
	int w,n;
}a[N];
inline bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
	memset(f,63,sizeof(f));
	memset(ans,63,sizeof(ans));
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].w);a[i].n=i;
		f[i][i]=0;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)	num[a[i].n]=i;
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x=num[x];y=num[y];
		f[x][y]=f[y][x]=min(f[x][y],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				ans[i][j]=min(ans[i][j],f[i][j]+max(a[k].w,max(a[i].w,a[j].w)));
			}
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[num[x]][num[y]]);
	}
}

Tags: bzoj usaco
评论(0) 阅读(1169)

1084: [SCOI2005]最大子矩阵

2013年3月22日 09:23

http://www.lydsy.com/JudgeOnline/problem.php?id=1084

RunID User Problem Result Memory Time Language Code_Length Submit_Time
373714 Liu_Ts 1084 Accepted 1248 kb 64 ms C++ 1227 B 2013-03-22 08:51:24

 

题意

这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵不能相互重叠。

题解

这题我是一定不会的。。。

可是数据范围比较厉害。偶然翻题解发现原来m≤2,坑爹。

于是DP。

当 m=1 时

    g[i][j]表示前i个数字选出j段的最大分值

当 m=2 时

    f[i][j][k]表示第一列前i个数字,第二列前j个数字选出k个子矩阵的最大分值

    f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);

    f[i][j][k]=max{f[i][j][k],f[x][j][k-1]+s1[i]-s1[x]};

    f[i][j][k]=max{f[i][j][k],f[i][y][k-1]+s2[j]-s2[y]};

    当 i=j 时 

        f[i][j][k]=max{f[i][j][k],f[x][x][k-1]+s1[i]-s1[x]+s2[i]-s2[x]};

 

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=101,M=3,K=11;
int n,m,p,s[N],s1[N],s2[N];
int g[N][K],f[N][N][K];

void work1()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d",s+i);
		s[i]+=s[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=p;j++)
		{
			g[i][j]=g[i-1][j];
			for(int k=i-1;k>=0;k--)
				g[i][j]=max(g[i][j],g[k][j-1]+s[i]-s[k]);
		}
	printf("%d\n",g[n][p]);
}
void work2()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",s1+i,s2+i);
		s1[i]+=s1[i-1];s2[i]+=s2[i-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=p;k++)
			{
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int x=i-1;x>=0;x--)
					f[i][j][k]=max(f[i][j][k],f[x][j][k-1]+s1[i]-s1[x]);
				for(int y=j-1;y>=0;y--)
					f[i][j][k]=max(f[i][j][k],f[i][y][k-1]+s2[j]-s2[y]);
				if(i==j)
					for(int x=i-1;x>=0;x--)
						f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+s1[i]-s1[x]+s2[j]-s2[x]);
			}
	printf("%d\n",f[n][n][p]);
}
					
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	if(m==1)	work1();
	else work2();
}

 

 

Tags: bzoj SCOI
评论(0) 阅读(1385)

1779: [Usaco2010 Hol]Cowwar 奶牛战争

2013年3月21日 21:13

http://www.lydsy.com/JudgeOnline/problem.php?id=1779

RunID User Problem Result Memory Time Language Code_Length Submit_Time
369713 Liu_Ts 1779 Accepted 2440 kb 24 ms C++ 2171 B 2013-03-16 21:29:34

 

题意

太复杂了。。所以

http://www.nocow.cn/index.php/USACO/cowwar

题解

这题感觉就是利用网络流,瞪眼建模,通过流量来满足条件。

http://www.dxmtb.com/blog/usaco2010-hol-cowwar/

1.一个E点拆成两个点。把一个J点拆成三个点。T点不变。

2.从原点向每个J的第一个点连一条边容量为1,表示只有一只牛。

3.从J的第一个点连边到能到的点。能到的J点连第二个点,能到的E点连第一个点,容量都为1。注意,J也能到他自己。

4.对于每个能攻击的J点,把第三个J点连一条容量为1的边到能攻击的T。对于每个能攻击的E点,把第二个E点连到能攻击的T点,容量还是1。

5.把E的第一个点连一条容量为1的边到第二个点,表示只能从这个点攻击一次。J的第二个点连一条容量为1的边到第三个点,也表示只能从这个点攻击一次。

6.每个T点连一条边到汇点,容量为1。

 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<algorithm>
using namespace std;
const int N=3005,M=100000;
int u[M],v[M],w[M],next[M],head[N],k=1;
int low[N],pre[N],d[N],vd[N],cur[N];
int n,m;
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
int solve(int s,int t)
{
    int now=s,i,ans=0;
    low[s]=INT_MAX;vd[0]=t;
    while(d[s]<t)
    {
        for(i=cur[now];i;i=next[i])
            if(w[i]>0 && d[now]==d[v[i]]+1)
                break;
        cur[now]=i;
        if(i)
        {
            low[v[i]]=min(low[now],w[i]);pre[v[i]]=i;now=v[i];
            if(now==t)
            {
                for(;now!=s;now=u[pre[now]])
                {
                    w[pre[now]]-=low[t];w[pre[now]^1]+=low[t];
                }
                low[s]=INT_MAX;ans+=low[t];
            }
        }
        else
        {
            if(!--vd[d[now]])   break;
            d[now]=t;
            for(i=head[now];i;i=next[i])
                if(w[i]>0 && d[now]>d[v[i]]+1)
                {
                    d[now]=d[v[i]]+1;
                    cur[now]=i;
                }
            vd[d[now]]++;
            if(now!=s)  now=u[pre[now]];
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    char c[N];scanf("%s",c+1);
    int S=0,T=n*3+1;
    for(int i=1;i<=n;i++)
    {
        if(c[i]=='J')
        {
            add(S,i,1);
            add(i,i+n,1);
            add(i+n,i+n+n,1);
        }
        if(c[i]=='T')   add(i,T,1);
        if(c[i]=='E')   add(i,i+n,1);
    }
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        if(c[y]=='J')   swap(x,y);
        if(c[x]=='J')
        {
            if(c[y]=='T')   add(x+n+n,y,1);
            if(c[y]=='J')   add(x,y+n,1),add(y,x+n,1);
            if(c[y]=='E')   add(x,y,1);
        }
        if(c[x]=='T')
            if(c[y]=='E')
                add(y+n,x,1);
        if(c[x]=='E')
            if(c[y]=='T')
                add(x+n,y,1);
    }
    printf("%d\n",solve(S,T));
}

 

Tags: bzoj usaco
评论(0) 阅读(1119)

3011: [Usaco2012 Dec]Running Away From the Barn

2013年3月21日 20:03

http://www.lydsy.com/JudgeOnline/problem.php?id=3011

RunID User Problem Result Memory Time Language Code_Length Submit_Time
370535 Liu_Ts 3011 Accepted 14804 kb 908 ms C++ 1039 B 2013-03-17 23:35:13

 

题意

给出以1号点为根的一棵有根树,问每个点的子树中与它距离小于L的点有多少个。

题解

dfs,对于每个点,打一个+1的标记,在从它到根的路径上,第一个大于>L的点打一个-1的标记,

则每个点的答案就是以它为根的子树的标记和。

官方题解写的倍增,我只会记录dfs序列,然后二分。

 

#include<cstring>
#include<cmath>
#include<climits>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=210000;
int v[N],next[N],head[N],n,k; ll len,w[N];
int f[N],stack[N],tot;ll s[N];
void build(int x,int y,ll z)
{
    v[++k]=y;w[k]=z;next[k]=head[x];head[x]=k;
}
 
int check(int r)
{
    ll l=1;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(s[stack[tot]]-s[stack[mid]]>len) l=mid;
        else r=mid-1;
    }
    return stack[l];
}
 
void dfs(int x,ll sum)
{
    stack[++tot]=x;s[x]=sum;
    f[x]+=1;f[check(tot)]-=1;
    for(ll i=head[x];i;i=next[i])
    {
        dfs(v[i],sum+w[i]);
        f[x]+=f[v[i]];
    }
    tot--;
}
 
int main()
{
    scanf("%d%lld",&n,&len);
    for(int i=2;i<=n;i++)
    {
        ll x,y;scanf("%d%lld",&x,&y);
        build(x,i,y);
    }
    s[0]=-ll(1e20);stack[++tot]=0;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",f[i]);
}

Tags: bzoj usaco
评论(1) 阅读(1798)