spoj AMR11 Robbing Gringotts 双边暴力+hash+费用流
开始的时候，明显背包的复杂度是10000000*25*50 然后认为暴力的复杂度(1<<25)*50 还小于前者，然后就是各种剪纸，然后就是各种tle ，后面看题解又是暴力一半，hash一半，复杂度可以为（sqrt(1<<25)*50）,可见解，然后就是一遍费用流，有km也可以吧，但是只会费用流，模板上，如果不懂暴力一半hash 一半的请看zoj3661，
#include<cstdio>#include<cstring>#define M 60#define N 200000#define mod 133331int n,m;int a[M][M];int map1[M][M];struct H{ int head[N],en; struct E{ int u,v,next; }e[N<<2]; void init(){ memset(head,-1,sizeof(head));en=0; } int change(int x){ return x%mod; } void add(int x){ int t1=change(x); e[en].u=t1;e[en].v=x;e[en].next=head[t1];head[t1]=en++; } int find(int x){ int t1=change(x); for(int i=head[t1];~i;i=e[i].next){ if(e[i].v==x) return 1; } return 0; }}hash;int b[M];int ans[N],en;int tmax;void dfs1(int id,int level,int tsum){ if(level==a[id][0]/2+1){ ans[en++]=tsum; return ; } dfs1(id,level+1,tsum+a[id][level]); dfs1(id,level+1,tsum);}void dfs2(int id,int level,int tsum){ if(level==a[id][0]+1){ hash.add(tsum); return ; } dfs2(id,level+1,tsum+a[id][level]); dfs2(id,level+1,tsum);}void work1(){ for(int i=0;i<m;i++){ hash.init(); en=0; dfs1(i,1,0); dfs2(i,a[i][0]/2+1,0); for(int j=0;j<n;j++){ int t1=b[j]; for(int k=0;k<en;k++){ int t2=ans[k]; if(t2>t1) continue; int t3=t1-t2; if(hash.find(t3)){ map1[i][j]=1; break; } } } }}#define inf 0x3f3f3f3fusing namespace std;/*sumflow is max_flow*/const int MAXN=200;const int MAXM=10000;const int INF=inf;int sumflow;struct Edge{ int u,v,cap,cost,ednxt;}edge[MAXM<<2];int edn,head[MAXN],dist[MAXN],pp[MAXN];bool vis[MAXN];void init(){ edn=0,memset(head,-1,sizeof(head));}void addedge(int u,int v,int cap,int cost){ edge[edn].u=u,edge[edn].v=v,edge[edn].cap=cap,edge[edn].cost=cost, edge[edn].ednxt=head[u],head[u]=edn++; edge[edn].u=v,edge[edn].v=u,edge[edn].cap=0, edge[edn].cost=-cost,edge[edn].ednxt=head[v],head[v]=edn++;}int my_queue[MAXN<<3];int tp,hp;bool spfa(int s,int t,int n){ int i,u,v; hp=0;tp=-1; memset(vis,false,sizeof(vis)); memset(pp,-1,sizeof(pp)); for(i=0;i<=n;i++) dist[i]=INF; vis[s]=true,dist[s]=0; my_queue[++tp]=s; while(tp>=hp) { u=my_queue[tp--];vis[u]=false; for(i=head[u];i!=-1;i=edge[i].ednxt) { v=edge[i].v; if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost) { dist[v]=dist[u]+edge[i].cost; pp[v]=i; if(!vis[v]) { my_queue[++tp]=v; vis[v]=true; } } } } if(dist[t]==INF)return false; return true ;}int mcmf(int s,int t,int n){ int flow=0; int i,minflow,mincost; mincost=0; while(spfa(s,t,n)) { minflow=INF+1; for(i=pp[t];i!=-1;i=pp[edge[i].u]) if(edge[i].cap<minflow) minflow=edge[i].cap; flow+=minflow; for(i=pp[t];i!=-1;i=pp[edge[i].u]) { edge[i].cap-=minflow; edge[i^1].cap+=minflow; } mincost+=dist[t]*minflow; } sumflow=flow; return mincost;}int build(int n,int m){ int sp=0;tp=n+m+1; init(); for(int i=1;i<=n;i++){ addedge(sp,i,1,0); } for(int i=1;i<=m;i++){ addedge(i+n,tp,1,0); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(map1[j-1][i-1]==1){ addedge(i,j+n,1,-b[i-1]); } } } int ans=mcmf(sp,tp,tp+2); return -ans;}int main(){ int cas;while(~scanf("%d",&cas)){ while(cas--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&b[i]); for(int i=0;i<m;i++){ scanf("%d",&a[i][0]); for(int j=1;j<=a[i][0];j++){ scanf("%d",&a[i][j]); } } memset(map1,0,sizeof(map1)); work1(); int ans=build(n,m);//建图 printf("%d\n",ans); } } return 0;}/*1004 43 7 8 103 1 2 42 3 74 0 0 0 01 1*/