BZOJ总览

时间：2023-01-15 23:12:27

1040: [ZJOI2008]骑士 树上加了一条边 断边再树形DP 断边调了好久 要了解题目性质

1045: [HAOI2008] 糖果传递 中位数水题 内含数学方程 变量搞一搞

bzoj1053:有点忘记了，有空补题解。。。。。。感觉得反思了，明明是一道做了两遍的题，为了复习欧拉函数敲了一遍，然而各种思路都忘记了。。。从最小的质数枚举起，大的质数越少越好。。。。。。

1061: [Noi2008]志愿者招募 内含费用流模板

#include<cstdio>
#include<algorithm>
#include<cstring>
#define value pri
#define N 200000
#define inf 200000000
using namespace std;
int S,T,edgenum,ans,n,m,u,v,w,c;
int next[N],head[N],vet[N],pri[N],cost[N],q[N],inq[N],dis[N],a[N];
void add(int u,int v,int w,int c)
{
    edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;pri[edgenum]=w;cost[edgenum]=c;
    edgenum++;vet[edgenum]=u;next[edgenum]=head[v];head[v]=edgenum;pri[edgenum]=;cost[edgenum]=-c;
}
using namespace std;
bool spfa()
{
    ,tail=;q[]=T;
    ;i<=T;i++)dis[i]=inf;
    ;i<=T;i++)inq[i]=;
    dis[T]=;inq[T]=;
    while(tou<=tail)
    {
        ],e=head[u],ee;
        inq[u]=;
        )
        {
            ==)ee=e+;;
            if(dis[u]-cost[e]<dis[v])
             )
             {
                 dis[v]=dis[u]-cost[e];
                 )
                 {
                     tail++;
                     q[tail%]=v;inq[v]=;
                 }
             }
            e=next[e];
        }
        tou++;
    }
    return (dis[S]!=inf);
}
int dfs(int u,int aug)
{
    inq[u]=;
    if(u==T)return aug;
    ,w;
    )
    {
        ==)ee=e+;;
        )
         )
          if(dis[v]==dis[u]-cost[e])
        {
            w=dfs(v,min(aug-used,value[e]));
            ans+=w*cost[e];
            used+=w;value[e]-=w;value[ee]+=w;
            if(used==aug)return aug;
        }
        e=next[e];
    }
    return used;
}
void dinic()
{
    ans=;int tmp;
    while(spfa())
    {
        inq[T]=;
        )
        {
            memset(inq,,sizeof(inq));
              tmp+=dfs(S,inf);
        }
    }
}
int main()
{
    //freopen("1061.in","r",stdin);
    scanf("%d%d",&n,&m);
    ;i<=n;i++)scanf("%d",&a[i]);
    ;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v+,inf,w);
    }
    S=;T=n+;
    ;i<=n+;i++)
    {
        c=a[i]-a[i-];
        )add(S,i,c,););
        )add(i,i-,inf,);
    }
    dinic();
    printf("%d",ans);
}

1061

1303: [CQOI2009]中位数图 想法题 乱搞

1497: [NOI2006]最大获利 内含最大流dinic模板

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000000
#define inf 200000000
using namespace std;
int edgenum,ans,mon,u,v,w,n,m,S,T,tot;
int head[N],vet[N],pri[N],next[N],h[N],q[N],p[N];
void add(int u,int v,int w)
{
    //printf("%d %d %d\n",u,v,w);
    edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;pri[edgenum]=w;
    edgenum++;vet[edgenum]=u;next[edgenum]=head[v];head[v]=edgenum;pri[edgenum]=;
}
int dfs(int u,int aug)
{
    if(u==T)return aug;
    ,w,e=head[u],ee;
    )
    {
        int v=vet[e];
        )
        )
        {
            ==)ee=e+;;
            w=dfs(v,min(aug-used,pri[e]));
            used+=w;pri[e]-=w;pri[ee]+=w;
            if(used==aug)return used;
        }
        e=next[e];
    }
    )h[u]=-;return used;
}
bool bfs()
{
    ;i<=T;i++)h[i]=-;
    ,tail=;q[]=S;h[S]=;
    while(tou<=tail)
    {
        ],e=head[u];
        )
        {
            int v=vet[e];
            ))
            {
                h[v]=h[u]+;tail++;q[tail%]=v;
            }
            e=next[e];
        }
        tou++;
    }
    );
}
void dinic()
{
    ans=;
    while(bfs())
    {
        ans+=dfs(S,inf);
    }
}
int main()
{
    //freopen("1497.in","r",stdin);
    scanf("%d%d",&n,&m);
    S=;T=n+m+;
    ;i<=n;i++)scanf("%d",&p[i]),add(S,i,p[i]);
    tot=n;

    ;i<=n+m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,i,inf);add(v,i,inf);add(i,T,w);
        mon+=w;
    }
    dinic();
    printf("%d",mon-ans);
}

1497

1588: [HNOI2002]营业额统计 写的超弱的一种splay 好几年前的版本吧。。被坑了

1861: [Zjoi2006]Book 书架 抄黄学长的写法 高级splay 还没有深入理解过>_<

2152: 聪聪可可 第一道点分治 不理解 有空再刷别的 

2588: Spoj 10628. Count on a tree 第一次写主席树 权值线段树 struct LCA

4034: [HAOI2015]T2 树链剖分 改了挺久 pushdown出现了错误 下次写线段树要更仔细一点 还要longlong

 4552:内含线段树，push_down，懒人标记等。。。。

相关文章