USACO 刷题记录bzoj

bzoj 1606: [Usaco2008 Dec]Hay For Sale 购买干草——背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int h,n,f[],k;

int main()

{

    h=read(); n=read();

    f[]=;

    for(int i=;i<=n;i++){

        k=read();

        for(int j=h;j>=k;j--) if(f[j-k]) f[j]=;

    }

    for(int i=h;i>=;i--)if(f[i]){printf("%d\n",i); break;}

    return ;

}

bzoj 1607: [Usaco2008 Dec]Patting Heads 轻拍牛头——筛数

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,f[],v[],ans[];

int main()

{

    n=read();

    for(int i=;i<=n;i++) v[i]=read(),f[v[i]]++;

    for(int i=;i<=(int)1e6;i++)if(f[i]){

        for(int j=i;j<=(int)1e6;j+=i) if(f[j]) ans[j]+=f[i];

    }

    for(int i=;i<=n;i++) printf("%d\n",ans[v[i]]-);

    return ;

}

bzoj 1597: [Usaco2008 Mar]土地购买——斜率优化dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL x[M],y[M],f[M];

int q[M],n,tot;

struct node{LL x,y;}a[M];

bool cmp(node a,node b){return a.x!=b.x?a.x<b.x:a.y<b.y;}

double slop(int a,int b){return (double)(f[b]-f[a])/(y[a+]-y[b+]);}

int main()

{

    n=read();

    for(int i=;i<=n;i++) a[i].x=read(),a[i].y=read();

    sort(a+,a++n,cmp);

    for(int i=;i<=n;i++){

        while(tot&&y[tot]<=a[i].y) tot--;

        x[++tot]=a[i].x; y[tot]=a[i].y;

    }

    int head=,tail=;

    for(int i=;i<=tot;i++){

        while(head<tail&&slop(q[head],q[head+])<x[i]) head++;

        int v=q[head];

        f[i]=f[v]+y[v+]*x[i];

        while(head<tail&&slop(q[tail-],q[tail])>slop(q[tail],i)) tail--;

        q[++tail]=i;

    }

    printf("%lld\n",f[tot]);

    return ;

}

bzoj 1699: [Usaco2007 Jan]Balanced Lineup排队 ——zkw版

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=<<,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,q,l,r;

int mx[N<<],mn[N<<];

int push_ans(int l,int r){

    int mx1=,mn1=inf;

    for(l+=N-,r+=N+;r-l!=;l>>=,r>>=){

        if(~l&) mx1=max(mx1,mx[l^]),mn1=min(mn1,mn[l^]);

        if(r&)     mx1=max(mx1,mx[r^]),mn1=min(mn1,mn[r^]);

    }

    return mx1-mn1;

}

int main()

{

    n=read(); q=read();

    for(int i=;i<=n;i++) mx[N+i]=mn[N+i]=read();

    for(int i=N-;i;i--) mx[i]=max(mx[i<<],mx[i<<^]),mn[i]=min(mn[i<<],mn[i<<^]);

    for(int i=;i<=q;i++){

        l=read(); r=read();

        printf("%d\n",push_ans(l,r));

    }

    return ;

}

bzoj 1602: [Usaco2008 Oct]牧场行走——lca

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=1e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int vis[M],d[M],q[M];

int n,k,first[M],cnt;

struct node{int to,w,next;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,w,first[a]}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

void push_ans(int k){

    int head=,tail=;

    q[]=k; vis[k]=;

    while(head!=tail){

        int x=q[head++];

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(!vis[now]){

                vis[now]=;

                d[now]=d[x]+e[i].w;

                q[tail++]=now;

            }

        }

    }

}

int main()

{

    int x,y,w;

    n=read(); k=read();

    for(int i=;i<n;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    for(int i=;i<=k;i++){

        x=read(); y=read();

        memset(vis,,sizeof(vis));

        memset(d,,sizeof(d));

        push_ans(x);

        printf("%d\n",d[y]);

    }

    return ;

}

bzoj 1610: [Usaco2008 Feb]Line连线游戏——几何

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int M=;

bool pd(double x,double y){return fabs(x-y)<1e-;}

int n,cnt,ans;

double x[M],y[M],a[M*M];

bool cmp(double x,double y){return x<y;}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lf %lf",&x[i],&y[i]);

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++){

            if(!pd(x[i],x[j])) a[++cnt]=(y[i]-y[j])/(x[i]-x[j]);

            else ans=;

        }

    sort(a+,a++cnt,cmp);

    if(cnt>=) ans++;

    for(int i=;i<=cnt;i++) if(!pd(a[i],a[i-])) ans++;

    printf("%d\n",ans);

    return ;

}

bzoj 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 ——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,c[M],f[M][],ans=inf;

int main()

{

    n=read();

    for(int i=;i<=n;i++) c[i]=read();

    memset(f,0x3f,sizeof(f));

    f[][]=f[][]=f[][]=;

    for(int k=;k<=n;k++)

        for(int i=;i<=;i++){

            for(int j=;j<=i;j++) f[k][i]=min(f[k][i],f[k-][j]);

            if(i!=c[k]) f[k][i]++;

        }

    for(int i=;i<=;i++) ans=min(ans,f[n][i]);

    memset(f,0x3f,sizeof(f));

    f[n+][]=f[n+][]=f[n+][]=;

    for(int k=n;k>=;k--)

        for(int i=;i<=;i++){

            for(int j=;j<=i;j++) f[k][i]=min(f[k][i],f[k+][j]);

            if(i!=c[k]) f[k][i]++;

        }

    for(int i=;i<=;i++) ans=min(ans,f[][i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1625: [Usaco2007 Dec]宝石手镯——01背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,N=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,c[M],w[M],f[N];

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) c[i]=read(),w[i]=read();

    for(int i=;i<=n;i++)

        for(int j=m;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+w[i]);

    printf("%d\n",f[m]);

    return ;

}

bzoj 1617: [Usaco2008 Mar]River Crossing渡河问题——简单dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,f[M],w[M],s[M];

int main()

{

    n=read(); s[]=read();

    for(int i=;i<=n;i++) w[i]=read();

    for(int i=;i<=n;i++) s[i]=s[i-]+w[i];

    for(int i=;i<=n;i++){

        f[i]=inf;

        for(int j=;j<=i;j++) f[i]=min(f[i],f[i-j]+s[j]+s[]);

    }

    printf("%d\n",f[n]-s[]);

    return ;

}

bzoj 1650: [Usaco2006 Dec]River Hopscotch 跳石子——二分

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int L,n,m,s[M];

bool check(int mx){

    int cnt=,sum=;

    for(int i=;i<=n;i++){

        if(s[i]-sum<=mx) cnt++;

        else sum=s[i];

    }

    return cnt<=m;

}

int main()

{

    L=read(); n=read(); m=read();

    for(int i=;i<=n;i++) s[i]=read();

    s[++n]=L;

    sort(s+,s++n);

    int l=,r=L+;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) l=mid+;

        else r=mid-;

    }printf("%d\n",l);

    return ;

}

bzoj 2718: [Violet 4]毕业旅行——二分图匹配+最大反链

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,n,m,S,T,f[M][M];

int vis[M],d[M],first[M],cur[M],cnt=;

struct node{int to,next,flow;}e[M*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;};

void insert(int a,int b){ins(a,b,); ins(b,a,);}

void floyd(){

    for(int k=;k<=n;k++)

     for(int i=;i<=n;i++)

      for(int j=;j<=n;j++)

       f[i][j]|=f[i][k]&f[k][j];

    for(int i=;i<=n;i++) f[i][i]=;

}

queue<int>q;

int bfs(){

    memset(d,-,sizeof(d));

    q.push(S); d[S]=;

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(e[i].flow&&d[now]==-) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int f,flow=;

    for(int& i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(e[i].flow&&d[now]==d[x]+&&(f=dfs(now,min(a,e[i].flow)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

int main()

{

    int x,y;

    n=read(); m=read(); ans=n;

    S=; T=*n+;

    for(int i=;i<=m;i++) x=read(),y=read(),f[x][y]=;

    floyd();

    for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

      if(f[i][j]) insert(i,j+n);

    for(int i=;i<=n;i++) insert(S,i),insert(i+n,T);

    while(bfs()){

        for(int i=S;i<=T;i++) cur[i]=first[i];

        ans-=dfs(S,inf);

    }printf("%d\n",ans);

    return ;

}

bzoj 1613: [Usaco2007 Jan]Running贝茜的晨练计划——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,w[M];

int f[M][];

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) w[i]=read();

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++) f[i][j]=f[i-][j-]+w[i];

        f[i][]=f[i-][];

        for(int j=;j<=m;j++) if(i>j) f[i][]=max(f[i][],f[i-j][j]);

    }

    printf("%d\n",f[n][]);

    return ;

}

bzoj 1230: [Usaco2008 Nov]lites 开关灯——线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=<<;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m;

int k,L,R;

struct node{

    node *lc,*rc;

    int l,r,mid,sum,h,sz;

    void pr(){sum=sz-sum; h^=;}

    void up(){sum=lc->sum+rc->sum;}

    void down(){h=; lc->pr(); rc->pr();}

    void modify(){

        if(L<=l&&r<=R) return pr();

        if(h) down();

        if(L<=mid) lc->modify();

        if(R>mid) rc->modify();

        up();

    }

    int query(){

        if(L<=l&&r<=R) return sum;

        if(h) down();

        int tot=;

        if(L<=mid) tot+=lc->query();

        if(R>mid)  tot+=rc->query();

        return tot;

    }

    node*build(int L,int R);

}tr[M],*np=tr+;

node*node::build(int L,int R){

    l=L; r=R; sz=R-L+;

    if(L<R){

        mid=(L+R)>>;

        lc=++np;

        lc->build(L,mid);

        rc=++np;

        rc->build(mid+,R);

    }

}

int main(){

    n=read(); m=read();

    tr[].build(,n);

    for(int i=;i<=m;i++){

        k=read(); L=read(); R=read();

        if(!k) tr[].modify();

        else if(k)  printf("%d\n",tr[].query());

    }

    return ;

}

bzoj1600 1600: [Usaco2008 Oct]建造栅栏——简单dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n;

int f[][];

int main()

{

    n=read();

    f[][]=;

    int mx=(n+)/-;

    for(int k=;k<=;k++)

     for(int i=;i<=n;i++)

      for(int j=;j<=min(i,mx);j++)

          f[k][i]+=f[k-][i-j];

    printf("%d\n",f[][n]);

    return ;

}

bzoj 1612: [Usaco2008 Jan]Cow Contest奶牛的比赛

n^3算法用的bitset可能快点n^3/32吧暂时没有更优的方法

#include<cstdio>

#include<bitset>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m;

bitset<> f[];

int main(){

    int x,y;

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),f[x][y]=;

    for(int k=;k<=n;++k)

        for(int i=;i<=n;i++) if(f[i][k]) f[i]|=f[k];

    int res=;

    for(int i=;i<=n;++i){

        int sum=;

        for(int j=;j<=n;j++) sum+=f[i][j]|f[j][i];

        if(sum==n) ++res;

    }

    printf("%d",res);

    return ;

}

好的还有nm/32的写法但是实测没快多少

#include<cstdio>

#include<bitset>

#include<cstring>

#include<algorithm>

#include<queue>

#include<iostream>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,ans;

bitset<>f[];

int first[M],cnt,in[M],vis[M],map[M][M];

queue<int>q;

int main(){

    int x,y;

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),map[y][x]=,in[x]++;

    for(int i=;i<=n;i++){

        f[i][i]=;

        if(!in[i]) q.push(i),vis[i]=;

    }

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=;i<=n;i++)if(map[x][i]&&!vis[i]){

            in[i]--;

            f[i]|=f[x];

            if(!in[i]) vis[i]=,q.push(i);

        }

    }

    int ans=;

     for(int i=;i<=n;i++){

        int sum=;

        for(int j=;j<=n;j++) sum+=f[i][j]|f[j][i];

        if(sum==n) ans++;

    }

    printf("%d\n",ans);

    return ;

}

bzoj1614: [Usaco2007 Jan]Telephone Lines架设电话线——二分答案

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=2e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,mx;

int first[M],cnt,d[M],vis[M];

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

queue<int>q;

int spfa(int mx){

    memset(vis,,sizeof(d));

    memset(d,0x3f,sizeof(d));

    q.push(); d[]=;

    while(!q.empty()){

        int x=q.front(); q.pop();

        vis[x]=;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to,v=d[x]+(e[i].w>mx);

            if(d[now]>v){

                d[now]=v;

                if(!vis[now]) vis[now]=,q.push(now);

            }

        }

    }

    return d[n]<=k;

}

int main()

{

    int x,y,w;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),insert(x,y,w),mx=max(mx,w);

    int ans=-,l=,r=mx;

    while(l<=r){

        int mid=(l+r)>>;

        if(spfa(mid)) ans=mid,r=mid-;

        else l=mid+;

    }printf("%d\n",ans);

    return ;

}

bzoj 1603. -- [Usaco2008 Oct]打谷机——简单模拟

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=1e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,cnt,d[M];

struct node{int x,y,c;}e[M];

bool cmp(node a,node b){return a.x<b.x;}

int main()

{

    n=read();

    for(int i=;i<n;i++) e[i].x=read(),e[i].y=read(),e[i].c=read();

    sort(e+,e+n,cmp);

    d[]=;

    for(int i=;i<n;i++)

     if(e[i].c==) d[e[i].y]=d[e[i].x];

     else d[e[i].y]=-d[e[i].x];

    printf("%d\n",d[n]);

    return ;

}

bzoj 1599: [Usaco2008 Oct]笨重的石子

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int s[],mx,ans;

int f[],sum;

int main()

{

    for(int i=;i<=;i++) s[i]=read(),sum+=s[i];

    for(int s1=;s1<=s[];s1++)

     for(int s2=;s2<=s[];s2++)

      for(int s3=;s3<=s[];s3++)

       f[s1+s2+s3]++;

    for(int i=;i<=sum;i++) if(f[i]>mx) mx=f[i],ans=i;

    printf("%d\n",ans);

    return ;

}

bzoj 1692: [Usaco2007 Dec]队列变换——后缀数组

暂时不会写留坑代填填在后面了233（没用后缀数组QAQ）

bzoj 1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛——简单dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,T;

int sx,sy,ex,ey;

int f[M][M][],map[M][M];

int xi[]={,,,,-},yi[]={,,,-,};

char s[];

int main()

{

    n=read(); m=read(); T=read();

    for(int i=;i<=n;i++){

        scanf("%s",s+);

        for(int j=;j<=m;j++) if(s[j]=='.') map[i][j]=;

    }

    sx=read(); sy=read(); ex=read(); ey=read();

    f[sx][sy][]=;

    for(int k=;k<=T;k++)

     for(int x=;x<=n;x++)

      for(int y=;y<=m;y++)if(map[x][y])

          for(int i=;i<=;i++){

              int nx=x+xi[i],ny=y+yi[i];

              if(nx<||nx>n||ny<||ny>m||!map[nx][ny]||!f[nx][ny][k-]) continue;

              f[x][y][k]+=f[nx][ny][k-];

          }

    printf("%d\n",f[ex][ey][T]);

    return ;

}

bzoj1666 : [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏——模拟

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,ans;

int main()

{

    n=read();

    while(n!=){

        ans++;

        if(n%) n=n*+;

        else n/=;

    }printf("%d\n",ans);

    return ;

}

bzoj 1626: [Usaco2007 Dec]Building Roads 修建道路——最小生成树

1. Kruskal 这个写法超级慢QAQ 直接n^2logn^2 暴力

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int M=1e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,f[M],map[M][M];

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

double x[M],y[M],ans;

double calc(int p,int q){return sqrt((x[p]-x[q])*(x[p]-x[q])+(y[p]-y[q])*(y[p]-y[q]));}

int cnt,sum;

struct node{int from,to; double d;}e[M*M];

bool cmp(node a,node b){return (b.d-a.d)>1e-;}

int main()

{

    int p,q;

    n=read(); m=read();

    for(int i=;i<=n;i++) f[i]=i;

    for(int i=;i<=n;i++) scanf("%lf %lf",&x[i],&y[i]);

    for(int i=;i<=m;i++){

        p=read(); q=read();

        map[p][q]=map[q][p]=;

        e[++cnt]=(node){p,q,calc(p,q)};

    }

    sort(e+,e++cnt,cmp);

    for(int i=;i<=cnt;i++){

        int p=find(e[i].from),q=find(e[i].to);

        if(p==q) continue;

        sum++; f[q]=p;

    }

    if(sum==n) return printf("%.2lf\n",ans),;

    cnt=;

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)if(!map[i][j])

            e[++cnt]=(node){i,j,calc(i,j)};

    sort(e+,e++cnt,cmp);

    for(int i=;i<=cnt;i++){

        int p=find(e[i].from),q=find(e[i].to);

        if(p==q) continue;

        ans+=e[i].d; f[q]=p;

        sum++; if(sum==n) break;

    }printf("%.2lf\n",ans);

    return ;

}

2. prim 快好多啊稠密图n^2 比 kruskal 快好多啊QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int M=1e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,vis[M],f[M][M];

double x[M],y[M],ans,map[M][M],d[M];

double calc(int p,int q){return sqrt((x[p]-x[q])*(x[p]-x[q])+(y[p]-y[q])*(y[p]-y[q]));}

void prim(){

    d[]=; vis[]=;

    for(int i=;i<=n;i++) d[i]=map[][i];

    for(int i=;i<=n;i++){

        double mn=inf;

        int h=;

        for(int j=;j<=n;j++) if(!vis[j]&&mn>d[j]) mn=d[j],h=j;

        ans+=mn; d[h]=; vis[h]=;

        for(int j=;j<=n;j++) if(!vis[j]&&map[h][j]<d[j]) d[j]=map[h][j];

    }

}

int main()

{

    int p,q;

    n=read(); m=read();

    for(int i=;i<=n;i++) scanf("%lf %lf",&x[i],&y[i]);

    for(int i=;i<=m;i++){

        p=read(); q=read();

        f[p][q]=f[q][p]=;

    }

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)if(!f[i][j])

            map[i][j]=map[j][i]=calc(i,j);

    prim();

    printf("%.2lf\n",ans);

    return ;

}

bzoj 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

又一个代填的坑QAQ

这又是一道能用hash填的坑我们可以二分答案然后用hash套hash的方法写辣复杂度nlongn

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL unsigned long long

const int M=,P=,mod=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k;

LL w[M],f[M];

int first[mod],cnt,ans[M];

struct node{LL v; int next;}e[M];

int find(LL x){

    LL w=x%mod;

    for(int i=first[w];i;i=e[i].next)if(e[i].v==x) return i;

    e[++cnt]=(node){x,first[w]}; first[w]=cnt;

    return cnt;

}

bool check(int l){

    cnt=;

    memset(first,,sizeof(first));

    memset(ans,,sizeof(ans));

    for(int i=;i<=n-l+;i++){

        LL ly=f[i+l-]-f[i-]*w[l];

        int s=find(ly);

        ans[s]++;

        if(ans[s]>=k) return ;

    }

    return ;

}

int main(){

    n=read(); k=read();

    w[]=; for(int i=;i<=n;i++) w[i]=w[i-]*P;

    for(int i=;i<=n;i++) f[i]=f[i-]*P+read();

    if(k==) return printf("%d\n",n),;

    int l=,r=n;

    while(l<r){

        int mid=(l+r+)>>;

        if(check(mid)) l=mid;

        else r=mid-;

    }printf("%d\n",l);

    return ;

}

【bzoj1611】[Usaco2008 Feb]Meteor Shower流星雨-bfs

小心数组越界QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,xx[]={,,,,-},yy[]={,,,-,};

int map[][],vis[][];

struct node{int x,y,T;};

queue<node>q;

int main()

{

    for(int i=;i<=;i++) for(int j=;j<=;j++) map[i][j]=inf;

    int x,y,h;

    n=read();

    for(int i=;i<=n;i++){

        x=read(); y=read();

        h=read(); map[x][y]=min(map[x][y],h);

        for(int k=;k<=;k++){

            int nx=x+xx[k],ny=y+yy[k];

            if(nx<||ny<) continue;//小心数组越界

            map[nx][ny]=min(map[nx][ny],h);

        }

    }

    if(!map[][]) return printf("-1\n"),;

    vis[][]=;

    q.push((node){,,});

    while(!q.empty()){

        node s=q.front(); q.pop();

        if(map[s.x][s.y]==inf) return printf("%d\n",s.T),;

        for(int k=;k<=;k++){

            int nx=s.x+xx[k],ny=s.y+yy[k],nowh=s.T+;

            if(nx<||ny<||map[nx][ny]<=nowh||vis[nx][ny]) continue;

            vis[nx][ny]=;

            q.push((node){nx,ny,nowh});

        }

    }printf("-1\n");

    return ;

}

bzoj 1724: [Usaco2006 Nov]Fence Repair 切割木板

切割的逆过程就是合并所以切割木板=合并果子

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,k,ans;

struct node{

    LL w;

    bool operator <(const node& x)const {return x.w<w;}

};

priority_queue<node>q;

int main()

{

    n=read();

    for(int i=;i<=n;i++) k=read(),q.push((node){k});

    for(int i=;i<n;i++){

        node x=q.top(); q.pop();

        node y=q.top(); q.pop();

        int h=x.w+y.w;

        ans+=h;

        q.push((node){h});

    }printf("%lld\n",ans);

    return ;

}

bzoj 1621: [Usaco2008 Open]Roads Around The Farm分岔路口——模拟

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,ans;

queue<int>q;

int main()

{

    n=read(); k=read();

    q.push(n);

    while(!q.empty()){

        int x=q.front(); q.pop();

        if(x>k&&(x-k)%==){

            int now1=(x-k)/,now2=now1+k;

            q.push(now1);

            q.push(now2);

        }

        else ans++;

    }printf("%d\n",ans);

    return ;

}

bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛-二分求最长上升子序列

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,d,q[M],cnt;

int find(int w){

    int l=,r=cnt;

    while(l<=r){

        int mid=(l+r)>>;

        if(q[mid]<w) l=mid+;

        else r=mid-;

    }

    return l;

}

int main()

{

    n=read();

    k=read(); q[++cnt]=k;

    for(int i=;i<=n;i++){

        k=read();

        if(q[cnt]<k) q[++cnt]=k;

        else d=find(k),q[d]=k;

    }printf("%d\n",cnt);

    return ;

}

bzoj 1232: [Usaco2008Nov]安慰奶牛cheer——最小生成树

每条边的权值就是他的两个端点的c+他的长度*2

当然要记得选一个权值最小的点当作跟

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans=inf,n,m,first[M],cnt,c[M],f[M];

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

struct node{int from,to,w,next;}e[*M];

bool cmp(node a,node b){return a.w<b.w;}

void ins(int a,int b,int w){e[++cnt]=(node){a,b,w,first[a]}; first[a]=cnt;}

int main()

{

    int x,y,w;

    n=read(); m=read();

    for(int i=;i<=n;i++) c[i]=read(),f[i]=i,ans=min(ans,c[i]);

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),ins(x,y,(w<<)+c[x]+c[y]);

    sort(e+,e++cnt,cmp);

    int h=;

    for(int i=;i<=m;i++){

        int p=find(e[i].from),q=find(e[i].to);

        if(p==q) continue;

        f[q]=p; ans+=e[i].w;

        h++; if(h==n-) break;

    }printf("%d\n",ans);

}

bzoj 1636: [Usaco2007 Jan]Balanced Lineup-zkw线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=<<,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,q,l,r;

int mx[N<<],mn[N<<];

int push_ans(int l,int r){

    int mx1=,mn1=inf;

    for(l+=N-,r+=N+;r-l!=;l>>=,r>>=){

        if(~l&) mx1=max(mx1,mx[l^]),mn1=min(mn1,mn[l^]);

        if(r&)     mx1=max(mx1,mx[r^]),mn1=min(mn1,mn[r^]);

    }

    return mx1-mn1;

}

int main()

{

    n=read(); q=read();

    for(int i=;i<=n;i++) mx[N+i]=mn[N+i]=read();

    for(int i=N-;i;i--) mx[i]=max(mx[i<<],mx[i<<^]),mn[i]=min(mn[i<<],mn[i<<^]);

    for(int i=;i<=q;i++){

        l=read(); r=read();

        printf("%d\n",push_ans(l,r));

    }

    return ;

}

bzoj 1618: [Usaco2008 Nov]Buying Hay 购买干草——完全背包

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,h,mx,ans=inf;

int f[];

int c[],w[];

int main()

{

    n=read(); h=read();

    for(int i=;i<=n;i++) c[i]=read(),w[i]=read(),mx=max(mx,c[i]);

    memset(f,0x3f,sizeof(f)); f[]=;

    for(int i=;i<=n;i++)

        for(int j=c[i];j<h+mx;j++)

            f[j]=min(f[j],f[j-c[i]]+w[i]);

    for(int i=;i<mx;i++) ans=min(ans,f[h+i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1572: [Usaco2009 Open]工作安排Job——贪心+堆

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,cnt,ans;

struct pos{LL d,w;}e[M];

bool cmp(pos a,pos b){return a.d<b.d;}

priority_queue<LL>q;

int main()

{

    n=read();

    for(int i=;i<=n;i++) e[i].d=read(),e[i].w=read();

    sort(e+,e++n,cmp);

    for(int i=;i<=n;i++){

        ans+=e[i].w; q.push(-e[i].w); cnt++;

        if(cnt>e[i].d) cnt--,ans+=q.top(),q.pop();

    }printf("%lld\n",ans);

    return ;

}

bzoj 1631: [Usaco2007 Feb]Cow Party——spfa

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k;

int first[N],cnt,star[N],cntq;

struct node{int to,next,w;}e[M],q[M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insq(int a,int b,int w){q[++cntq]=(node){b,star[a],w}; star[a]=cnt;}

int d1[N],d2[N],vis[N];

queue<int>qu;

void spfa1(){

    memset(d1,0x3f,sizeof(d1));

    d1[k]=; vis[k]=; qu.push(k);

    while(!qu.empty()){

        int x=qu.front(); vis[x]=; qu.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(d1[now]>d1[x]+e[i].w){

                d1[now]=d1[x]+e[i].w;

                if(!vis[now]) qu.push(now),vis[now]=;

            }

        }

    }

}

void spfa2(){

    memset(d2,0x3f,sizeof(d2));

    d2[k]=; vis[k]=; qu.push(k);

    while(!qu.empty()){

        int x=qu.front(); vis[x]=; qu.pop();

        for(int i=star[x];i;i=q[i].next){

            int now=q[i].to;

            if(d2[now]>d2[x]+q[i].w){

                d2[now]=d2[x]+q[i].w;

                if(!vis[now]) qu.push(now),vis[now]=;

            }

        }

    }

}

int main()

{

    int x,y,w;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),ins(x,y,w),insq(y,x,w);

    spfa1();

    spfa2();

    int ans=;

    for(int i=;i<=n;i++) ans=max(ans,d1[i]+d2[i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1231: [Usaco2008 Nov]mixup2 混乱的奶牛——状压dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define LL long long

using namespace std;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int s,n,mn;

LL f[][<<],h[],w[];

int main()

{

    n=read(); mn=read(); s=(<<n)-;

    for(int i=;i<=n;i++) h[i]=read(),w[i]=<<(i-),f[i][w[i]]=;

    for(int k=;k<=s;k++)

        for(int i=;i<=n;i++)if(!(k&w[i]))

            for(int j=;j<=n;j++)if((k&w[j])&&abs(h[i]-h[j])>mn)

                f[i][k|w[i]]+=f[j][k];

    LL ans=;

    for(int i=;i<=n;i++) ans+=f[i][s];

    printf("%lld\n",ans);

    return ;

}

bzoj 1726: [Usaco2006 Nov]Roadblocks第二短路——spfa求次短路

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m;

int first[M],cnt;

struct node{int to,next,w;}e[];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int d1[M],d2[M],vis[M];

queue<int>q;

void spfa(){

    memset(d1,0x3f,sizeof(d1));

    memset(d2,0x3f,sizeof(d2));

    d1[]=; vis[]=; q.push();

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            bool f=false;

            int now=e[i].to;

            if(d1[x]+e[i].w<d1[now]) f=true,d2[now]=min(d1[now],d2[x]+e[i].w),d1[now]=d1[x]+e[i].w;

            else if(d1[x]+e[i].w>d1[now]&&d1[x]+e[i].w<d2[now]) f=true,d2[now]=d1[x]+e[i].w;

            else if(d2[x]+e[i].w<d2[now]) f=true,d2[now]=d2[x]+e[i].w;

            if(f&&!vis[now]) vis[now]=,q.push(now);

        }

        vis[x]=;

    }

}

int main()

{

    int x,y,w;

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    spfa();

    printf("%d\n",d2[n]);

    return ;

}

bzoj 1677: [Usaco2005 Jan]Sumsets 求和——完全背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int mod=1e9,M=1e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,f[M];

int main()

{

    n=read();

    f[]=;

    for(int i=;(<<i)<=n;i++){

        int now=<<i;

        for(int j=now;j<=n;j++) (f[j]+=f[j-now])%=mod;

    }printf("%d\n",f[n]);

    return ;

}

bzoj 1657: [Usaco2006 Mar]Mooo 奶牛的歌声——单调栈

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,h[M],v[M];

int st[M],top,s[M],ans;

int main()

{

    n=read();

    for(int i=;i<=n;i++) h[i]=read(),v[i]=read();

    for(int i=;i<=n;i++){

        while(top&&h[st[top]]<h[i]) s[i]+=v[st[top--]];

        st[++top]=i;

    }

    top=;

    for(int i=n;i;i--){

        while(top&&h[st[top]]<h[i]) s[i]+=v[st[top--]];

        st[++top]=i;

    }

    for(int i=;i<=n;i++) ans=max(ans,s[i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1646: [Usaco2007 Open]Catch That Cow 抓住那只牛——bfs

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int mx=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int s,k,now,d[mx+];

queue<int>q;

int main()

{

    s=read(); k=read();

    q.push(s); d[s]=;

    if(s>=k) return printf("%d\n",s-k),;

    while(!q.empty()){

        int x=q.front(); q.pop();

        now=x+;if(now>=&&now<=mx&&!d[now]) d[now]=d[x]+,q.push(now);

        now=x-;if(now>=&&now<=mx&&!d[now]) d[now]=d[x]+,q.push(now);

        now=*x;if(now>=&&now<=mx&&!d[now]) d[now]=d[x]+,q.push(now);

        if(d[k]) return printf("%d\n",d[k]-),;

    }

    return ;

}

bzoj 1660: [Usaco2006 Nov]Bad Hair Day 乱发节——单调栈

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int h[M],n;

LL ans;

int st[M],top;

int main()

{

    n=read();

    for(int i=;i<=n;i++) h[i]=read();

    for(int i=;i<=n;i++){

        while(top&&h[st[top]]<=h[i]) top--;

        ans+=top; st[++top]=i;

    }printf("%lld\n",ans);

    return ;

}

bzoj 1734: [Usaco2005 feb]Aggressive cows 愤怒的牛——二分

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,x[M];

int check(int k){

    int sum=x[],cnt=;

    for(int i=;i<=n;i++)if(x[i]-sum>=k) cnt++,sum=x[i];

    return cnt>=m;

}

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) x[i]=read();

    sort(x+,x++n);

    int l=,r=x[n];

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) l=mid+;

        else r=mid-;

    }printf("%d\n",r);

    return ;

}

bzoj 1679: [Usaco2005 Jan]Moo Volume 牛的呼声——排序

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,x[M];

LL ans;

int main()

{

    n=read();

    for(int i=;i<=n;i++) x[i]=read();

    sort(x+,x++n);

    LL sum=x[];

    for(int i=;i<=n;i++) ans=ans+1LL*(i-)*x[i]-sum,sum+=x[i];

    printf("%lld\n",ans*);

    return ;

}

bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级——分层图+Dijkstra

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int N=,inf=0x7f7f7f7f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k;

int d[N][];

struct node{

    int d,h,pos;

    bool operator <(const node& x)const{return x.d<d;}

};

priority_queue<node>q;

int first[N],cnt;

struct pos{int to,next,w;}e[*N];

void ins(int a,int b,int w){e[++cnt]=(pos){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int dj(){

    memset(d,0x7f,sizeof(d));

    for(int i=;i<=k;i++) d[][i]=;

    q.push((node){,,});

    while(!q.empty()){

        node p=q.top(); q.pop();

        if(d[p.pos][p.h]!=p.d) continue;

        if(p.pos==n) return p.d;

        int x=p.pos,h=p.h;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(d[now][h]>d[x][h]+e[i].w) d[now][h]=d[x][h]+e[i].w,q.push((node){d[now][h],h,now});

            if(h<k&&d[now][h+]>d[x][h]) d[now][h+]=d[x][h],q.push((node){d[now][h+],h+,now});

        }

    }

    return d[n][k];

}

int main()

{

    int x,y,v;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),v=read(),insert(x,y,v);

    printf("%d\n",dj());

    return ;

}

bzoj 1711: [Usaco2007 Open]Dining吃饭——网络流

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

const int M=1e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k;

int S,T,N,ans;

int first[M],cur[M],cnt=;

struct node{int to,next,flow;}e[M*M];

void ins(int a,int b,int flow){e[++cnt]=(node){b,first[a],flow}; first[a]=cnt;}

void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}

int d[M];

queue<int>q;

int bfs(){

    memset(d,-,sizeof(d));

    d[S]=; q.push(S);

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(e[i].flow&&d[now]==-) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int flow=,f;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]==d[x]+&&(f=dfs(now,min(e[i].flow,a)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

int main()

{

    int x,y,v;

    n=read(); m=read(); k=read();

    S=; T=n*+m+k+; N=n*;

    for(int i=;i<=n;i++) insert(i,i+n,);

    for(int i=;i<=m;i++) insert(S,i+N,);

    for(int i=;i<=k;i++) insert(i+N+m,T,);

    for(int i=;i<=n;i++){

        x=read(); y=read();

        for(int j=;j<=x;j++) v=read(),insert(v+N,i,);

        for(int j=;j<=y;j++) v=read(),insert(i+n,v+N+m,);

    }

    while(bfs()){

        for(int i=S;i<=T;i++) cur[i]=first[i];

        ans+=dfs(S,inf);

    }printf("%d\n",ans);

    return ;

}

bzoj 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚——差分

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=1e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,s[M],l,r,mx;

int main()

{

    n=read();

    for(int i=;i<=n;i++){

        l=read(); r=read();

        mx=max(mx,r);

        s[l]++; s[r+]--;

    }

    int sum=,ans=;

    for(int i=;i<=mx;i++) sum+=s[i],ans=max(ans,sum);

    printf("%d\n",ans);

    return ;

}

bzoj 1690: [Usaco2007 Dec]奶牛的旅行——分数规划+spfa判负环

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=1e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

bool f;

int n,m,v[M];

int first[M],cnt;

struct node{int to,next,w; double h;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w,}; first[a]=cnt;}

int vis[M];

double d[M];

void dfs(int x){

    vis[x]=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]>d[x]+e[i].h){

            if(vis[now]){f=true; return ;}

            d[now]=d[x]+e[i].h;

            dfs(now);

        }

    }

    vis[x]=;

}

bool check(double k){

    for(int i=;i<=cnt;i++) e[i].h=k*e[i].w-v[e[i].to];

    for(int i=;i<=n;i++) d[i]=vis[i]=;

    f=false;

    for(int i=;i<=n;i++){dfs(i); if(f) return ;}

    return ;

}

int main()

{

    int x,y,w;

    n=read(); m=read();

    for(int i=;i<=n;i++) v[i]=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),ins(x,y,w);

    double l=0.0,r=;

    while(r-l>1e-){

        double mid=(l+r)/;

        if(check(mid)) l=mid;

        else r=mid;

    }printf("%.2f\n",l);

    return ;

}

bzoj 1708: [Usaco2007 Oct]Money奶牛的硬币——完全背包

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,c[];

LL f[];

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) c[i]=read();

    f[]=;

    for(int i=;i<=n;i++)

        for(int j=c[i];j<=m;j++)

            f[j]+=f[j-c[i]];

    printf("%lld\n",f[m]);

    return ;

}

bzoj 1634: [Usaco2007 Jan]Protecting the Flowers 护花——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n;

struct node{

    int T,d;

    bool operator <(const node& x)const{return T*x.d<x.T*d;}

}e[M];

LL ans,sum;

int main()

{

    n=read();

    for(int i=;i<=n;i++) e[i].T=read(),e[i].d=read(),sum+=e[i].d;

    sort(e+,e++n);

    for(int i=;i<=n;i++){

        sum-=e[i].d;

        ans+=*e[i].T*sum;

    }printf("%lld\n",ans);

    return ;

}

bzoj 1629: [Usaco2007 Demo]Cow Acrobats——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,ans,sum;

struct node{int w,s;}e[M];

bool cmp(node a,node b){return b.s-a.w>a.s-b.w;}

int main()

{

    n=read();

    for(int i=;i<=n;i++) e[i].w=read(),e[i].s=read();

    sort(e+,e++n,cmp);

    ans=-e[].s; sum=e[].w;

    for(int i=;i<=n;i++){

        ans=max(ans,sum-e[i].s);

        sum+=e[i].w;

    }printf("%d\n",ans);

    return ;

}

bzoj 1725: [Usaco2006 Nov]Corn Fields牧场的安排——状压dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int mod=1e9;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,cnt,ans;

int s[],f[][];

bool pd(int x){return (x&(x<<))==;}

int main()

{

    n=read(); m=read(); cnt=(<<m)-;

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) s[i]=(s[i]<<)+(read()^);

    for(int i=;i<=cnt;i++) if(pd(i)&&!(i&s[])) f[][i]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=cnt;j++) if(!(j&s[i])&&pd(j))

        for(int k=;k<=cnt;k++) if(!(j&k)&&!(k&s[i-])&&pd(k))

        (f[i][j]+=f[i-][k])%=mod;

    for(int i=;i<=cnt;i++) (ans+=f[n][i])%=mod;

    printf("%d\n",ans);

    return ;

}

bzoj 1620: [Usaco2008 Nov]Time Management 时间管理——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=1e3+,mod=1e9;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,ans=1e6+;

struct node{int T,s;}e[M];

bool cmp(node a,node b){return a.s>b.s;}

int main()

{

    n=read();

    for(int i=;i<=n;i++) e[i].T=read(),e[i].s=read();

    sort(e+,e++n,cmp);

    for(int i=;i<=n;i++) ans=min(ans,e[i].s)-e[i].T;

    if(ans<) printf("-1\n");

    else printf("%d\n",ans);

    return ;

}

bzoj 1827: [Usaco2010 Mar]gather 奶牛大集会——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=1e6+;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,c[M];

LL sz[M],ans,dis[M];

int first[M],cnt;

struct node{int to,next; LL w;}e[*M];

void ins(int a,int b,LL w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,LL w){ins(a,b,w); ins(b,a,w);}

LL dfs(int x,int fa){

    LL sum=dis[x]*c[x];

    sz[x]=c[x];

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to; if(now==fa) continue;

        dis[now]=dis[x]+e[i].w;

        sum+=dfs(now,x);

        sz[x]+=sz[now];

    }

    return sum;

}

void mov(int x,int fa){

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to; if(now==fa) continue;

        if(sz[]-*sz[now]<){

            ans+=e[i].w*(sz[]-*sz[now]);

            mov(now,x); return ;

        }

    }

}

int main()

{

    LL x,y,w;

    n=read();

    for(int i=;i<=n;i++) c[i]=read();

    for(int i=;i<n;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    ans=dfs(,-);

    mov(,-);

    printf("%lld\n",ans);

    return ;

}

bzoj 1639: [Usaco2007 Mar]Monthly Expense 月度开支——二分

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,ans,l,r;

int w[M];

int check(int k){

    int sum=,cnt=;

    for(int i=;i<=n;i++)

        if(sum+w[i]<=k) sum+=w[i];

        else{

            sum=w[i]; cnt++;

            if(cnt>m||w[i]>k) return ;

        }

    return ;

}

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) w[i]=read(),r+=w[i];

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) ans=mid,r=mid-;

        else l=mid+;

    }printf("%d\n",ans);

    return ;

}

临时改变计划 silver刷不下去了QAQ 现在先刷gold

bzoj2442: [Usaco2011 Open]修剪草坪——单调队列优化dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=;

const LL inf=1e15;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k;

int head,tail,q[M];

LL ans,f[M],h[M],mn=inf;

int main()

{

    n=read(); k=read();

    for(int i=;i<=n;i++) h[i]=read(),ans+=h[i];

    for(int i=;i<=n;i++){

        f[i]=f[q[head]]+h[i];

        while(head<=tail&&f[q[tail]]>f[i]) tail--;

        q[++tail]=i;

        while(head<=tail&&i-q[head]>k) head++;

    }

    for(int i=n-k;i<=n;i++) mn=min(mn,f[i]);

    printf("%lld\n",ans-mn);

    return ;

}

bzoj 1592: [Usaco2008 Feb]Making the Grade 路面修整——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,s[M],h[M],f[M],ff[M];

int main()

{

    n=read(); for(int i=;i<=n;i++) s[i]=read(),h[i]=s[i];

    sort(h+,h++n);

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            f[j]+=abs(s[i]-h[j]);

            if(j>) f[j]=min(f[j],f[j-]);

        }

        for(int j=n;j;j--){

            ff[j]+=abs(s[i]-h[j]);

            if(j<n) ff[j]=min(ff[j],ff[j+]);

        }

    }

    printf("%d\n",min(f[n],ff[]));

    return ;

}

bzoj 1576: [Usaco2009 Jan]安全路经Travel——dijkstra+并查集

题解我博客有另写请搜索bzoj 1576（记得加空格）另外spfa会被卡

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=1e5+,M=4e5+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,ans[N];

int f[N],fa[N];

int find(int x){while(x!=f[x]) x=f[x]=f[f[x]]; return x;}

int first[N],cnt,cntq;

struct node{int from,to,next,w;}e[M],qs[M];

bool cmp(node a,node b){return a.w<b.w;}

void ins(int a,int b,int w){e[++cnt]=(node){a,b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int dis[N],dep[N];

struct Q{

    int d,pos;

    bool operator <(const Q& x)const{return x.d<d;}

};

priority_queue<Q>q;

void dj(){

    memset(dis,0x3f,sizeof(dis));

    q.push((Q){,}); dis[]=;

    while(!q.empty()){

        Q p=q.top(); q.pop();

        if(p.d>dis[p.pos]) continue;

        int x=p.pos;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x]+e[i].w){

                dis[now]=dis[x]+e[i].w;

                dep[now]=dep[x]+;

                fa[now]=x;

                q.push((Q){dis[now],now});

            }

        }

    }

    //for(int i=1;i<=n;i++) printf("[%d] ",dis[i]); printf("\n");

}

int main(){

    int x,y,w;

    n=read(); m=read();

    for(int i=;i<=n;i++) f[i]=i;

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    dj();

    for(int i=;i<=cnt;i++){

        x=e[i].from; y=e[i].to;

        if(dep[x]<dep[y]) swap(x,y);

        if(dis[x]==dis[y]+e[i].w) continue;

        qs[++cntq]=(node){x,y,,dis[x]+dis[y]+e[i].w};

    }

    sort(qs+,qs++cntq,cmp);

    for(int i=;i<=cntq;i++){

        x=qs[i].from; y=qs[i].to;

        while(x!=y){

            if(dep[x]<dep[y]) swap(x,y);

            if(!ans[x]) ans[x]=qs[i].w-dis[x];

            x=f[x]=find(fa[x]); //printf("[%d]\n",x);

        }

    }

    for(int i=;i<=n;i++){

        if(!ans[i]) printf("-1\n");

        else printf("%d\n",ans[i]);

    }

    return ;

}

bzoj 1782: [Usaco2010 Feb]slowdown 慢慢游——dfs序

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=2e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,sum,l[M],r[M],pos[M],k;

int first[M],cnt;

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void dfs(int x,int fa){

    pos[x]=l[x]=++sum;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        dfs(now,x);

    }

    r[x]=sum;

}

int s[M];

int lowbit(int x){return x&-x;}

int query(int x){

    int ans=;

    while(x){ans+=s[x]; x-=lowbit(x);}

    return ans;

}

void add(int x,int v){

    while(x<=n){

        s[x]+=v;

        x+=lowbit(x);

    }

}

int main(){

    int x,y;

    n=read();

    for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    dfs(,);

    for(int i=;i<=n;i++){

        k=read();

        int lx=l[k],rx=r[k];

        printf("%d\n",query(pos[k]));

        add(lx,); add(rx+,-);

    }

    return ;

}

bzoj 1596: [Usaco2008 Jan]电话网络——贪心+dfs

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=2e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,n,mark[M];

int first[M],cnt;

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void dfs(int x,int fa){

    bool f=false;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        dfs(now,x);

        if(mark[now]) f=;

    }

    if(!f&&!mark[x]&&!mark[fa]){ans++; mark[fa]=;}

}

int main(){

    int x,y;

    n=read(); for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    dfs(,);

    printf("%d\n",ans);

    return ;

}

bzoj 1692: [Usaco2007 Dec]队列变换——二分+hash

强行hash代替后缀数组QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,P=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,cnt;

char s[M],ans[M];

unsigned long long h1[M],h2[M],w[M];

int find(int x,int y){

    if(s[x]!=s[y]) return ;

    int l=,r=y-x+;

    while(l<r){

        int mid=(l+r)>>;

        if(h1[x+mid]-h1[x-]*w[mid+]==h2[y-mid]-h2[y+]*w[mid+]) l=mid+;

        else r=mid;

    }//printf("%d %d [%d]\n",x,y,l);

    return l;

}

void prepare(){

    w[]=;

    for(int i=;i<=n;i++) w[i]=w[i-]*P;

}

int main(){

    n=read(); prepare();

    for(int i=;i<=n;i++) scanf("%s",s+i);

    for(int i=;i<=n;i++) h1[i]=h1[i-]*P+s[i];

    for(int i=n;i;i--) h2[i]=h2[i+]*P+s[i];

    int l=,r=n;

    while(l<=r){

        int d=find(l,r);

        if(s[l+d]<s[r-d]) ans[++cnt]=s[l],l++;

        else ans[++cnt]=s[r],r--;

    }//printf("[%d]\n",cnt);

    for(int i=;i<=cnt;++i){

        putchar(ans[i]);

        if(i%==)putchar();

    }

    return ;

}

bzoj 1715: [Usaco2006 Dec]Wormholes 虫洞——spfa判负环

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int T,n,m,k,vis[M],d[M];

int first[M],cnt;

struct node{int to,next,w;}e[];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

bool f;

void dfs(int x){

    vis[x]=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]>d[x]+e[i].w){

            if(vis[now]){f=true; return ;}

            d[now]=d[x]+e[i].w;

            dfs(now);

        }

    }

    vis[x]=;

}

int pd(){

    f=false;

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++){

        memset(d,,sizeof(d));

        dfs(i);

        if(f) return ;

    }

    return ;

}

int main(){

    T=read();

    while(T--){

        int x,y,w;

        cnt=; memset(first,,sizeof(first));

        n=read(); m=read(); k=read();

        for(int i=;i<=m;i++) x=read(),y=read(),w=read(),insert(x,y,w);

        for(int i=;i<=k;i++) x=read(),y=read(),w=read(),ins(x,y,-w);

        if(pd()) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

bzoj 1596: [Usaco2008 Jan]电话网络——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int M=2e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,n,mark[M];

int first[M],cnt;

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void dfs(int x,int fa){

    bool f=false;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        dfs(now,x);

        if(mark[now]) f=;

    }

    if(!f&&!mark[x]&&!mark[fa]){ans++; mark[fa]=;}

}

int main(){

    int x,y;

    n=read(); for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    dfs(,);

    printf("%d\n",ans);

    return ;

}

bzoj 1571: [Usaco2009 Open]滑雪课Ski——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=,N=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int T,n,m,ans;

int s[M],d[M],h[M],mn[N];

int c[M],w[M];

int f[M][N],k[M][N],g[M][N];

int main(){

    T=read(); n=read(); m=read();

    for(int i=;i<=n;i++) s[i]=read(),d[i]=read(),h[i]=read(),k[s[i]+d[i]][h[i]]=s[i];

    for(int i=;i<=m;i++) c[i]=read(),w[i]=read();

    memset(mn,0x3f,sizeof(mn));

    memset(f,-0x3f,sizeof(f));

    memset(g,-0x3f,sizeof(g));

    for(int i=;i<=;i++)

     for(int j=;j<=m;j++)if(c[j]<=i) mn[i]=min(mn[i],w[j]);

    f[][]=g[][]=;

    for(int i=;i<=T;i++){

        for(int j=;j<=;j++){

            f[i][j]=f[i-][j];

            if(i>=mn[j]) f[i][j]=max(f[i][j],f[i-mn[j]][j]+);

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

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

        }

    }

    for(int i=;i<=;i++) ans=max(ans,f[T][i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1770: [Usaco2009 Nov]lights 燈

1.折半搜索

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int mod=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans[<<],n,m,h,mn=inf;

LL p[],tot;

bool f;

int first[mod],cnt;

struct node{LL v; int next;}e[<<];

int get(LL w){

    int x=w%mod;

    for(int i=first[x];i;i=e[i].next) if(e[i].v==w) return i;

    e[++cnt]=(node){w,first[x]}; first[x]=cnt;

    return cnt;

}

void dfs(int x,LL now,int step){

    if(x==h+){

        int k;

        if(now==tot) mn=min(mn,step);

        if(!f){

            k=get(now);

            if(!ans[k]||ans[k]>step) ans[k]=step;

        }

        else{

            k=get(tot-now);

            if(!ans[k]) return ;

            mn=min(mn,ans[k]+step);

        }

        return ;

    }

    dfs(x+,now,step);

    dfs(x+,now^p[x],step+);

}

int main(){

    int x,y;

    n=read(); m=read(); tot=(1LL<<n)-;

    for(int i=;i<=n;i++) p[i]=1LL<<(i-);

    for(int i=;i<=m;i++){

        x=read(); y=read();

        p[x]^=1LL<<(y-); p[y]^=1LL<<(x-);

    }

    f=false; h=n/; dfs(,,);

    f=true;  h=n; dfs(n/+,,);

    printf("%d\n",mn);

    return ;

}

2.高斯消元——待填

bzoj 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富——dp（最长路）

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,now;

int s[N][N],d[N][N];

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) s[i][j]=read();

    memset(d,-0x3f,sizeof(d)); d[][]=s[][];

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++){

            now=j-;if(now>=&&now<=n) d[j][i]=max(d[j][i],d[now][i-]+s[j][i]);

            now=j;  if(now>=&&now<=n) d[j][i]=max(d[j][i],d[now][i-]+s[j][i]);

            now=j+;if(now>=&&now<=n) d[j][i]=max(d[j][i],d[now][i-]+s[j][i]);

        }

    printf("%d\n",d[n][m]);

    return ;

}

bzoj 1691: [Usaco2007 Dec]挑剔的美食家——贪心+平衡树

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#define LL long long

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m;

LL ans;

struct node{

    int w,c;

    bool operator <(const node& x)const{return x.c<c;}

}e[M],q[M];

std::multiset<int>tr;

std::multiset<int>::iterator it;

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++) e[i].w=read(),e[i].c=read();

    for(int i=;i<=m;i++) q[i].w=read(),q[i].c=read();

    std::sort(e+,e++n);

    std::sort(q+,q++m);

    int k=;

    for(int i=;i<=n;i++){

        while(k<=m&&q[k].c>=e[i].c) tr.insert(q[k++].w);

        it=tr.lower_bound(e[i].w);

        if(it!=tr.end()) ans+=*it,tr.erase(it);

        else return puts("-1"),;

    }printf("%lld\n",ans);

    return ;

}

bzoj 1593: [Usaco2008 Feb]Hotel 旅馆——线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=<<;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int k,d,n,m,L,R;

struct node{int l,r,lr,rl,mx,h[];}tr[M];

void up(int x){

    int l=x<<,r=x<<^;

    tr[x].lr=tr[l].lr;

    if(tr[l].lr==tr[l].r-tr[l].l+) tr[x].lr=tr[l].lr+tr[r].lr;

    tr[x].rl=tr[r].rl;

    if(tr[r].rl==tr[r].r-tr[r].l+) tr[x].rl=tr[r].rl+tr[l].rl;

    tr[x].mx=max(max(tr[l].mx,tr[r].mx),tr[l].rl+tr[r].lr);

}

void calc(int x){

    tr[x].lr=tr[x].rl=tr[x].mx=;

    tr[x].h[]=; tr[x].h[]=;

}

void calc1(int x){

    tr[x].lr=tr[x].rl=tr[x].mx=tr[x].r-tr[x].l+;

    tr[x].h[]=; tr[x].h[]=;

}

void down(int x){

    int l=x<<,r=x<<^;

    if(tr[x].h[]){

        calc(l); calc(r);

        tr[x].h[]=;

    }

    if(tr[x].h[]){

        calc1(l); calc1(r);

        tr[x].h[]=;

    }

}

void build(int x,int l,int r){

    tr[x].l=l; tr[x].r=r;

    if(l==r){

        tr[x].lr=tr[x].rl=tr[x].mx=;

        return ;

    }

    int mid=(l+r)>>;

    build(x<<,l,mid);

    build(x<<^,mid+,r);

    up(x);

}

void modify(int x,int s){

    if(L<=tr[x].l&&tr[x].r<=R){

        if(s==) calc(x);

        else calc1(x);

        return ;

    }

    down(x);

    int mid=(tr[x].l+tr[x].r)>>;

    if(L<=mid) modify(x<<,s);

    if(R>mid) modify(x<<^,s);

    up(x);

}

int find(int x,int d){

    down(x);

    int l=x<<,r=x<<^,mid=(tr[x].l+tr[x].r)>>;

    if(tr[x].l==tr[x].r) return l;

    if(tr[l].mx>=d) return find(l,d);

    if(tr[l].rl+tr[r].lr>=d) return mid-tr[l].rl+;

    return find(r,d);

}

int main(){

    n=read(); m=read();

    build(,,n);

    for(int i=;i<=m;i++){

        k=read();

        if(k==){

            d=read();

            if(tr[].mx<d) printf("0\n");

            else{

                int y=find(,d);

                printf("%d\n",y);

                L=y; R=y+d-;

                modify(,);

            }

        }

        else{

            L=read(); R=L+read()-;

            modify(,);

        }

    }

    return ;

}

bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居——排序+贪心+set

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#include<queue>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,c;

int f[M],h[M],ans,mx;

int find(int x){while(f[x]!=x) x=f[x]=f[f[x]]; return x;}

struct node{

    int x,y,id;

    bool operator <(const node& k)const{return x<k.x;}

}e[M];

struct pos{

    int y,id;

    bool operator <(const pos& k)const{return y!=k.y?y<k.y:id<k.id;}

};

std::queue<int>q;

std::multiset<pos>tr;

std::multiset<pos>::iterator it;

int main(){

    int x,y;

    n=read(); c=read();

    for(int i=;i<=n;i++){

        x=read(); y=read();

        f[i]=i; e[i].x=x+y,e[i].y=x-y; e[i].id=i;

    }

    sort(e+,e++n);

    for(int i=;i<=n;i++){

        while(!q.empty()&&e[i].x-e[q.front()].x>c){

            int now=q.front(); q.pop();

            tr.erase(tr.find((pos){e[now].y,e[now].id}));

        }

        q.push(i);

        it=tr.insert((pos){e[i].y,e[i].id});

        if(it!=tr.begin()){

            --it;

            if(e[i].y-(it->y)<=c){

                int p=find(e[i].id),q=find(it->id);

                f[q]=p;

            }

            ++it;

        }

        ++it;

        if(it!=tr.end()){

            if(it->y-e[i].y<=c){

                int p=find(e[i].id),q=find(it->id);

                f[q]=p;

            }

        }

    }

    for(int i=;i<=n;i++){

        int x=find(e[i].id);

        if(!h[x]) ans++;

        h[x]++; mx=max(mx,h[x]);

    }printf("%d %d\n",ans,mx);

    return ;

}

bzoj 1697: [Usaco2007 Feb]Cow Sorting牛排序——置换

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,v[M],s[M],vis[M],ans;

void mins(int &x,int y){if(y<x) x=y;}

int min(int x,int y){return x<y?x:y;}

int main(){

    n=read();

    for(int i=;i<=n;i++) v[i]=s[i]=read();

    sort(s+,s++n);

    for(int i=;i<=n;i++)if(!vis[i]){

        int mn=v[i],sum=v[i],now=i,h=;

        while(){

            vis[now=lower_bound(s+,s++n,v[now])-s]=;

            if(now==i) break;

            h++; mins(mn,v[now]);

            sum+=v[now];

        }

        ans=ans+min((sum-mn)+(h-)*mn,(s[]+mn)*+(sum-mn)+(h-)*s[]);

    }printf("%d\n",ans);

    return ;

}

bzoj 1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果——拓扑排序求基环树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,to[M],in[M],stk[M],top,f[M];

int head,tail,q[M];

int main(){

    n=read();

    for(int i=;i<=n;i++) to[i]=read(),in[to[i]]++;

    for(int i=;i<=n;i++) if(!in[i]) q[tail++]=i;

    while(head<=tail){

        int x=q[head++],now=to[x];

        in[now]--;

        if(!in[now]) q[tail++]=now;

    }

    for(int i=;i<=n;i++)if(in[i]){

        int now=i,h=;

        stk[top=]=i; in[i]=;

        while(){

            now=to[now];

            if(now==i) break;

            h++; in[now]=; stk[++top]=now;

        }

        while(top) f[stk[top]]=h,top--;

    }

    while(tail>) tail--,f[q[tail]]=f[to[q[tail]]]+;

    for(int i=;i<=n;i++) printf("%d\n",f[i]);

    return ;

}

bzoj 1574: [Usaco2009 Jan]地震损坏Damage——贪心+搜索

因为你一个点附近的点如果能够使其他点到达1那他也一定可以然这个点到达1

所以把走不到1的点全部删掉然后dfs一次就行了

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,ans;

int first[M],cnt,mark[M],vis[M];

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void delet(int x){for(int i=first[x];i;i=e[i].next) mark[e[i].to]=;}

void dfs(int x){

    vis[x]=; ans--;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!mark[now]&&!vis[now]) dfs(now);

    }

}

int main(){

    int x,y;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),insert(x,y);

    for(int i=;i<=k;i++) x=read(),delet(x);

    ans=n; dfs();

    printf("%d\n",ans);

    return ;

}

bzoj 1707: [Usaco2007 Nov]tanning分配防晒霜——排序贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

const int M=;

char buf[M*],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

int n,m,ans;

struct node{

    int l,r;

    bool operator <(const node& x)const{return r<x.r;}

}e[M];

struct pos{

    int w,h;

    bool operator <(const pos& x)const{return w<x.w;}

}q[M];

struct Q{

    int w,id;

    bool operator <(const Q& x)const{return w!=x.w?w<x.w:id<x.id;}

};

std::multiset<Q>tr;

std::multiset<Q>::iterator it;

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=read(); m=read();

    for(int i=;i<=n;i++) e[i].l=read(),e[i].r=read();

    std::sort(e+,e++n);

    for(int i=;i<=m;i++) q[i].w=read(),q[i].h=read();

    std::sort(q+,q++m);

    int k=;

    for(int i=;i<=n;i++){

        while(k<=m&&q[k].w<=e[i].r) tr.insert((Q){q[k].w,k}),k++;

        it=tr.lower_bound((Q){e[i].l,-});

        if(it!=tr.end()){

            ans++; q[it->id].h--;

            if(!q[it->id].h) tr.erase(it);

        }

    }printf("%d\n",ans);

    return ;

}

bzoj 1709: [Usaco2007 Oct]Super Paintball超级弹珠——暴力

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,s[][M][M],f[M][M],ans;

int main(){

    int x,y;

    n=read(); k=read();

    for(int i=;i<=k;i++){

        x=read(); y=read(); f[x][y]++;

        for(int k=;k<=;k++) s[k][x][y]++;

    }

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            s[][i][j]+=s[][i][j-];

            s[][i][j]+=s[][i-][j-];

            s[][i][j]+=s[][i-][j];

            s[][i][j]+=s[][i-][j+];

        }

    for(int i=n;i;i--)

        for(int j=n;j;j--){

            s[][i][j]+=s[][i][j+];

            s[][i][j]+=s[][i+][j-];

            s[][i][j]+=s[][i+][j];

            s[][i][j]+=s[][i+][j+];

        }

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            for(int k=;k<=;k++) s[][i][j]+=s[k][i][j];

            if(f[i][j]) s[][i][j]-=*f[i][j];

        }

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)if(s[][i][j]==k) ans++;

    printf("%d\n",ans);

    return ;

}

bzoj 1828: [Usaco2010 Mar]balloc 农场分配——线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=1e5+,N=<<,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,ans,L,R;

struct node{int l,r;}q[M];

bool cmp(node a,node b){return a.r!=b.r?a.r<b.r:a.l>b.l;}

struct pos{int l,r,mn,tag;}tr[N];

void up(int x){tr[x].mn=std::min(tr[x<<].mn,tr[x<<^].mn);}

void down(int x){

    if(tr[x].tag){

        int v=tr[x].tag; tr[x].tag=;

        tr[x<<].tag+=v; tr[x<<^].tag+=v;

        tr[x<<].mn-=v;  tr[x<<^].mn-=v;

    }

}

void build(int x,int l,int r){

    tr[x].l=l; tr[x].r=r;

    if(l==r){tr[x].mn=read();return ;}

    int mid=(l+r)>>;

    build(x<<,l,mid);

    build(x<<^,mid+,r);

    up(x);

}

int pmin(int x){

    if(L<=tr[x].l&&tr[x].r<=R) return tr[x].mn;

    int mid=(tr[x].l+tr[x].r)>>,mn=inf;

    down(x);

    if(L<=mid) mn=std::min(mn,pmin(x<<));

    if(R>mid) mn=std::min(mn,pmin(x<<^));

    return mn;

}

void modify(int x){

    if(L<=tr[x].l&&tr[x].r<=R){tr[x].mn-=; tr[x].tag++; return ;}

    int mid=(tr[x].l+tr[x].r)>>;

    down(x);

    if(L<=mid) modify(x<<);

    if(R>mid) modify(x<<^);

    up(x);

}

int main(){

    n=read(); m=read();

    build(,,n);

    for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read();

    std::sort(q+,q++m,cmp);

    for(int i=;i<=m;i++){

        L=q[i].l; R=q[i].r;

        if(pmin()>=) ans++,modify();

    }printf("%d\n",ans);

    return ;

}

bzoj 1706: [usaco2007 Nov]relays 奶牛接力跑——倍增floyd（裸

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=1e3+,inf=0x3f3f3f3f,mod=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,S,T;

int first[mod],cnt;

struct node{int v,next;}e[M];

int get(int w){

    int x=w%mod;

    for(int i=first[x];i;i=e[i].next) if(e[i].v==w) return i;

    e[++cnt]=(node){w,first[x]}; first[x]=cnt; return cnt;

}

void mins(int &x,int y){if(x>y) x=y;}

typedef int mat[M][M];

mat f,ans,tmp;

void floyd(mat b,mat c){

    memset(tmp,0x3f,sizeof(mat));

    for(int i=;i<=cnt;i++)

    for(int k=;k<=cnt;k++)

    for(int j=;j<=cnt;j++) mins(tmp[i][j],b[i][k]+c[k][j]);

    memcpy(b,tmp,sizeof(mat));

}

int main(){

    int x,y,w;

    memset(f,0x3f,sizeof(mat));

    n=read(); m=read(); S=get(read()); T=get(read());

    for(int i=;i<=m;i++) w=read(),x=get(read()),y=get(read()),f[x][y]=f[y][x]=std::min(f[x][y],w);

    memset(ans,0x3f,sizeof(mat));

    for(int i=;i<=cnt;i++) ans[i][i]=;

    for(;n;n>>=,floyd(f,f)) if(n&) floyd(ans,f);

    printf("%d\n",ans[S][T]);

    return ;

}

bzoj 1584: [Usaco2009 Mar]Cleaning Up 打扫卫生——$nsqrt(n)$ DP

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define LL long long

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,d;

int c[M],last[M],now[M],q[M],f[M];

void mins(int &x,int y){if(x>y) x=y;}

int main(){

    n=read(); m=read(); d=sqrt(n);

    for(int i=;i<=m;i++) last[i]=-;

    for(int i=;i<=n;i++) c[i]=read(),now[i]=last[c[i]],last[c[i]]=i;

    for(int i=;i<=n;i++){

        int k=; while(k<=d&&q[k]>now[i]) k++; k--;

        f[i]=i; q[]=i;

        for(int j=std::min(k,d);j;j--) q[j]=q[j-];

        for(int j=;j<=d;j++) mins(f[i],f[q[j]-]+j*j);

    }printf("%d\n",f[n]);

    return ;

}

bzoj 1754: [Usaco2005 qua]Bull Math——高精度x高精度

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

char s1[M],s2[M];

int cnt1,cnt2,b[M],c[M],ans[*M],cntq;

int main(){

    scanf("%s%s",s1,s2);

    cnt1=strlen(s1); cnt2=strlen(s2);

    for(int i=;i<cnt1;++i) b[i]=s1[cnt1-i-]-'';

    for(int i=;i<cnt2;++i) c[i]=s2[cnt2-i-]-'';

    cntq=cnt1+cnt2;

    for(int i=;i<cnt1;--i){

        for(int j=;j<cnt2;j++){

            ans[i+j]+=b[i]*c[j];

        }

    }

    for(int i=;i<cntq;++i){

        ans[i+]+=ans[i]/;

        ans[i]%=;

    }

    while(!ans[cntq]&&cntq) --cntq;

    for(int i=cntq;i>=;--i) printf("%d",ans[i]);

    return ;

}

bzoj 1753: [Usaco2005 qua]Who's in the Middle——STL nth_element

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,s[M];

int main(){

    n=read(); k=n/;

    for(int i=;i<n;i++) s[i]=read();

    std::nth_element(s,s+k,s+n);

    printf("%d\n",s[k]);

    return ;

}

bzoj 1710: [Usaco2007 Open]Cheappal 廉价回文——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

const int M=3e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,cnt;

int f[M][],cost[M];

char s[M],ch[];

int main(){

    int x,y;

    n=read(); m=read();

    scanf("%s",s+); cnt=strlen(s+);

    for(int i=;i<=n;i++){

        scanf("%s",ch); x=read(); y=read();

        cost[(int)ch[]]=min(x,y);

    }

    for(int k=;k<m;k++){

        for(int l=;l<=m-k;l++){

            int r=l+k;

            f[l][r]=min(f[l+][r]+cost[(int)s[l]],f[l][r-]+cost[(int)s[r]]);

            if(s[l]==s[r]) f[l][r]=min(f[l][r],f[l+][r-]);

        }

    }printf("%d\n",f[][m]);

    return ;

}

bzoj 1598: [Usaco2008 Mar]牛跑步——第K短路

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=2e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,h[M],d[M][];

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void merge(int s1[M],int s2[M],int w){

    memset(h,,sizeof(h));

    int cnt=,l=,r=;

    while(cnt<k){

        if(s1[l]<s2[r]+w) h[++cnt]=s1[l++];

        else h[++cnt]=s2[r]+w,r++;

    }

    for(int i=;i<=k;i++) s1[i]=h[i];

}

int main(){

    int x,y,w;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),ins(y,x,w);

    memset(d,0x3f,sizeof(d));

    d[n][]=;

    for(int x=n-;x;x--){

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            merge(d[x],d[now],e[i].w);

        }

    }

    for(int i=;i<=k;i++)

        if(d[][i]==inf) printf("-1\n");

        else printf("%d\n",d[][i]);

    return ;

}

bzoj 2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛——树形dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::max;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,f[M][];

int first[M],cnt;

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void dfs(int x,int fa){

    f[x][]=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        dfs(now,x);

        f[x][]=f[x][]+max(f[now][],f[now][]);

        f[x][]=f[x][]+f[now][];

    }

}

int main(){

    int x,y;

    n=read();

    for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    dfs(,-);

    printf("%d\n",max(f[][],f[][]));

    return ;

}

bzoj 1741: [Usaco2005 nov]Asteroids 穿越小行星群——网络流

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using std::min;

const int M=2e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,cur[M],d[M];

int S,T,ans;

int first[M],cnt=;

struct node{int to,next,flow;}e[*M];

void ins(int a,int b,int flow){e[++cnt]=(node){b,first[a],flow}; first[a]=cnt;}

void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}

std::queue<int>q;

int bfs(){

    memset(d,-,sizeof(d));

    d[S]=; q.push(S);

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(e[i].flow&&d[now]==-) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]==d[x]+&&(f=dfs(now,min(e[i].flow,a)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

int main(){

    int x,y;

    n=read(); k=read();

    S=; T=*n+;

    for(int i=;i<=n;i++) insert(S,i,);

    for(int i=;i<=n;i++) insert(i+n,T,);

    for(int i=;i<=k;i++) x=read(),y=read(),insert(x,y+n,);

    while(bfs()){for(int i=S;i<=T;i++) cur[i]=first[i]; ans+=dfs(S,inf);}

    printf("%d\n",ans);

    return ;

}

bzoj 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名——floyd传递闭包

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<bitset>

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,x,y,ans;

std::bitset<> f[];

int main(){

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),f[x][y]=;

    for(int k=;k<=n;k++)

     for(int i=;i<=n;i++)

         if(f[i][k]) f[i]|=f[k];

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)if(!f[i][j]&&!f[j][i]) ans++;

    printf("%d\n",ans);

    return ;

}

bzoj 1578: [Usaco2009 Feb]Stock Market 股票市场——dp（完全背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::max;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,mx;

int f[],map[][];

int main(){

    n=read(); m=read(); k=read();

    for(int i=;i<=n;i++) for(int j=;j<=m;j++) map[j][i]=read();

    mx=k;

    for(int i=;i<=m;i++){

        memset(f,,sizeof(f));

        for(int j=;j<=n;j++)

        {

        //printf("%d %dQWQ\n",map[i-1][j],mx);

        for(int k=map[i-][j];k<=mx;k++)

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

        }

        mx+=f[mx];

        //printf("QAQ%d\n",mx);

    }

    printf("%d\n",mx);

    return ;

}

bzoj 1703: [Usaco2007 Mar]Ranking the Cows 奶牛排名——floyd传递闭包

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<bitset>

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,x,y,ans;

std::bitset<> f[];

int main(){

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),f[x][y]=;

    for(int k=;k<=n;k++)

     for(int i=;i<=n;i++)

         if(f[i][k]) f[i]|=f[k];

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++)if(!f[i][j]&&!f[j][i]) ans++;

    printf("%d\n",ans);

    return ;

}

bzoj 1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害——最小割

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int first[M],cur[M],cnt=,ans;

int n,m,h,S,T,mark[M];

struct node{int to,next,flow;}e[*M];

void ins(int a,int b,int flow){e[++cnt]=(node){b,first[a],flow}; first[a]=cnt;}

void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}

std::queue<int>q;

int d[M];

int bfs(){

    memset(d,-,sizeof(d));

    d[S]=; q.push(S);

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(d[now]==-&&e[i].flow) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]==d[x]+&&(f=dfs(now,std::min(e[i].flow,a)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

int main(){

    int x,y;

    n=read(); m=read(); h=read();

    S=; T=*n+;

    insert(S,,inf); insert(,+n,inf);

    for(int i=;i<=m;i++){

        x=read(); y=read();

        if(x==y) continue;

        insert(x+n,y,inf); insert(y+n,x,inf);

    }

    for(int i=;i<=h;i++){

        x=read(); mark[x]=;

        insert(x,x+n,inf);

        insert(x+n,T,inf);

    }

    for(int i=;i<=n;i++) if(!mark[i]) insert(i,i+n,);

    while(bfs()){for(int i=S;i<=T;i++) cur[i]=first[i]; ans+=dfs(S,inf);}

    printf("%d\n",ans);

    return ;

}

bzoj 1704: [Usaco2007 Mar]Face The Right Way 自动转身机——O（n）枚举O（n）计算就可以了

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,f[M],s[M],ansm,ansk=;

char ch[];

bool flag;

int main(){

    n=read();

    for(int i=;i<=n;i++){

        scanf("%s",ch);

        if(ch[]=='B') s[i]=,ansm++;

    }

    for(int k=;k<=n;k++){

        flag=false;

        int sum=,now=;

        for(int i=;i<=n-k+;i++){

            if(f[i]==k) now^=;

            if(s[i]^now) sum++,now^=,f[i+k]=k;

        }

        for(int i=n-k+;i<=n;i++){

            if(f[i]==k) now^=;

            if(s[i]^now){flag=true; break;}

        }

        if(flag) continue;

        if(sum<ansm) ansm=sum,ansk=k;

    }

    printf("%d %d\n",ansk,ansm);

    return ;

}

bzoj 2199: [Usaco2011 Jan]奶牛议会——2—SAT

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int qread(){

    int x=read(),c=getchar();

    while(c!='Y'&&c!='N') c=getchar();

    if(c=='Y') return x<<^;

    return x<<;

}

int n,m;

int first[M],cnt,star[M],sum;

struct node{int from,to,next;}e[*M],q[*M];

void ins(int a,int b){e[++cnt]=(node){a,b,first[a]}; first[a]=cnt;}

void qins(int a,int b){q[++sum]=(node){a,b,star[a]}; star[a]=sum;}

int qc,color[M],dfn[M],low[M],stk[M],last[M],top,tot;

void tarjan(int x){

    dfn[x]=low[x]=++tot;

    stk[++top]=x; last[x]=top;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!dfn[now]) tarjan(now),low[x]=min(low[x],low[now]);

        else if(!color[now]) low[x]=min(low[x],dfn[now]);

    }

    if(low[x]==dfn[x]){

        qc++;

        while(top>=last[x]) color[stk[top]]=qc,top--;

    }

}

int h,vis[M];

void dfs(int x){

    vis[x]=h;

    for(int i=star[x];i;i=q[i].next){

        int now=q[i].to;

        if(vis[now]!=h) dfs(now);

    }

}

int pd(int x){

    h++; dfs(x);

    for(int i=;i<=n;i++)if(vis[color[i<<]]==h&&vis[color[i<<^]]==h) return ;

    return ;

}

char ans[M];

int main(){

    int x,y;

    n=read(); m=read();

    for(int i=;i<=m;i++){

        x=qread(); y=qread();

        ins(x^,y); ins(y^,x);

    }

    for(int i=;i<=(n<<^);i++)if(!dfn[i]) tarjan(i);

    for(int i=;i<=cnt;i++)if(color[e[i].from]!=color[e[i].to]) qins(color[e[i].from],color[e[i].to]);

    for(int i=;i<=n;i++){

        if(color[i<<]==color[i<<^]) return puts("IMPOSSIBLE"),;

        int p=pd(color[i<<]),q=pd(color[i<<^]);

        if(!p&&!q) return puts("IMPOSSIBLE"),;

        if(p&&q) ans[i]='?';

        else if(p) ans[i]='N';

        else if(q) ans[i]='Y';

    }

    for(int i=;i<=n;i++) printf("%c",ans[i]);

    return ;

}

bzoj 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列——hash+map

这道题转2进制后求前缀和，前缀和的每位都减去第一位，如果有两个前缀和 i 和 j 相同的话，那么i+1~j这一段的k种颜色出现次数一样多

这道题有单独的题解QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define LL unsigned long long

const int M=2e5+,P=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,ans;

int d[M][];

std::map<LL,int>q;

int find(int x){

    LL sum=;

    for(int i=;i<=k;i++) sum=sum*P+1LL*d[x][i];

    if(!q[sum]&&sum) q[sum]=x;

    return q[sum];

}

int main(){

    n=read(); k=read();

    for(int i=;i<=n;i++){

        int now=,x=read();

        for(;x;x>>=) d[i][++now]=x&;

        for(int j=;j<=k;j++) d[i][j]+=d[i-][j];

    }

    for(int i=;i<=n;i++){

        for(int j=;j<=k;j++) d[i][j]-=d[i][];

        ans=std::max(ans,i-find(i));

    }printf("%d\n",ans);

    return ;

}

bzoj 1718: [Usaco2006 Jan] Redundant Paths 分离的路径——边双连通分量缩点求出叶子数

#include<cstdio>

#include<cstring>

#include<cstring>

#include<algorithm>

using std::min;

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,f[*M];

int dfn[M],low[M],last[M],stk[M],top;

int color[M],hc,T;

int first[M],cnt=,star[M],sum=;

struct node{int from,to,next;}e[*M],q[*M];

void ins(int a,int b){e[++cnt]=(node){a,b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

void insq(int a,int b){q[++sum]=(node){a,b,star[a]}; star[a]=sum;}

void insertq(int a,int b){insq(a,b); insq(b,a);}

void tarjan(int x){

    low[x]=dfn[x]=++T;

    stk[++top]=x; last[x]=top;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(f[i^]) continue; f[i]=;

        if(!dfn[now]) tarjan(now),low[x]=min(low[x],low[now]);

        else if(!color[now]) low[x]=min(low[x],dfn[now]);

    }

    if(low[x]==dfn[x]) for(hc++;top>=last[x];top--) color[stk[top]]=hc;

}

int in[M],vis[M],ans;

int main(){

    int x,y;

    n=read(); m=read();

    for(int i=;i<=m;i++) x=read(),y=read(),insert(x,y);

    for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i);

    for(int i=;i<=cnt;i+=)

    if(color[e[i].from]!=color[e[i].to]) in[color[e[i].from]]++,in[color[e[i].to]]++;

    for(int i=;i<=hc;i++) if(in[i]==) ans++;

    printf("%d\n",(ans+)>>);

    return ;

}

bzoj 1700: [Usaco2007 Jan]Problem Solving 解题——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans=inf,n,m,f[M][M];

int k,s1[M],s2[M];

int main(){

    memset(f,0x3f,sizeof(f));

    n=read(); m=read();

    for(int i=;i<=m;i++){

        k=read(); s1[i]=s1[i-]+k;

        k=read(); s2[i]=s2[i-]+k;

    }

    f[][]=;f[][]=;f[][]=;

    for(int k=;k<=m;k++){

        for(int i=;i<=k;i++)if(s1[k]-s1[k-i]<=n)

        for(int j=;j<=k-i;j++)if((s1[k]-s1[k-i])+(s2[k-i]-s2[k-i-j])<=n)

        f[k][i]=std::min(f[k][i],f[k-i][j]+);

        for(int i=;i<=m;i++)if(s2[k]-s2[k-i]<=n)f[k][]=min(f[k][],f[k][i]+);

    }

    ans=f[m][]+;

    for(int i=;i<=m;i++) if(s2[m]-s2[m-i]<=n) ans=min(ans,f[m][i]+);

    printf("%d\n",ans);

    return ;

}

bzoj 1776: [Usaco2010 Hol]cowpol 奶牛政坛——树的直径QAQ

可以证明一个结论一棵树的直径必然存在一条过深度最深的点

所以我们可以求出每种颜色最深的点然后其他点和他求一波lca算答案就可以了

这样的复杂度是nlogn的

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=3e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int rt,n,k,c[M],mx[M],id[M];

int first[M],cnt;

struct node{int to,next;}e[M];

int f[M][],fa[M],dep[M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void dfs(int x){//printf("[%d]\n",x);

    for(int i=;(<<i)<=dep[x];i++) f[x][i]=f[f[x][i-]][i-];

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        dep[now]=dep[x]+;

        f[now][]=x;

        if(dep[now]>mx[c[now]]) mx[c[now]]=dep[now],id[c[now]]=now;

        dfs(now);

    }

}

int find(int x,int y){

    if(dep[x]<dep[y]) std::swap(x,y);

    int d=dep[x]-dep[y];

    for(int i=;(<<i)<=d;i++) if((<<i)&d) x=f[x][i];

    if(x==y) return x;

    for(int i=;i>=;i--)

     if((<<i)<=dep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

    return f[x][];

}

int ans[M];

int main(){

    int x,y;

    n=read(); k=read();

    for(int i=;i<=n;i++){

        c[i]=read(); fa[i]=read();

        if(fa[i]) ins(fa[i],i);

        else rt=i;

    }

    dep[rt]=; dfs(rt);

    for(int i=;i<=n;i++){

        int lca=find(i,id[c[i]]);

        ans[c[i]]=std::max(ans[c[i]],dep[i]+dep[id[c[i]]]-*dep[lca]);

    }

    for(int i=;i<=k;i++) printf("%d\n",ans[i]);

    return ;

}

bzoj 1778: [Usaco2010 Hol]Dotp 驱逐猪猡——高斯消元+概率dp（待填QAQ

bzoj 3126: [Usaco2013 Open]Photo——单调队列优化dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

using std::max;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,x,y;

int l[M],r[M],f[M];

int q[M],ql=,qr;

int main(){

    n=read(); m=read();

    for(int i=;i<=n+;i++) r[i]=i-;

    for(int i=;i<=m;i++){

        x=read(); y=read();

        r[y]=min(r[y],x-);

        l[y+]=max(l[y+],x);

    }

    for(int i=n;i;i--) r[i]=min(r[i],r[i+]);

    for(int i=;i<=n+;i++) l[i]=max(l[i],l[i-]);

    f[qr=]=;

    for(int i=;i<=n+;i++){

        for(int k=r[i-]+;k<=r[i];k++){

            while(ql<=qr&&f[q[qr]]<=f[k]) qr--;

            q[++qr]=k;

        }

        while(ql<=qr&&q[ql]<l[i]) ql++;

        if(ql>qr) f[i]=-inf;

        else f[i]=f[q[ql]]+;

    }

    if(f[n+]>=) printf("%d\n",f[n+]-);

    else printf("-1\n");

    return ;

}

当然这道题也有差分约束的写法QAQ——其实是硬水过去的QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using std::queue;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

bool f=false;

int ans,n,m;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

int dis[M],vis[M];

struct pos{int dis,id;};

bool operator <(pos a,pos b){return a.dis>b.dis;};

std::priority_queue<pos>q;

void spfa(){

    memset(dis,0x3f,sizeof(dis));

    q.push((pos){,});

    dis[]=; vis[]=;

    while(!q.empty()){

        pos x=q.top(); q.pop();

        for(int i=first[x.id];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x.id]+e[i].w){

                ans++; if(ans>) return void(f=true);

                dis[now]=dis[x.id]+e[i].w;

                if(!vis[now]) vis[now]=,q.push((pos){dis[now],now});

            }

        }

        vis[x.id]=;

    }

}

int main(){

    int l,r;

    n=read(); m=read();

    for(int i=;i<=m;i++) l=read(),r=read(),ins(l-,r,),ins(r,l-,-);

    for(int i=;i<=n;i++) ins(i-,i,),ins(i,i-,);

    spfa();

    if(f) printf("-1\n");

    else printf("%d\n",dis[n]);

    return ;

}

bzoj 1731: [Usaco2005 dec]Layout 排队布局——差分约束

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define LL long long

const int M=1e3+,N=1e5+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,ml,md,h[M],vis[M];

int x,y,w,dis[M];

int first[M],cnt;

struct node{int to,next,w;}e[N];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

std::queue<int>q;

bool f=false;

void spfa(){

    memset(dis,0x3f,sizeof(dis));

    q.push(); dis[]=;

    vis[]=; h[]=;

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x]+e[i].w){

                dis[now]=dis[x]+e[i].w;

                if(!vis[now]){

                    vis[now]=; q.push(now);

                    h[now]++; if(h[now]==n){f=true; return ;}

                }

            }

        }

        vis[x]=;

    }

}

int main(){

    n=read(); ml=read(); md=read();

    for(int i=;i<=ml;i++) x=read(),y=read(),w=read(),ins(x,y,w);

    for(int i=;i<=md;i++) x=read(),y=read(),w=read(),ins(y,x,-w);

    for(int i=;i<n;i++) ins(i+,i,);

    spfa();

    if(f) printf("-1\n");

    else if(dis[n]==inf) printf("-2\n");

    else printf("%d\n",dis[n]);

    return ;

}

bzoj 1705: [Usaco2007 Nov]Telephone Wire 架设电话线——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

using std::max;

const int M=1e5+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,c,ans,mn;

int h[M],f[M][];

int main(){

    n=read(); c=read();

    for(int i=;i<=n;i++) h[i]=read();

    memset(f,0x3f,sizeof(f));

    for(int i=h[];i<=;i++) f[][i]=(h[]-i)*(h[]-i);

    for(int k=;k<=n;k++){

        mn=inf;

        for(int i=h[k-];i<max(h[k-],h[k]);i++) mn=min(mn,f[k-][i]-c*i);

        for(int i=h[k];i<=;i++){

            mn=min(mn,f[k-][i]-c*i);

            f[k][i]=mn+c*i+(h[k]-i)*(h[k]-i);

        }

        mn=inf;

        for(int i=;i>=h[k];i--){

            if(i>=h[k-]) mn=min(mn,f[k-][i]+c*i);

            f[k][i]=min(f[k][i],mn-c*i+(h[k]-i)*(h[k]-i));

        }

    }

    ans=inf;

    for(int i=;i<=;i++) ans=min(ans,f[n][i]);

    printf("%d\n",ans);

    return ;

}

bzoj 1755: [Usaco2005 qua]Bank Interest-.....

#include<cstdio>

#include<cstring>

#include<algorithm>

double R,M;

int y;

int main(){

    scanf("%lf %lf %d",&R,&M,&y);

    for(int i=;i<=y;i++) M=M*(+R/);

    printf("%d\n",(int)M);

    return ;

}

bzoj 2200: [Usaco2011 Jan]道路和航线

1——spfa+SLF优化QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=3e4+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

bool f=false;

int n,nr,np,S;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int dis[M],vis[M];

int q[M],head,tail=;

void spfa(){

    memset(dis,0x3f,sizeof(dis));

    dis[S]=; vis[S]=;

    q[head]=S;

    while(head!=tail){

        int x=q[head++]; if(head>M) head=;

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(dis[now]>dis[x]+e[i].w){

                dis[now]=dis[x]+e[i].w;

                if(!vis[now]){

                    vis[now]=;

                    if(dis[now]<=dis[q[head]]){

                        head--;

                        if(head<) head=M;

                        q[head]=now;

                    }

                    else{q[tail++]=now; if(tail>M) tail=;}

                }

            }

        }

        vis[x]=;

    }

    for(int i=;i<=n;i++)

        if(dis[i]>=inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

}

int main(){

    int x,y,w;

    n=read(); nr=read(); np=read(); S=read();

    for(int i=;i<=nr;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    for(int i=;i<=np;i++) x=read(),y=read(),w=read(),ins(x,y,w);

    spfa();

    return ;

}

2——dfs染色+拓扑+dijkstra

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=3e4+,inf=0x3f3f3f3f;

char buf[*M],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

bool flag=false;

int n,nr,np,S;

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

int color[M],hc;

void dfs(int x){

    color[x]=hc;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!color[now]) dfs(now);

    }

}

int sum,star[M];

struct pos{int from,to,next,w;}q[*M];

void insq(int a,int b,int w){q[++sum]=(pos){a,b,star[a],w}; star[a]=sum;}

int f[M],vis[M];

void find(int x){

    vis[x]=f[color[x]]=n+;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(!vis[now]) find(now);

    }

}

int k,dis[M],wh[M],mark[*M];

struct QAQ{

    int d,id;

    bool operator <(const QAQ& x)const{return x.d<d;}

};

std::priority_queue<QAQ>qu[M];

std::queue<int>Q;

int in[M];

void find_w(int x){

    vis[x]=k;

    for(int i=star[x];i;i=q[i].next){

        int now=color[q[i].to];

        dis[q[i].to]=std::min(dis[q[i].to],dis[x]+q[i].w);

        qu[now].push((QAQ){dis[q[i].to],q[i].to});

        if(!--in[now]) Q.push(now);

    }

    for(int i=first[x];i;i=e[i].next)if(!mark[i]){

        int now=e[i].to;

        if(vis[now]!=k) find_w(now);

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    int x,y,w;

    n=read(); nr=read(); np=read(); S=read();

    for(int i=;i<=nr;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    for(int i=;i<=n;i++)if(!color[i]) hc++,wh[hc]=i,dfs(i);

    for(int i=;i<=np;i++) x=read(),y=read(),w=read(),ins(x,y,w),mark[cnt]=,insq(x,y,w);

    memset(dis,0x3f,sizeof(dis)); dis[S]=;

    for(int i=;i<=sum;i++) if(f[color[q[i].from]]&&f[color[q[i].to]]) in[color[q[i].to]]++;

    Q.push(color[S]); qu[color[S]].push((QAQ){,S});

    while(!Q.empty()){

        int x=Q.front(); Q.pop(); k++;

        while(!qu[x].empty()){

            QAQ p=qu[x].top(); qu[x].pop();

            if(dis[p.id]<p.d) continue;

            for(int i=first[p.id];i;i=e[i].next)if(!mark[i]){

                int now=e[i].to;

                if(dis[now]>dis[p.id]+e[i].w) dis[now]=dis[p.id]+e[i].w,qu[x].push((QAQ){dis[now],now});

            }

        }

        find_w(wh[x]);

    }

    for(int i=;i<=n;i++)

        if(dis[i]>=inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

    return ;

}

bzoj 1774: [Usaco2009 Dec]Toll 过路费——（改）floyd

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

using std::max;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,map[M][M],h[M],ans[M][M];

struct node{int id,h;}q[M];

bool cmp(node a,node b){return a.h<b.h;}

void floyd(){

    memset(ans,0x3f,sizeof(ans));

    std::sort(q+,q++n,cmp);

    for(int k=;k<=n;k++)

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++){

          map[i][j]=min(map[i][j],map[i][q[k].id]+map[q[k].id][j]);

          ans[i][j]=min(ans[i][j],map[i][j]+max(max(h[i],h[j]),q[k].h));

    }

}

int main(){

    int x,y,w;

    n=read(); m=read(); k=read();

    memset(map,0x3f,sizeof(map));

    for(int i=;i<=n;i++) h[i]=q[i].h=read(),q[i].id=i;

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),map[x][y]=map[y][x]=min(map[x][y],w);

    floyd();

    for(int i=;i<=k;i++) x=read(),y=read(),printf("%d\n",ans[x][y]);

    return ;

}

bzoj 1575: [Usaco2009 Jan]气象牛Baric——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using std::min;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,f[M][M];

int v[M],star[M],mid[M][M],last[M];

int main(){

    n=read(); k=read();

    for(int i=;i<=n;i++) v[i]=read();

    for(int i=;i<=n;i++){

        for(int j=;j<i;j++) star[i]+=*abs(v[i]-v[j]);

        for(int j=i+;j<=n;j++) last[i]+=*abs(v[i]-v[j]);

        for(int j=i+;j<=n;j++) for(int k=i+;k<j;k++) mid[i][j]+=abs(*v[k]-v[i]-v[j]);

    }

    memset(f,0x3f,sizeof(f));

    for(int i=;i<=n;i++){

        f[i][]=star[i];

        for(int j=;j<=i;j++)

        for(int k=j-;k<i;k++) f[i][j]=min(f[i][j],f[k][j-]+mid[k][i]);

    }

    int ansh=inf,ans=inf;

    for(int i=;i<=n;i++)

        for(int j=;j<=i;j++)

        if(f[i][j]+last[i]<=k){

            if(ansh>j) ansh=j,ans=f[i][j]+last[i];

            else if(j==ansh) ans=min(ans,f[i][j]+last[i]);

        }

    printf("%d %d\n",ansh,ans);

    return ;

}

bzoj 1783: [Usaco2010 Jan]Taking Turns——博弈dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,id;

LL f[M],g[M],v[M];

int main(){

    n=read(); id=n+;

    for(int i=;i<=n;i++) v[i]=read();

    for(int i=n;i>=;i--){

        f[i]=g[id]+v[i];

        g[i]=f[id];

        if(f[i]>=f[id]) id=i;

    }

    printf("%lld %lld\n",f[id],g[id]);

    return ;

}

bzoj 1577: [Usaco2009 Feb]庙会捷运Fair Shuttle——大根堆+小根堆+贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

const int M=3e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int f[*M],cnt,cost,k,n,c,ans;

struct pos{

    int id,h,ed;

    bool operator <(const pos &x)const{return x.ed<ed;}

};

std::vector<pos>e[M];

std::priority_queue<pos>q1;

struct Q{

    int id,h,ed;

    bool operator <(const Q &x)const{return x.ed>ed;}

};

std::priority_queue<Q>q2;

int main(){

    int v,x,y;

    k=read(); n=read(); c=read();

    for(int i=;i<=k;i++) x=read(),y=read(),v=read(),e[x].push_back((pos){++cnt,v,y});

    for(int i=;i<=n;i++){

        while(!q1.empty()){

            pos x=q1.top();

            if(x.ed>i) break;

            q1.pop();

            if(f[x.id]) continue;

            f[x.id]=; cost-=x.h; ans+=x.h;

        }

        int mx=e[i].size();

        for(int j=;j<mx;j++){

            q1.push((pos){e[i][j].id,e[i][j].h,e[i][j].ed});

            q2.push((Q){e[i][j].id,e[i][j].h,e[i][j].ed});

            cost+=e[i][j].h;

        }

        while(cost>c){

            Q x=q2.top(); q2.pop();

            if(f[x.id]) continue;

            f[x.id]=;

            if(cost-c>=x.h){cost-=x.h; continue;}

            int now=cost-c;

            cnt++;

            q1.push((pos){cnt,x.h-now,x.ed});

            q2.push((Q){cnt,x.h-now,x.ed});

            cost=c;

        }

    }

    printf("%d\n",ans);

    return ;

}

bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形——极角排序

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using std::sort;

const int M=2e5+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n;

struct pos{int x,y,wh; double k;}q[M];

bool cmp(pos a,pos b){return a.wh!=b.wh?a.wh<b.wh:a.k>b.k;}

int main(){

    int x,y;

    n=read();

    for(int i=;i<=n;i++){

        x=read(); y=read();

        q[i].x=x; q[i].y=y;

        if(x) q[i].k=1.0*y/x; else q[i].k=-inf;

        if(x>&&y>=) q[i].wh=;

        else if(x>=&&y<) q[i].wh=;

        else if(x<&&y<=) q[i].wh=;

        else q[i].wh=;

    }

    LL ans=1LL*n*(n-)*(n-)/;

    sort(q+,q++n,cmp);

    LL sum=,ly=;

    for(int i=;i<=n;i++){

        sum--;

        while(1LL*q[ly].y*q[i].x<1LL*q[i].y*q[ly].x){

            ly++; sum++;

            if(ly>n) ly-=n;

        }

        ans=ans-sum*(sum-)/;

    }

    printf("%lld\n",ans);

    return ;

}

bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍——中位数排序

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

using std::sort;

using std::min;

const int M=2e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,sum,n,x[M],y[M];

struct pos{

    int x,y;

    bool operator <(const pos& h)const{return h.x!=x?h.x<x:h.y<y;}

}q[M];

std::map<pos,bool>vis;

int main(){

    n=read();

    for(int i=;i<=n;i++){

        x[i]=read(); y[i]=read();

        q[i].x=x[i]; q[i].y=y[i];

    }

    sort(x+,x++n); sort(y+,y++n);

    int x1=x[(n+)/],y1=y[(n+)/],x2=x[(n+)/],y2=y[(n+)/];

    if(x1==x2&&y1==y2){

        bool f=false;

        for(int i=;i<=n;i++)if(q[i].x==x1&&q[i].y==y1){f=true; break;}

        if(!f){

            ans=;

            for(int i=;i<=n;i++){

                sum=sum+abs(q[i].x-x1);

                sum=sum+abs(q[i].y-y1);

            }

        }

        else{

            int nx=x1,ny=y1-;

            for(int i=;i<=n;i++){

                sum=sum+abs(q[i].x-nx);

                sum=sum+abs(q[i].y-ny);

            }

            ans=; nx=x1; ny=y1+;

            int now=;

            for(int i=;i<=n;i++){

                now=now+abs(q[i].x-nx);

                now=now+abs(q[i].y-ny);

            }

            if(sum>now) ans=;

            if(sum==now) ans++;

            nx=x1+; ny=y1;

            now=;

            for(int i=;i<=n;i++){

                now=now+abs(q[i].x-nx);

                now=now+abs(q[i].y-ny);

            }

            if(sum>now) ans=;

            if(sum==now) ans++;

            now=;

            nx=x1-; ny=y1;

            for(int i=;i<=n;i++){

                now=now+abs(q[i].x-nx);

                now=now+abs(q[i].y-ny);

            }

            if(sum>now) ans=;

            if(sum==now) ans++;

        }

        printf("%d %d\n",sum,ans);

    }

    else{

        ans=(x2-x1+)*(y1-y2+);

        for(int i=;i<=n;i++){

            if(q[i].x>=x1&&q[i].x<=x2&&q[i].y>=y2&&q[i].y<=y1){

                if(!vis[(pos){q[i].x,q[i].y}]){ans--; vis[(pos){q[i].x,q[i].y}]=;}

            }

            sum=sum+abs(q[i].x-x1);

            sum=sum+abs(q[i].y-y1);

        }

        printf("%d %d\n",sum,ans);

    }

    return ;

}

bzoj 1590: [Usaco2008 Dec]Secret Message 秘密信息

1. 排序版本如果A是B的前缀那么字典序 A<=B<=Ainf 正反做一次就可以了就是有点慢=_=

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using std::sort;

using std::lower_bound;

using std::upper_bound;

const int M=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k;

int ans[M],f[M];

struct pos{

    int id; std::vector<int>s;

    bool operator <(const pos& x)const{return s<x.s;}

}s1[M],s2[M];

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++){

        k=read();

        for(int j=;j<=k;j++) s1[i].s.push_back(read()),s1[i].id=i;

    }

    for(int i=;i<=m;i++){

        k=read();

        for(int j=;j<=k;j++)  s2[i].s.push_back(read()),s2[i].id=i;

    }

    sort(s1+,s1++n); sort(s2+,s2++m);

    for(int i=;i<=n;i++){

        int lx=lower_bound(s2+,s2++m,s1[i])-s2;

        s1[i].s.push_back(inf);

        int rx=upper_bound(s2+,s2++m,s1[i])-s2;

        s1[i].s.pop_back();

        f[lx]++; f[rx]--;

    }

    for(int i=;i<=m;i++){

        int lx=upper_bound(s1+,s1++n,s2[i])-s1;

        s2[i].s.push_back(inf);

        int rx=upper_bound(s1+,s1++n,s2[i])-s1;

        s2[i].s.pop_back();

        ans[s2[i].id]=rx-lx;

    }

    int now=;

    for(int i=;i<=m;i++){now+=f[i]; ans[s2[i].id]+=now;}

    for(int i=;i<=m;i++) printf("%d\n",ans[i]);

    return ;

}

2. trie版本记一下每个位置作为多少个串的前缀以及每个串的终止位置统计一波就可以了很快QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=1e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,son[M],sum[M],ans[M];

int s[M],c[M][],cnt;

void insert(int len){

    int rt=;

    for(int i=;i<=len;i++){

        if(!c[rt][s[i]]) c[rt][s[i]]=++cnt;

        rt=c[rt][s[i]];

        son[rt]++;

    }

    sum[rt]++;

}

int find(int len){

    int rt=,ans=;

    for(int i=;i<=len;i++){

        if(!c[rt][s[i]]) break;

        rt=c[rt][s[i]];

        if(i==len) ans+=son[rt];

        else ans+=sum[rt];

    }

    return ans;

}

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++){

        k=read();

        for(int j=;j<=k;j++) s[j]=read();

        insert(k);

    }

    for(int i=;i<=m;i++){

        k=read();

        for(int j=;j<=k;j++) s[j]=read();

        printf("%d\n",find(k));

    }

    return ;

}

bzoj 3940: [Usaco2015 Feb]Censoring——another坑QAQ

bzoj 2097: [Usaco2010 Dec]Exercise 奶牛健美操——二分+树形dp+贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::sort;

const int M=2e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,sz[M];

int first[M],cnt,s[M];

struct node{int to,next;}e[*M];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

bool cmp(int x,int y){return x>y;}

int ans,mx;

void dfs(int x,int fa){

    sz[x]=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        dfs(now,x);

    }

    cnt=;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        s[++cnt]=sz[now]+;

    }

    sort(s+,s++cnt,cmp);

    int k=;

    s[cnt+]=s[cnt+]=s[cnt+]=;

    while(s[k]+s[k+]>mx) ans++,k++;

    sz[x]=s[k];

}

bool check(int ly){

    mx=ly; ans=;

    dfs(,-);

    return ans<=k;

}

int main(){

    int x,y;

    n=read(); k=read();

    for(int i=;i<n;i++) x=read(),y=read(),insert(x,y);

    int l=,r=n;

    while(l<r){

        int mid=(l+r)>>;

        if(check(mid)) r=mid;

        else l=mid+;

    }printf("%d\n",l);

    return ;

}

bzoj 1693: [Usaco2007 Demo]Asteroids——二分图匹配

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using std::min;

const int M=2e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,k,cur[M],d[M];

int S,T,ans;

int first[M],cnt=;

struct node{int to,next,flow;}e[*M];

void ins(int a,int b,int flow){e[++cnt]=(node){b,first[a],flow}; first[a]=cnt;}

void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}

std::queue<int>q;

int bfs(){

    memset(d,-,sizeof(d));

    d[S]=; q.push(S);

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(e[i].flow&&d[now]==-) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]==d[x]+&&(f=dfs(now,min(e[i].flow,a)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

int main(){

    int x,y;

    n=read(); k=read();

    S=; T=*n+;

    for(int i=;i<=n;i++) insert(S,i,);

    for(int i=;i<=n;i++) insert(i+n,T,);

    for(int i=;i<=k;i++) x=read(),y=read(),insert(x,y+n,);

    while(bfs()){for(int i=S;i<=T;i++) cur[i]=first[i]; ans+=dfs(S,inf);}

    printf("%d\n",ans);

    return ;

}

bzoj 1663: [Usaco2006 Open]赶集——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::sort;

using std::max;

const int M=1e3+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,n,ly[M][M],f[M];

struct pos{int h,id;}q[M];

bool cmp(pos a,pos b){return a.h<b.h;}

int main(){

    n=read();

    for(int i=;i<=n;i++) q[i].h=read(),q[i].id=i;

    sort(q+,q++n,cmp);

    for(int i=;i<=n;i++) for(int j=;j<=n;j++) ly[i][j]=read();

    for(int i=;i<=n;i++){

        if(ly[][q[i].id]<=q[i].h) f[i]=;

        else f[i]=-inf;

        for(int j=;j<i;j++)

        if(q[j].h+ly[q[j].id][q[i].id]<=q[i].h) f[i]=max(f[i],f[j]+);

    }

    for(int i=;i<=n;i++) ans=max(ans,f[i]); printf("%d\n",ans);

    return ;

}

bzoj 1742: [Usaco2005 nov]Grazing on the Run 边跑边吃草——一类dp问题QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::min;

using std::sort;

const int M=1e3+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,star;

int f1[M][M],f2[M][M],s[M];

int main(){

    n=read(); star=read();

    for(int i=;i<=n;i++) s[i]=read();

    sort(s+,s++n);

    for(int i=;i<=n;i++) f1[i][i]=f2[i][i]=n*abs(star-s[i]);

    for(int len=;len<=n;len++){

        for(int i=;i<=n-len+;i++){

            int j=i+len-,now=n-j+i;

            f1[i][j]=min(f1[i+][j]+(s[i+]-s[i])*now,f2[i+][j]+(s[j]-s[i])*now);

            f2[i][j]=min(f1[i][j-]+(s[j]-s[i])*now,f2[i][j-]+(s[j]-s[j-])*now);

        }

    }printf("%d\n",min(f1[][n],f2[][n]));

    return ;

}

bzoj 1594: [Usaco2008 Jan]猜数游戏——二分+线段树

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::sort;

using std::max;

using std::min;

const int M=1e5+,N=3e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int cnt,n,m,lx[M],rx[M],mn[N],sign[N],ll[M],rr[M];

struct pos{int l,r,v;}q[M],s[M];

bool cmp(pos a,pos b){return a.v>b.v;}

void clear(){

    cnt=;

    memset(mn,,sizeof(mn));

    memset(sign,,sizeof(sign));

}

int L,R;

void up(int x){mn[x]=min(mn[x<<],mn[x<<^]);}

void down(int x){

    if(!sign[x]) return ;

    int ls=x<<,rs=x<<^;

    sign[x]=; sign[ls]=sign[rs]=;

    mn[ls]=mn[rs]=;

}

void modify(int x,int l,int r){

    if(L<=l&&r<=R){

        mn[x]=; sign[x]=;

        return ;

    }

    down(x);

    int mid=(l+r)>>;

    if(L<=mid) modify(x<<,l,mid);

    if(R>mid) modify(x<<^,mid+,r);

    up(x);

}

int push_mn(int x,int l,int r){

    if(L<=l&&r<=R) return mn[x];

    down(x);

    int mid=(l+r)>>,ans=;

    if(L<=mid) ans=min(ans,push_mn(x<<,l,mid));

    if(R>mid) ans=min(ans,push_mn(x<<^,mid+,r));

    return ans;

}

bool check(int k){

    if(!k) return ;

    clear();

    for(int i=;i<=k;i++) s[i]=q[i];

    sort(s+,s++k,cmp);

    int color=s[].v;

    lx[]=s[].l; rx[]=s[].r;

    ll[]=lx[cnt],rr[]=rx[cnt];

    for(int i=;i<=k;i++){

        if(s[i].v!=color){

            cnt++; color=s[i].v;

            lx[cnt]=s[i].l; rx[cnt]=s[i].r;

            ll[cnt]=lx[cnt]; rr[cnt]=rx[cnt];

        }

        else lx[cnt]=min(lx[cnt],s[i].l),rx[cnt]=max(rx[cnt],s[i].r),ll[cnt]=max(ll[cnt],s[i].l),rr[cnt]=min(rr[cnt],s[i].r);

        if(ll[cnt]>rr[cnt]) return ;

    }

    for(int i=;i<=cnt;i++){

        L=ll[i]; R=rr[i];

        if(push_mn(,,n)!=) return ;

        L=lx[i]; R=rx[i];

        modify(,,n);

    }

    return ;

}

int main(){

    n=read(); m=read();

    for(int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].v=read();

    int l=,r=m+;

    while(l<r){

        int mid=(l+r)>>;

        if(check(mid)) r=mid;

        else l=mid+;

    }

    if(r>m) printf("0\n");

    else printf("%d\n",r);

    return ;

}

bzoj 1583: [Usaco2009 Mar]Moon Mooing 哞哞叫

因为两个函数都是单增的所以维护队列就可以了

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=4e6+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL num[][],c,n;

LL ans[M],cnt,l=,r=;

int main(){

    c=read(); n=read();

    for(int i=;i<=;i++) for(int j=;j<=;j++) num[i][j]=read();

    ans[++cnt]=c;

    LL n1=c*num[][]/num[][]+num[][];

    LL n2=c*num[][]/num[][]+num[][];

    while(cnt<n){

        if(n1<n2){

            if(n1!=ans[cnt]) ans[++cnt]=n1;

            n1=ans[++l]*num[][]/num[][]+num[][];

        }

        else{

            if(n2!=ans[cnt]) ans[++cnt]=n2;

            n2=ans[++r]*num[][]/num[][]+num[][];

        }

    }printf("%lld\n",ans[cnt]);

    return ;

}

bzoj 1716: [Usaco2006 Dec]The Fewest Coins 找零钱——多重背包+完全背包

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::max;

using std::min;

const int M=,N=,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,n,T,m,q[N],id[N],ql,qr,mx;

int v[M],c[M],f[N],ly[N];

int main(){

    //freopen("qwq.out","w",stdout);

    n=read(); T=read();

    for(int i=;i<=n;i++) v[i]=read(),mx=max(mx,v[i]);

    for(int i=;i<=n;i++) c[i]=read();

    m=mx*mx+T; for(int i=;i<=m;i++) f[i]=ly[i]=inf;

    for(int i=;i<=n;i++){

        for(int j=;j<v[i];j++){

            ql=; qr=;

            for(int k=,now;(now=k*v[i]+j)<m;k++){

                int h=f[now]-k;

                while(ql<=qr&&q[qr]>=h) qr--;

                while(ql<=qr&&id[ql]<k-c[i]) ql++;

                q[++qr]=h; id[qr]=k;

                f[now]=min(inf,q[ql]+k);

            }

        }

    }

    for(int i=;i<=n;i++) for(int j=v[i];j<=m;j++) ly[j]=min(ly[j],ly[j-v[i]]+);

    ans=inf;

    for(int i=T;i<=m;i++) ans=min(ans,f[i]+ly[i-T]);

    printf("%d\n",ans==inf?-:ans);

    return ;

}

bzoj 1775: [Usaco2009 Dec]Vidgame 电视游戏问题——dp

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::max;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,p[],k,c[],w[];

int f[][];

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++){

        p[i]=read(); k=read();

        for(int j=;j<=k;j++){

            c[j]=read(); w[j]=read();

            for(int s=m;s>=c[j];s--) f[i][s]=max(f[i][s],max(f[i-][s-c[j]]+w[j],f[i][s-c[j]]+w[j]));

        }

        for(int j=m;j>=p[i];j--) f[i][j]=max(f[i-][j],f[i][j-p[i]]);

        for(int j=;j<=p[i]-;j++) f[i][j]=f[i-][j];

    }

    int ans=; for(int i=;i<=n;i++) ans=max(ans,f[i][m]); printf("%d\n",ans);

    return ;

}

bzoj 1712: [Usaco2007 China]Summing Sums 加密——矩阵乘法

这道题我们可以发现和（sum）每次都会乘(n-1) 所以单独考虑每一位就可以了这样复杂度就可以接受了

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=5e4+,mod=;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL sum,n,m,v[M];

LL ans[][],b[][],c[][];

void pmod(LL a[][],LL b[][]){

    memset(c,,sizeof(c));

    for(int i=;i<=;i++) for(int k=;k<=;k++)

    for(int j=;j<=;j++) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod+mod)%mod;

    for(int i=;i<=;i++) for(int j=;j<=;j++) a[i][j]=c[i][j];

}

int main(){

    n=read(); m=read();

    for(int i=;i<=n;i++) v[i]=read(),sum=(sum+v[i])%mod;

    ans[][]=ans[][]=;

    b[][]=-; b[][]=;

    b[][]=;  b[][]=n-;

    while(m){

        if(m&) pmod(ans,b);

        pmod(b,b); m>>=;

    }

    sum=(ans[][]*sum)%mod;

    for(int i=;i<=n;i++) printf("%lld\n",((ans[][]*v[i])%mod+sum+mod)%mod);

    return ;

}

bzoj 1916: [Usaco2010 Open]冲浪——dp

f[i][j]表示到点i失控j次的答案注意按拓扑序来从n到1逆着dp就可以了QAQ 拓扑的时候小心点为此WA了3次QAQ

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using std::max;

using std::min;

using std::queue;

const int M=,N=;

const LL inf=1e18;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,vis[N];

LL f[N][];

int first[N],cnt,in[N];

struct node{int to,next; LL w;}e[*M];

void ins(int a,int b,LL w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,LL w){ins(a,b,w); ins(b,a,w);}

queue<int>q;

void topsort(int x){

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(vis[now]) continue;

        if(!--in[now]) q.push(now),vis[now]=;

    }

}

void solve(){

    int x=q.front(); q.pop();

    if(x==n){for(int i=;i<=k;i++) f[x][i]=-inf; topsort(x); return ;}

    LL mn=inf,mx=-inf;

    for(int j=;j<=k;j++){

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(!vis[now]) continue;

            if(f[now][j]>=) mx=max(mx,f[now][j]+e[i].w);

            if(j&&f[now][j-]>=) mn=min(mn,f[now][j-]+e[i].w);

        }

        f[x][j]=mx<?(mn<?-inf:mn):(mn<?mx:min(mx,mn));

    }

    topsort(x);

}

int main(){

    int x,y,w;

    n=read(); m=read(); k=read();

    for(int i=;i<=m;i++){

        x=read(); y=read(); w=read();

        insert(x,y,w);

        in[x]++;

    }

    for(int i=;i<=n;i++)if(!in[i]) q.push(i),vis[i]=;

    while(!q.empty()) solve();

    printf("%lld\n",f[][k]);

    return ;

}

bzoj 2274: [Usaco2011 Feb]Generic Cow Protests——树状数组优化dp

f[i]表示前i个数的方案数这题本质上就是

USACO 刷题记录bzoj

这里只要满足前缀和小于i的f[j]就可以辣这个离散化一下前缀和然后树状数组维护一下就可以辣

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using std::sort;

using std::unique;

using std::lower_bound;

const int M=2e5+,mod=1e9+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,s[M];

LL b[M],c[M],cnt;

#define lowbit(x) x&-x

void insert(int x,LL w){

    while(x<=cnt){

        s[x]=(s[x]+w)%mod;

        x+=lowbit(x);

    }

}

LL query(int x){

    LL sum=;

    while(x) sum=(sum+s[x])%mod,x-=lowbit(x);

    return sum;

}

int main(){

    n=read();

    for(int i=;i<=n;i++) b[i]=b[i-]+read(),c[++cnt]=b[i];

    cnt++; sort(c+,c++cnt); cnt=unique(c+,c++cnt)-c-;

    for(int i=;i<=n;i++) b[i]=lower_bound(c+,c++cnt,b[i])-c;

    LL ans=lower_bound(c+,c++cnt,)-c;

    insert(ans,);

    for(int i=;i<=n;i++) ans=query(b[i]),insert(b[i],ans);

    printf("%lld\n",ans);

    return ;

}

bzoj 3408: [Usaco2009 Oct]Heat Wave 热浪——最短路

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int M=1e4+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,S,T,d[M];

int first[M],cnt;

struct node{int to,next,w;}e[*M];

void ins(int a,int b,int w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}

void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}

struct pos{

    int id,d;

    bool operator <(const pos& x)const{return x.d<d;}

};

std::priority_queue<pos>q;

void dj(){

    memset(d,0x3f,sizeof(d));

    d[S]=; q.push((pos){S,d[S]});

    while(!q.empty()){

        pos x=q.top(); q.pop();

        if(x.d!=d[x.id]) continue;

        for(int i=first[x.id];i;i=e[i].next){

            int now=e[i].to;

            if(d[now]>d[x.id]+e[i].w)

            d[now]=d[x.id]+e[i].w,q.push((pos){now,d[now]});

        }

    }

}

int main(){

    int x,y,w;

    n=read(); m=read(); S=read(); T=read();

    for(int i=;i<=m;i++) x=read(),y=read(),w=read(),insert(x,y,w);

    dj();printf("%d\n",d[T]);

    return ;

}

bzoj 2274: [Usaco2011 Feb]Generic Cow Protests——树状数组优化dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=2e5+,mod=1e9+;

using std::sort;

using std::lower_bound;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,v[M],x[M],f[M],s[M];

#define lowbit(x) x&-x

void ins(int x,int v){while(x<=n) s[x]=(s[x]+v)%mod,x+=lowbit(x);}

int query(int x){int sum=; while(x) sum=(sum+s[x])%mod,x-=lowbit(x); return sum;}

int main(){

    n=read();

    for(int i=;i<=n;i++){

        v[i]=v[i-]+read(); x[i]=v[i];

        if(v[i]>=) f[i]=;

    }

    sort(x+,x++n);

    for(int i=;i<=n;i++) v[i]=lower_bound(x+,x++n,v[i])-x;

    for(int i=;i<=n;i++){

        f[i]=(f[i]+query(v[i]))%mod;

        ins(v[i],f[i]);

    }printf("%d\n",f[n]);

    return ;

}

bzoj 1740: [Usaco2005 mar]Yogurt factory 奶酪工厂——贪心

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const LL inf=1e15;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,s,k,mn=inf,ans;

int main(){

    n=read(); s=read();

    for(int i=;i<=n;i++){

        k=read();

        if(k-s*i<mn) mn=k-s*i;

        k=read(); ans=ans+(mn+s*i)*k;

    }printf("%lld\n",ans);

    return ;

}

bzoj 1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛——二分答案+网络流

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

using std::min;

using std::max;

const int M=,Max=0x3f3f3f3f;

const LL inf=1e15;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,S,T;

LL tot,s[M][M],c[M],h[M],l,r;

int first[*M],cnt,cur[*M];

struct node{int to,next,flow;}e[M*M*];

void ins(int a,int b,int flow){e[++cnt]=(node){b,first[a],flow}; first[a]=cnt;}

void insert(int a,int b,int flow){ins(a,b,flow); ins(b,a,);}

std::queue<int>q;

LL d[*M];

int bfs(){

    memset(d,-,sizeof(d));

    d[S]=; q.push(S);

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=first[x];i;i=e[i].next){

            int now=e[i].to;

            if(e[i].flow&&d[now]==-) d[now]=d[x]+,q.push(now);

        }

    }

    return d[T]!=-;

}

int dfs(int x,int a){

    if(x==T||!a) return a;

    int f,flow=;

    for(int &i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(d[now]==d[x]+&&(f=dfs(now,min(a,e[i].flow)))>){

            e[i].flow-=f; e[i^].flow+=f;

            flow+=f;

            a-=f; if(!a) break;

        }

    }

    return flow;

}

bool check(LL k){

    S=; T=*n+; cnt=;

    memset(first,,sizeof(first));

    for(int i=;i<=n;i++) insert(S,i,c[i]),insert(i+n,T,h[i]);

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)if(s[i][j]<=k) insert(i,j+n,Max);

    LL sum=;

    while(bfs()){

        for(int i=;i<=T;i++) cur[i]=first[i];

        sum+=dfs(S,Max);

    }

    return sum>=tot;

}

int main(){

    int x,y,w;

    n=read(); m=read();

    for(int i=;i<=n;i++) c[i]=read(),h[i]=read(),tot+=c[i];

    for(int i=;i<=n;i++) for(int j=;j<=n;j++)if(i!=j) s[i][j]=inf;

    for(int i=;i<=m;i++){

        x=read(); y=read(); w=read();

        s[x][y]=s[y][x]=min(s[x][y],1LL*w);

    }

    for(int k=;k<=n;k++) for(int i=;i<=n;i++)

    for(int j=;j<=n;j++) s[i][j]=min(s[i][j],s[i][k]+s[k][j]);

    r=1e15;

    while(l<r){

        LL mid=(l+r)>>;

        if(check(mid)) r=mid;

        else l=mid+;

    }

    if(r==1e15) puts("-1");

    else printf("%lld\n",r);

    return ;

}

秒客网

USACO 刷题记录bzoj

相关文章