2013年6月13日 23:18

BZOJ2763: [JLOI2011]飞行路线【分层图dijkstra+堆】

BZOJ

这道题也是分层图。k次机会让边权变0。虽然以前搞过但是好久了我也忘了。于是写死写死地写。然后纠结了下标纠结了n久之后就过了。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=getint(),e=getint();
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    for(int k=1;k<=K;k++) for(int i=0;i<n;i++) for(int j=h[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]);
        ae(i+(k-1)*n,n*k+p[j],0);
    }dijkstra(s);
    printf("%d\n",d[n*K+e]);
    return 0;
}

Comments(0)

Tags:

2013年6月13日 23:15

BZOJ2662: [BeiJing wc2012]冻结【分层图dijkstra】

BZOJ

n个顶点m条边。给你k次机会让边权减半。一次机会对一条边只能做一次。

n、k都是小于50,那么分层。然后就好了。有些细节比较纠结。于是调了好久。囧。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int g[55][55]={0},hh[maxn],h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=1,e=n;
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    memcpy(hh,h,sizeof(h));
    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++) for(int j=hh[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]); 
        ae(i+(k-1)*n,n*k+p[j],w[j]>>1);
    }dijkstra(s); int An=inf; for(int i=0;i<=K;i++) An=min(An,d[n*i+e]);
    printf("%d\n",An); return 0;
}

Comments(0)

Tags:

2013年6月13日 16:50

BZOJ2783: [JLOI2012]树【dfs+set】

BZOJ

因为求的路径都是从在包含根的一条链上。所以可以考虑直接dfs。记录栈里元素的前缀和。

比如搜到u了,在set里面查询有没有d[u]-k,有的话就加一。然后继续往下dfs的时候把d[u]插入set。

别忘了最开始插个0。

10w个点递归会爆?最好写个手工栈?哈哈我会写了!

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=200005;
int n,K,vis[maxn]={0},w[maxn],h[maxn],st[maxn],d[maxn],p[maxn],n1[maxn],tot=0;
set<int>S; char buf[5000000],*pt=buf;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); K=getint();
    memset(h,-1,sizeof(h)); S.clear(); S.insert(0);
    for(int i=1;i<=n;i++) w[i]=getint(); int u,v,An=0;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v);
    int top=0; st[++top]=1; S.insert(w[1]); d[1]=w[1]; vis[1]=1;
    while(top){
        int o=st[top],flag=0;
        for(int i=h[o];~i;i=n1[i]) if(!vis[p[i]]){
            st[++top]=p[i]; h[o]=n1[i]; d[p[i]]=d[o]+w[p[i]];
            vis[p[i]]=flag=1; S.insert(d[p[i]]);
            if(S.find(d[p[i]]-K)!=S.end()) An++;break;
        }if(!flag){ top--; S.erase(d[o]);}
    }printf("%d\n",An); return 0;
}

Comments(0)

Tags:

2013年6月12日 22:21

BZOJ1786: [Ahoi2008]Pair 配对【DP】

BZOJ

10000个数。有些数空着给你填。每个数的范围都在1~K内。求出填满后的逆序对的最小值。

很明显这几个填的数是递增的。不然自己就产生逆序对了。(没证明过

先处理出da[i][j]表示i~n中比j大的数,xi[i][j]表示1~i中比j小的数。

f[i][j]表示填到第i个数了,这位填了j所产生的逆序对。

则f[i][j]=min{f[i][k]+da[pos[i]][j]+xi[pos[i]][j]}。然后再加上数列本身的逆序对数就行了。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1061109567;
int a[10005],da[10005][105],xi[10005][105],p[10005],f[10005][100],n,k,m=0,An=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!~a[i]) p[++m]=i;
    }for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++) da[i][j]=da[i-1][j];
        if(~a[i-1]) for(int j=1;j<a[i-1];j++) da[i][j]++;
    }for(int i=n-1;i;i--){
        for(int j=1;j<=k;j++) xi[i][j]=xi[i+1][j];
        if(~a[i+1]) for(int j=a[i+1]+1;j<=k;j++) xi[i][j]++;
    }for(int i=1;i<=n;i++) if(~a[i]) An+=da[i][a[i]];
    memset(f,63,sizeof(f));
    for(int i=1;i<=k;i++) f[1][i]=da[p[1]][i]+xi[p[1]][i];
    for(int i=2;i<=m;i++) for(int j=1;j<=k;j++) for(int o=1;o<=j;o++)
        f[i][j]=min(f[i][j],f[i-1][o]+da[p[i]][j]+xi[p[i]][j]);
    int An2=inf;  for(int i=1;i<=k;i++) An2=min(An2,f[m][i]);
    An2=(An2==inf)?0:An2;
    printf("%d\n",An+An2); return 0;
}

Comments(0)

Tags:

2013年6月12日 21:14

BZOJ1705: [Usaco2007 Nov]Telephone Wire【DP】

BZOJ

设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}(k是第i-1位上的数,j是当前位上的数)

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试?

j>k时:dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时:dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k},g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话,第一维好像一点用都没有。那就不要了!

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    memset(dp,63,sizeof(dp));
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        memset(dp,63,sizeof(dp));
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
}

Comments(0)

Tags:

2013年6月12日 18:04

博弈论初探Ⅱ【SG函数】

专题

先留一个坑。

Comments(1)

Tags:

2013年6月12日 16:29

博弈论初探I【Nim取石子游戏】

专题

题目1:有n堆石子,第i堆有A(i)颗石子。两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

令C=A(1) xor A(2) xor A(3) xor ... xor A(n),若C>0,则记为利己态,用S表示,若C=0,则记为利他态,用T表示。

【定理1】对于一个S态,一定能从一堆石子中取出若干个,使其成为T态。

【证明】既然是S态,则此时C>0,我们要使得C变为0。

设C转化为二进制后,最高位的1是第p位。那么一定存在一个A(t)的二进制最高位的1是第p位。(显然,不然C的第p位不可能是1)

然后,把第t堆石子的个数变为x=A(t) xor C。因为A(t)和C的二进制最高位的1是同一位。那么异或之后这一位就变成了0。那么x一定小于A(t)。

此时的C'=A(1) xor A(2) xor ... xor A(t) xor C xor A(t+1) xor ... xor A(n)。把C带进去,得到

C'=A(1) xor A(2) xor ... xor A(n) xor A(1) xor A(2) xor ... xor A(n)。显然C'=0。

所以,只要在第t堆石子中取出A(t)-x颗石子,就把S态变为了T态。


【定理2】对于一个T态,从任意一堆取任意个石子出来,都会变为S态。

【证明】用反证法。设此时第i堆的石子数变成了A(i')。此时C=0。如果C'>0,那么命题就成立了。

假设C'=0。则C'=A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

因为C=0。所以C xor C'=0。则A(1) xor A(2) xor ... xor A(i) xor... xor A(n) xor A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

A(i) xor A(i')=0。A(i)=A(i')明显不对了。所以命题得证。


得到了这两个定理之后,我们可以发现,任何一个S态,我们都可以通过自己的控制将它转化成T态。而对方怎么做都是将T态再转回S态,很被动。所以只要先手是S态,总是可以根据定理1得到的策略获胜。



题目2:有n堆石子,第i堆有A(i)颗石子。两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为,求必胜的方法。

再来定义几个状态。一堆石子里只有一个石子,记为孤单堆。否则记为充裕堆。

在T态中,如果充裕堆的个数大于等于2,记为T2态,1个充裕堆,记为T1态,没有充裕堆,记为T0态。S0、S1、S2同理。

【定理3】在S0态中,若孤单堆的个数为奇数。那必输。T0态必赢。

【证明】也就是奇数个石子,每次取一个。很明显先去的人必输。


【定理4】在S1态中,方法正确就必胜。

【证明】如果孤单堆的个数是奇数,那么就把充裕堆取完;如果是偶数,就把充裕堆取的只剩1根。这样留下的就是奇数个孤单堆,对方先手。由定理3得,对方必输,己方必胜。


【定理5】S2态不可一次变为T0态。

【证明】显然,充裕堆不可能一次从2堆以上变为0。


【定理6】S2态可一次变为T2态。

【证明】由定理1得S态可以一次变为T态,而且不会一次取完整堆,那么充裕堆的个数是不会变的,由定理5得S2态不能一次变为T0态,那么转化的T态是T2态。


【定理7】T2态只能转变为S1或S2态。

【证明】由定理2得,T态一次只能变为S态。由于充裕堆数不会变为0。所以是S1或S2态。


【定理8】在S2态中,只要方法正确,就必胜。

【证明】由定理6得,先转化为T2态。由定理7,对方只能再转化回S1或S2态。由定理4,己方必胜。


【定理9】T2态必输。

【证明】同证明8。


我们得到了几个必胜态:S2,S1,T0。必输态:T2,T1,S0。


比较一下两题:

第一题的过程:S2-T2-S2-T2-.....-T2-S1-T0-S0-T0-...-S0-T0(全0)

第二题的过程:S2-T2-S2-T2-.....-T2-S1-S0-T0-S0-...-S0-T0(全0)

我们可以发现前面的过程是一样的。关键在于得到了S1态之后,怎样抉择使自己获胜。而这个是自己可以掌握的。

因此,我们只需要把T2态留给对方,迟早他会转化成S1态。己方就必胜。



HDU 1850

题意:题目1模型。首先判断是否先手必胜。如果必胜则输出第一次的可行方案数。

根据定理1,先得到C的二进制最高位的1是第p位。然后计算n个数中有多少个数最高位的1也是第p位即可。



#include<cstdio>
int a[105];
int main(){
    int n,Xor,t;
    while(scanf("%d",&n),n){
        Xor=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),Xor^=a[i];
        if(!Xor){ printf("0\n"); continue;} 
        int k=0,ans=0; while(Xor)k++,Xor>>=1;
        for(int i=1;i<=n;i++)if(a[i]&(1<<k-1))ans++;
        printf("%d\n",ans);
    }return 0;
}

HDU 1907 

题意:有n堆糖果,每次吃任意一堆中的任意个。可以吃完一堆。不能不吃。吃完最后的负。问先手输赢情况。

很明显就是上面的题目2模型。









#include<cstdio>
int main(){
    int tc; scanf("%d",&tc);
    int n,t;
    while(tc--){
        scanf("%d",&n); int Xor=0,k=0;
        for(int i=1;i<=n;i++) scanf("%d",&t),k+=t>1,Xor^=t;   
        if((Xor&&k>=1)||(!Xor&&!k))printf("John\n");
        else printf("Brother\n");
    }return 0;
}

HDU 2509 也转化为题目2模型。代码大同小异。

Comments(1)

Tags:

2013年6月12日 12:56

BZOJ1498: [NOI2006]神奇的口袋【高精度】

BZOJ

模拟一下发现答案与取球的顺序其实是无关的。

然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。

但是既然这样就是高精度模拟了?

双倍经验(1416 && 1498)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Hugeint{int len,num[10000];  Hugeint(){  len=1;  memset(num,0,sizeof(num));}}An1,An2;
int num[1005],A[10000]={0},B[10000]={0},flag[20005]={0},prime[10000],cnt=0,sum=0;
inline int pre(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<=n;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}inline Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(int i=1;i<=a.len;i++) for(int j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(int i=1;i<c.len;i++)  if(c.num[i]>9999) c.num[i+1]+=c.num[i]/10000,c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,c.num[c.len]+=c.num[c.len-1]/10000,c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1) c.len--;   return c;
}inline Hugeint pow(int b,int p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}void print(Hugeint a){
    printf("%d",a.num[a.len]); for(int i=a.len-1;i;i--)printf("%04d",a.num[i]);
}inline void pushA(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)A[i]++,k/=prime[i];
}inline void pushB(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)B[i]++,k/=prime[i];
}int main(){
    int n,m,d,x,y;  pre(20000);
    scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++)scanf("%d",&num[i]),sum+=num[i];
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(num[y]==0){ printf("0/1\n");return 0;}
        pushA(num[y]);  pushB(sum);
        num[y]+=d;      sum+=d;
    }for(int i=0;i<cnt;i++) if(A[i]&&B[i]){
        if(A[i]>B[i])   A[i]-=B[i], B[i]=0;
        else            B[i]-=A[i], A[i]=0;
    }An1.num[1]=An2.num[1]=1;
    for(int i=0;i<cnt;i++)  if(A[i])    An1=Mul(An1,pow(prime[i],A[i]));
    for(int i=0;i<cnt;i++)  if(B[i])    An2=Mul(An2,pow(prime[i],B[i]));
    print(An1);putchar('/');print(An2);putchar('\n');return 0;
}

Comments(0)

Tags:

2013年6月11日 21:43

BZOJ1787: [Ahoi2008]Meet 紧急集合【LCA】

BZOJ

给你一颗无根树。每条边的路径长是1。

每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。

看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据,发现求的点一定在其中两个点的LCA。

那么就好了。每次求出3个LCA。然后枚举。算出距离和。

介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。

如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、

 





#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char buf[21000000],*pt=buf,*o=buf;
int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0};
int lg[500005],a[500005][20],n,m,tot=1;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++;
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void print(int x){
    char str[11],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}inline void pre(){
    int s=0,e=1; q[0]=1; d[1]=1; v[1]=1;
    while(s<e){
        for(int i=h[q[s++]];i;i=n1[i]) if(!v[p[i]])
            v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1];
    }for(int j=1;j<20;j++) for(int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1];
}inline int lca(int u,int v){
    if(d[u]>d[v]){ u^=v; v^=u; u^=v;}
    int k=d[v]-d[u],j=0; while(k){ if(k&1)v=a[v][j]; j++; k>>=1;}
    if(u==v)return u;
    for(int i=lg[d[u]-1];~i;i--)
        if(a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i];
    return a[u][0]; 
}int main(){
    fread(pt,1,21000000,stdin);  
    n=getint();m=getint();
    for(int i=0;(1<<i)<=n;i++)
        for(int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i;
    int u,v,w,a1,a2,a3,a4,a5,An1,An2;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); 
    pre();
    for(int i=1;i<=m;i++){
        u=getint(),v=getint(),w=getint();
        a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w];
        An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1);
        if((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2;
        if((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3;
        print(An1);*o++=' ';print(An2);*o++='\n';
    }return fwrite(buf,1,o-buf,stdout),0;
}

Comments(0)

Tags:

2013年6月11日 18:13

BZOJ1707: [Usaco2007 Nov]tanning分配防晒霜【最大流】

BZOJ

第i头牛,可以使用第j个防晒霜的,从j到i连一条容量1的边。

每个防晒霜从S给它连容量为cover[i]的边。

求一遍最大流就好了

 





#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000,maxm=5000000,inf=1000000009;
int p[maxm],c[maxm],n1[maxm],q[maxn],h1[maxn],d[maxn],h[maxn],g[maxn];
int l[3000],r[3000],S,T,n,m,k,tot=0,cnt=0,N=0;  char buf[2000000],*pt=buf;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++; 
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void ae(int x,int y,int z){
    p[tot]=y;   c[tot]=z;   n1[tot]=h[x];   h[x]=tot++;
    p[tot]=x;   c[tot]=0;   n1[tot]=h[y];   h[y]=tot++;
}inline int bfs(){
    memset(d,0xff,sizeof(d));   int r=d[q[0]=S]=0;
    for(int l=0;l<=r;l++)
        for(int k=h[q[l]];~k;k=n1[k])
            if(c[k] && !~d[p[k]])   d[q[++r]=p[k]]=d[q[l]]+1;
    return ~d[T];
}int dfs(int x=S,int lmt=inf){
    if(x==T)    return lmt; int flow;
    for(int &k=g[x];~k;k=n1[k]){
        if(c[k] && d[p[k]]==d[x]+1 && (flow=dfs(p[k],min(lmt,c[k])))){
            c[k]-=flow; c[k^1]+=flow;   return flow;
        }
    }return 0;
}int main(){
    memset(h,-1,sizeof(h));
    fread(pt,1,2000000,stdin);  n=getint(); m=getint(); S=0; T=n+m+1;
    for(int i=1;i<=n;i++)   l[i]=getint(),r[i]=getint(),ae(m+i,T,1);
    for(int i=1;i<=m;i++){
        int u,v; u=getint(),v=getint();  ae(S,i,v);
        for(int j=1;j<=n;j++) if(l[j]<=u&&u<=r[j]) ae(i,m+j,1);
    }int An=0,f=0;   while(bfs()){   memcpy(g,h,sizeof(h));  while(f=dfs())  An+=f;}
    printf("%d\n",An);    return 0;
} 

Comments(0)

Tags:

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1