@Boleyn Su's

字典树。

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

#include <sstream>

#include <map>

#include <vector>

#include <set>

using namespace std;

struct Trie

{

    Trie* f;

    Trie* c[26];

    int d;

};

Trie pool[4*1024*1024];

Trie* top=pool;

Trie* root;

#define f(x) ((x)-'a')

void calc(Trie* p,char* s,int d,set<Trie*>& get)

{

    if (p)

    {

       if (*s)

       {

           calc(p->c[f(*s)],s+1,d,get);

           if (d)

           {

              for (int i=0;i<26;i++)

                  calc(p->c[i],s,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p,s+1,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p->c[i],s+1,d-1,get);

           }

       }

       else get.insert(p);

    }

}

int main()

{

    root=top++;

    int n,m;

    cin>>n;

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

    {

       char db[16];

       cin>>db;

       Trie* p=root;

       char* s=db;

       while (*s)

       {

           if (!p->c[f(*s)]) top->f=p,p->c[f(*s)]=top++;

           p=p->c[f(*s)];

           p->d++;

           s++;

       }

    }

    cin>>m;

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

    {

       char s[1024];

       int d;

       cin>>s>>d;

       set<Trie*> get;

       calc(root,s,d,get);

       int answer=0;

       for (set<Trie*>::reverse_iterator it=get.rbegin();it!=get.rend();it++)

       {

           Trie* p=*it;

           int delta=p->d;

           while (p!=root)

           {

              p=p->f;

              set<Trie*>::iterator t=get.find(p);

              if (t!=get.end()) delta=0;

           }

           answer+=delta;

       }

       cout<<answer<<endl;

    }

}

最小费用流。

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

using namespace std;

#define oo 0x7f7f7f7f

#define MAXEDGE 510000

#define MAXV 1002

typedef struct struct_edge* edge;

struct struct_edge{int v,c,d;edge n,b;};

struct_edge pool[MAXEDGE];

edge top;

int S,T,V;

edge adj[MAXV];

int q[MAXV];

bool inq[MAXV];

int head,tail;

edge p[MAXV];

int d[MAXV];

void add_edge(int u,int v,int c,int d)

{

     top->v=v,top->c=c,top->d=d,top->n=adj[u],adj[u]=top++;

     top->v=u,top->c=0,top->d=-d,top->n=adj[v],adj[v]=top++;

     adj[u]->b=adj[v];

     adj[v]->b=adj[u];

}

int min_cost_flow(int n,int t)

{

    int flow=0,cost=0;

    for (;;)

    {

        memset(d,oo,sizeof(d));

        inq[q[head=tail=0]=S]=true;

        d[S]=0;

        p[S]=0;

        while (head<=tail)

        {

              int u;

              inq[u=q[(head++)%MAXV]]=false;

              for (edge i=adj[u];i;i=i->n)

                  if (i->c&&d[i->v]>d[u]+i->d)

                  {

                     if (!inq[i->v])

                        inq[q[(++tail)%MAXV]=i->v]=true;

                     d[i->v]=d[u]+i->d;

                     p[i->v]=i;

                  }

        }

        if (d[T]==oo) break;

        else

        {

            int delta=oo;

            for (edge i=p[T];i;i=p[i->b->v])

                if (delta>i->c) delta=i->c;

            for (edge i=p[T];i;i=p[i->b->v])

                i->c-=delta,i->b->c+=delta;

            flow+=delta;

            cost+=d[T]*delta;

        }

    }

    if (flow!=n) return 1+t;

    return cost;

}

int E;

int u[MAXEDGE],v[MAXEDGE];

int n;

int mine[MAXV];

int price[MAXV];

bool source[MAXV];

int total_price;

int result(int t)

{

    if (t)

    {

       int answer=-1,i=0;

       if (t==n)

       {

           source[0]=true;

           int get=result(t-1);

           if (get>answer) answer=get;

           source[0]=false;

       }

       else

       {

           int k=n-t;

           while (k) if (source[i++]) k--;

           while (i<n*2)

           {

              if (!source[i])

              {

                  source[i]=true;

                  int get=result(t-1);

                  if (get>answer) answer=get;

                  source[i]=false;

              }

              i++;

           }

       }

       return answer;

    }

    else

    {

       memset(adj,0,sizeof(adj));

       top=pool;

       S=V+V,T=V+V+1;

       for (int i=0;i<E;i++)

           add_edge(u[i]+V,v[i],1,0),

           add_edge(v[i]+V,u[i],1,0);

       for (int i=0;i<V;i++)

           add_edge(i,i+V,1,price[i]);

       for (int i=0;i<n*2;i++)

           if (source[i]) add_edge(S,mine[i],1,0);

           else add_edge(mine[i]+V,T,1,0);

       return total_price-min_cost_flow(n,total_price);

    }

}

int main()

{

    int T;

    cin>>T;

    for (int t=0;t<T;t++)

    {

       cin>>V>>E;

       for (int i=0;i<E;i++)

           cin>>u[i]>>v[i];

       cin>>n;

       for (int i=0;i<n*2;i++) cin>>mine[i];

       total_price=0;

       for (int i=0;i<V;i++) cin>>price[i],total_price+=price[i];

       cout<<result(n)<<endl;

    }

}