字典树。
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;
}
}
#include <cstring>
using namespace std;
const int MAXV=20000;
const int MAXE=1000000;
struct struct_edge{int v;struct_edge* n;};
typedef struct_edge* edge;
typedef void function(int block,int node);
int V;
struct_edge pool[MAXE];
edge top;
edge adj[MAXV];
void build_graph()
{
top=pool;
memset(adj,0,sizeof(adj));
//V;
//add_edge(u,v);
}
void add_edge(int u,int v)
{
top->v=v,top->n=adj[u],adj[u]=top++;
}
int stamp;
int DFN[MAXV];
int LOW[MAXV];
int st;
int s[MAXV];
bool ins[MAXV];
bool visited[MAXV];
int depth;
edge e[MAXV];
int root[MAXV];
int block;
void tarjan(function f)
{
memset(visited,0,sizeof(visited));
memset(ins,0,sizeof(ins));
st=0;
block=0;
for (int start=0;start<V;start++)
if (!visited[start])
{
depth=0;
root[depth]=start;
e[depth]=adj[root[depth]];
DFN[root[depth]]=LOW[root[depth]]=++stamp;
ins[s[st++]=root[depth]]=true;
visited[root[depth]]=true;
do
{
if (e[depth])
{
if (!visited[e[depth]->v])
{
int depth_=depth+1;
e[depth_]=adj[root[depth_]=e[depth]->v];
DFN[root[depth_]]=LOW[root[depth_]]=++stamp;
ins[s[st++]=root[depth_]]=true;
visited[root[depth_]]=true;
e[depth]=e[depth]->n;
depth++;
}
else if (ins[e[depth]->v])
{
if (LOW[root[depth]]>DFN[e[depth]->v])
LOW[root[depth]]=DFN[e[depth]->v];
e[depth]=e[depth]->n;
}
else e[depth]=e[depth]->n;
}
else
{
if (LOW[root[depth]]==DFN[root[depth]])
{
do
{
ins[s[--st]]=false;
f(block,s[st]);
}
while (s[st]!=root[depth]);
block++;
}
if (depth>0)
{
int depth_=depth-1;
if (LOW[root[depth_]]>LOW[root[depth]])
LOW[root[depth_]]=LOW[root[depth]];
}
depth--;
}
}
while (depth>=0);
}
}
typedef struct_edge struct_list;
typedef edge list;
int block_id[MAXV];
struct_list spool[MAXV];
list stop;
list set[MAXV];
#define T(x) ((x)<<1)
#define F(x) (((x)<<1)|1)
void build_2sat()
{
stop=spool;
memset(set,0,sizeof(set));
build_graph();
//add_edge(u,v);
}
void function_2sat(int block,int node)
{
block_id[node]=block;
stop->v=node,stop->n=set[node],set[node]=stop++;
}
#include <iostream>
using namespace std;
bool possible_2sat()
{
tarjan(function_2sat);
for (int i=0;i<(V>>1);i++)
if (block_id[T(i)]==block_id[F(i)])
return false;
return true;
}
int N,M;
int B[MAXV];
int main()
{
int T;
cin>>T;
for (int t=1;t<=T;t++)
{
cin>>N>>M;
V=N*2;
build_2sat();
for (int i=0;i<N;i++)
cin>>B[i],B[i]--;
for (int i=0;i<M;i++)
{
int a,b,k;
cin>>a>>b>>k;
a--,b--;
if (k)
{
if (B[a]==B[b])
{
add_edge(T(a),F(b));
add_edge(F(b),T(a));
add_edge(F(a),T(b));
add_edge(T(b),F(a));
}
else if ((B[a]+1)%3==B[b]) add_edge(F(a),F(b));
else add_edge(F(b),F(a));
}
else
{
if (B[a]==B[b])
{
add_edge(T(a),T(b));
add_edge(T(b),T(a));
add_edge(F(a),F(b));
add_edge(F(b),F(a));
}
else if ((B[a]+1)%3==B[b])
{
add_edge(F(a),T(b));
add_edge(T(b),F(a));
add_edge(T(a),F(a));
add_edge(F(b),T(b));
}
else
{
add_edge(F(b),T(a));
add_edge(T(a),F(b));
add_edge(T(b),F(b));
add_edge(F(a),T(a));
}
}
}
cout<<"Case #"<<t<<": "<<(possible_2sat()?"yes":"no")<<endl;
}
}
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-28
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
#include <cstring>
using namespace std;
typedef long long int lli;
const int MAXN=12;
const int MAXSTATE=300001;
int N,M;
char map[MAXN][MAXN];
int sc,SC;
int s_[MAXSTATE],S_[MAXSTATE];
lli f_[MAXSTATE],F_[MAXSTATE];
int* s=s_;
int* S=S_;
lli* f=f_;
lli* F=F_;
void qsort(int l,int r)
{
int i=l,j=r;
int mid=S[(l+r)>>1];
while (i<=j)
{
while (S[i]<mid) i++;
while (S[j]>mid) j--;
if (i<=j)
{
int SS;
lli SF;
SS=S[i],S[i]=S[j],S[j]=SS,SF=F[i],F[i]=F[j],F[j]=SF;
i++,j--;
}
}
if (l<j) qsort(l,j);
if (i<r) qsort(i,r);
}
lli min(lli a,lli b)
{
return a<b?a:b;
}
int run()
{
cin>>N>>M;
int lasti=0,lastj=0;
for (int i=1;i<=N;i++)
for (int j=1;j<=M;j++)
{
cin>>map[i][j];
if (map[i][j]=='o') lasti=i,lastj=j;
}
N++,M++;
lli answer=(~0u);
SC=0;
S[SC]=0;
F[SC]=0;
SC++;
for (int i=0;i<N;i++)
{
for (int j=0;j<M;j++)
{
int* ss;
lli* sf;
ss=s,s=S,S=ss,sf=f,f=F,F=sf;
sc=SC,SC=0;
#define getp(state,p) (((state)>>((p)<<1))&3)
#define replace(state,p,n) (((state)&(~(3<<((p)<<1))))|n<<((p)<<1))
#define getl(state) getp(state,j)
#define getu(state) getp(state,j+1)
#define replacedr(state,d,r) replace(replace(state,j,d),j+1,r)
#define getcl(state,p,ns)\
do\
{\
ns=replacedr(state,0,0);\
int get=2;\
for (int i=p+2;i<=M;i++)\
{\
if (getp(ns,i)==1) get++;\
else if (getp(ns,i)==2) get--;\
if (get==1)\
{\
ns=replace(ns,i,1);\
break;\
}\
}\
}\
while (false)
#define getcr(state,p,ns)\
do\
{\
ns=replacedr(state,0,0);\
int get=2;\
for (int i=p-1;i>=0;i--)\
{\
if (getp(ns,i)==2) get++;\
else if (getp(ns,i)==1) get--;\
if (get==1)\
{\
ns=replace(ns,i,2);\
break;\
}\
}\
}\
while (false)
for (int si=0;si<sc;si++)
{
bool out=true;
for (int p=0;p<=j;p++)
if (getp(s[si],p)) out=!out;
if (map[i][j]=='o'&&out) continue;
if (map[i][j]=='x'&&!out) continue;
int l=getl(s[si]),u=getu(s[si]);
if (l&&u)
{
int ns;
if (l==2&&u==1) ns=replacedr(s[si],0,0);
else if (l==1&&u==1) getcl(s[si],j,ns);
else if (l==2&&u==2) getcr(s[si],j,ns);
else
{
if (((i>lasti)||(i==lasti&&j>=lastj))&&replacedr(s[si],0,0)==0) answer=min(answer,f[si]);
continue;
}
S[SC]=ns;
F[SC]=f[si];
SC++;
}
else if (l)
{
int ns;
ns=replacedr(s[si],l,u);
S[SC]=ns;
F[SC]=f[si]+1;
SC++;
ns=replacedr(s[si],u,l);
S[SC]=ns;
F[SC]=f[si]+1;
SC++;
}
else if (u)
{
int ns;
ns=replacedr(s[si],l,u);
S[SC]=ns;
F[SC]=f[si]+1;
SC++;
ns=replacedr(s[si],u,l);
S[SC]=ns;
F[SC]=f[si]+1;
SC++;
}
else
{
int ns;
//there can be a box without plug
ns=replacedr(s[si],0,0);
S[SC]=ns;
F[SC]=f[si];
SC++;
ns=replacedr(s[si],1,2);
S[SC]=ns;
F[SC]=f[si]+2;
SC++;
}
}
{
qsort(0,SC-1);
int RSC=0;
int i=0;
while (i<SC)
{
int j=i+1;
while (j<SC&&S[i]==S[j]) F[i]=min(F[j],F[i]),j++;
S[RSC]=S[i];
F[RSC++]=F[i];
i=j;
}
SC=RSC;
}
}
{
int RSC=0;
int i=0;
while (i<SC)
{
while (i<SC&&getp(S[i],M)) i++;
if (i<SC) S[RSC]=S[i]<<(1<<1),F[RSC++]=F[i++];
}
SC=RSC;
}
}
static int casen;
cout<<"Case #"<<++casen<<": "<<int(answer)<<endl;
return 0;
}
int main()
{
int T;
for (cin>>T;T;T--) run();
}
