高橋・直樹's Blog

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

题意

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

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

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

题解

一看到是求任意点对的费用，就要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]]);
	}
}

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

题意

太复杂了。。所以

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));
}

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

题意

给出以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]);
}

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

题目大意：

在一个无向图中有T条边，每个点至少和两条边相连，每条边有一个长度，询问从给定起点到给定终点的包含N条边的路最短是多长。

问题规模：

1<=N<=1000000000, 1<=T<=100

这题我了解到3个方法，都很神牛，很有启发。

1.基于倍增的floyd

官方的解法。假设我们已经知道了两点间经过k条边的最短路，就可以利用floyd求出两点间经过k*2条边的最短路，于是我们可以依次求出经过1,2,4,8,16...条边的最短路，它们正好可以组成任何二进制数，我们只要把N分解成这些的和，再用floyd求一遍就可以了。复杂度O(T^3 logN)。

2.矩阵乘法思想

看到这题的数据应该很多人想到矩阵乘法快速幂，但矩阵乘法表示的是乘积的和，如果是要求经过N条边的路径数就可以直接这么做了，无奈之下只好放弃了这个想法。但其实我们可以尝试定义一个新的矩阵乘法，使它可以表示我们需要的结果。

原始的矩阵乘法是这样的：如果C=A*B 那么

我们可以定义C=A@B

于是样例的结果就可以表示为

可以证明运算@是满足结合律的，所以也可以用快速幂求出。

这个方法时间复杂度跟floyd是一样的O(T^3 logN)，而且写起来也差不多，以至于我认为它们本质上是一种方法。

3.部分贪心思想

这个是GYH神牛的论文《部分贪心思想在信息学竞赛中的应用》里的，核心有两点：

1.最短路径一定在一条较短边（这条路上的最短边）上来回走了很多次

2.路径上的其他边至多经过两次

证明详见论文。于是我们只需算出起点和终点到每个点经过2*T条边的最短路，然后枚举经过很多次的边，就可以在O(T^2)的时间内解决了。

题解转自http://hi.baidu.com/lilymona/item/3b401d86d22c6fd6d0f8cdf5

代码是写了第二种办法。

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
const int N=102,M=1005;
int n,e,s,t,vis[M],tot;

struct matrix 
{
	int a[N][N];
	int *operator [](int x) { return a[x];}
	void clear()
	{
		memset(a,63,sizeof(a));
	}
	matrix operator*(matrix b) 
	{
		matrix c;
		memset(c.a,63,sizeof(c.a));
		for(int i=1;i<=tot;++i)
			for(int j=1;j<=tot;++j)
				for(int k=1;k<=tot;++k)
					c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
		return c;
	}
	matrix operator^(int n) 
	{
		matrix b;b=*this;--n;
		while(n) 
		{
			if(n&1) b=b**this;
			*this=*this**this;
			n/=2;
		}
		return b;
	}
}a;

int get(int x)
{
	if(!vis[x])	vis[x]=++tot;
	return vis[x];
}

int main()
{
	scanf("%d%d%d%d",&n,&t,&s,&e);
	a.clear();
	memset(vis,0,sizeof(vis));tot=0;
	for(int i=0;i<t;i++)
	{
		int z,x,y;scanf("%d%d%d",&z,&x,&y);
		x=get(x);y=get(y);
		a[x][y]=a[y][x]=z;
	}
	s=get(s);e=get(e);
	matrix ans=a^n;
	printf("%d\n",ans[s][e]);
}

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

大意

数轴上有N个点，起点为额外的P点，在某个点被到达之前，这个点每单位时间会消费1点费用，到达后不再产生费用。求遍历所有点花费的最小费用。

题解

区间DP，

L(a,b) 表示已经走完a到b，且当前在a点的最小花费；

R(a,b) 表示已经走完a到b，且当前在a点的最小花费；

则：

L(a,b) = min( L(a+1,b) + |x(a)-x(a+1)|, R(a+1,b) + |x(a)-x(b)| )

R(a,b) = min( R(a,b-1) + |x(b)-x(b-1)|, L(a,b-1) + |x(b)-x(a)| )

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1011;
int n,a[N],L[N][N],R[N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	a[++n]=0;
	sort(a+1,a+1+n);
	int t=lower_bound(a+1,a+1+n,0)-a;
	memset(L,60,sizeof(L));
	memset(R,60,sizeof(R));
	L[t][t]=R[t][t]=0;
	for(int l=2;l<=n;l++)
		for(int i=1;i<=n;i++)
		{
			int j=i+l-1;
			if(j>n)	continue;
			L[i][j]=min(L[i+1][j]+(n-l+1)*(a[i+1]-a[i]),
						R[i+1][j]+(n-l+1)*(a[j]-a[i]));
			R[i][j]=min(L[i][j-1]+(n-l+1)*(a[j]-a[i]),
						R[i][j-1]+(n-l+1)*(a[j]-a[j-1]));
		}
	printf("%d\n",min(L[1][n],R[1][n]));
}