原题： http://codeforces.com/problemset/problem/730/I
题意：
每个人有ab值，现在选择x个人取a，y个人取b，求和的最大值。
解析：
dp不会，直接费用流即可。ab两点连汇点，流量为x和y，每个人的点连向ab，流量1，费用（-其值），跑一下即可。
#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> using namespace std; #define LL long long #define pill pair<int,int> const int inf=0x3f3f3f3f; const LL infll=1e18; const int N=4010,M=202020; int head[N],nex[M],to[M],val[M],cost[M],now; void add(int a,int b,int v,int c){ to[++now]=b;val[now]=v;cost[now]=c;nex[now]=head[a];head[a]=now; to[++now]=a;val[now]=0;cost[now]=-c;nex[now]=head[b];head[b]=now; } //********************* int sp,ep,dis[N]; bool vis[N]; int pre[N]; bool SPFA(int &flow,int &cos){ memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); for(int i=0;i<N;i++)dis[i]=inf; queue<int>Q; dis[sp]=0;vis[sp]=1;Q.push(sp); int d=inf; while(!Q.empty()){ int p=Q.front();Q.pop(); vis[p]=0; for(int i=head[p];~i;i=nex[i]){ int u=to[i]; if(val[i]>0&&dis[u]-cost[i]>dis[p]){ dis[u]=dis[p]+cost[i]; pre[u]=i; if(!vis[u]){ vis[u]=1;Q.push(u); } } } } if(dis[ep]==inf)return 0; for(int i=pre[ep];~i;i=pre[to[i^1]]){ d=min(d,val[i]); } for(int i=pre[ep];~i;i=pre[to[i^1]]){ val[i]-=d; val[i^1]+=d; cos+=cost[i]*d; } flow+=d; return 1; } int MinCost(){ int flow=0,cost=0; while(SPFA(flow,cost)){} return cost; } //*********************** int n,m,k,W; struct node{ int id,s,t,v,op; bool operator < (const node &r)const{ return s<r.s; } }e[201]; void init(){ now=-1;//要求第一条边为0 memset(head,-1,sizeof(head)); } //sp -p-> point --> ep int x[N],y[N]; int main(){ int n,a,b; scanf("%d%d%d",&n,&a,&b); init(); sp=0;ep=N-1; for(int i=1;i<=n;i++){ scanf("%d",x+i); } for(int i=1;i<=n;i++){ scanf("%d",y+i); } for(int i=1;i<=n;i++)add(0,i,1,0),add(i,n+1,1,-x[i]),add(i,n+2,1,-y[i]); add(n+1,ep,a,0); add(n+2,ep,b,0); int ans=MinCost(); printf("%d\n",-ans); for(int i=head[n+1];~i;i=nex[i]){ int u=to[i]; if(u>=1&&u<=n&&val[i]==1)printf("%d ",u); } printf("\n"); for(int i=head[n+2];~i;i=nex[i]){ int u=to[i]; if(u>=1&&u<=n&&val[i]==1)printf("%d ",u); } printf("\n"); }