首页 > 其他 > 详细

[Luogu 3701] 「伪模板」主席树

时间:2018-05-21 20:57:14      阅读:40      评论:0      收藏:0      [点我收藏+]

标签:push   empty   ace   表白   一个人   printf   scan   algo   ems   

[Luogu 3701] 「伪模板」主席树

<题目链接>


这是一道网络流,不是主席树,不是什么数据结构,而是网络流。

题目背景及描述都非常的暴力,以至于 Capella 在做此题的过程中不禁感到生命流逝。

S 向 byx 的树中的每一个人连有向边,手气君的树中的每一个人向 T 连有向边,边权为这个人的寿命。统计同一棵树中的膜法师数量 x。如果一个人是主席,那么边权要加上 x。(续得好啊

然后,如果 byx 树中的一个点 i 能赢手气君树中的点 j,那么连 i->j,边权为 1。

跑最大流,最终答案为 min(m,ans)。

PS:指针邻接表写网络流真有意思,我再也不用写什么 ((i-1)^1)+1 蛇皮操作了!开心!

以及悄悄在代码里表白一下 Procyon。qwqqwqqwq

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using std::min;
using std::queue;
const int MAXN=210,INF=0x3f3f3f3f;
int n,m,S,T,win[5][5]={ {0  ,1  ,1  ,-1 ,-1 },
                        {-1 ,0  ,1  ,1  ,-1 },
                        {-1 ,-1 ,0  ,1  ,1  },
                        {1  ,-1 ,-1 ,0  ,1  },
                        {1  ,1  ,-1 ,-1 ,0  }};
struct Edge
{
    int to,w;
    Edge *nxt,*back;
    Edge(int to=0,int w=0,Edge* nxt=nullptr):to(to),w(w),nxt(nxt),back(nullptr){}
    ~Edge(void)
    {
        if(nxt!=nullptr)
            delete nxt;
    }
}*head[MAXN];
void AddEdges(int u,int v,int w)
{
    head[u]=new Edge(v,w,head[u]);
    head[v]=new Edge(u,0,head[v]);
    head[u]->back=head[v];
    head[v]->back=head[u];
}
int Number(char *s)
{
    if(s[0]==‘J‘)
        return 0;
    else if(s[0]==‘H‘)
        return 1;
    else if(s[0]==‘W‘)
        return 2;
    else if(s[0]==‘E‘)
        return 3;
    else if(s[0]==‘Y‘)
        return 4;
}
void InitTree(int *a)
{
    char s[5];
    for(int i=1;i<=n;++i)
    {
        scanf(" %s",s);
        a[i]=Number(s);
        if(a[i]==4)
            ++a[0];
    }
}
void Init(void)
{
    static int a[MAXN],b[MAXN];
    T=(n<<1)+1;
    InitTree(a);
    InitTree(b);
    for(int i=1;i<=n;++i)
        head[i]=nullptr;
    for(int i=1,x;i<=n;++i)
    {
        scanf("%d",&x);
        AddEdges(S,i,!a[i] ? x+a[0] : x);
    }
    for(int i=1,x;i<=n;++i)
    {
        scanf("%d",&x);
        AddEdges(i+n,T,!b[i] ? x+b[0] : x);
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(win[a[i]][b[j]]==1)
                AddEdges(i,j+n,1);
}
void Destroy(void)
{
    for(int i=S;i^T;++i)
        delete head[i];
}
namespace Procyon
{
    int dis[MAXN];
    Edge *cur[MAXN];
    bool BFS(int S,int T)
    {
        queue<int> q;
        memset(dis,0,sizeof dis);
        q.push(S);
        dis[S]=1;
        while(!q.empty())
        {
            int u=q.front(),v;
            q.pop();
            for(Edge *i=head[u];i!=nullptr;i=i->nxt)
                if(i->w && !dis[v=i->to])
                {
                    q.push(v);
                    dis[v]=dis[u]+1;
                }
        }
        return dis[T];
    }
    int DFS(int u,int k)
    {
        if(u==T || !k)
            return k;
        int v,f,sum=0;
        for(Edge *&i=cur[u];i!=nullptr;i=i->nxt)
            if(i->w && dis[v=i->to]==dis[u]+1 && (f=DFS(v,min(k,i->w))))
            {
                k-=f;
                sum+=f;
                i->w-=f;
                i->back->w+=f;
            }
        if(!sum)
            dis[u]=1;
        return sum;
    }
    void Dinic(int S,int T)
    {
        int ans=0;
        while(BFS(S,T))
        {
            memcpy(cur,head,sizeof head);
            ans+=DFS(S,INF);
        }
        printf("%d\n",min(m,ans));
    }
}
int main(int argc,char** argv)
{
    scanf("%d %d",&n,&m);
    Init();
    Procyon::Dinic(S,T);
    Destroy();
    return 0;
}

谢谢阅读。

[Luogu 3701] 「伪模板」主席树

标签:push   empty   ace   表白   一个人   printf   scan   algo   ems   

原文:https://www.cnblogs.com/Capella/p/9069178.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号