Codeforces CodeCraft-20 (Div. 2) E贪心，费用流

Codeforces CodeCraft-20 (Div. 2) E,费用流
原题

题意：

现有n个人需要成为队员或者观众，一个team有p（<7）个位置，需要k个观众。
每个人 当观众贡献ai ，当不同位置的队员分别贡献pij
问如何安排贡献最大。

思路：

这个题官方题解状态压缩DP，这里考虑一个网络流做法。
不考虑要选k个观众，显然就是一个简单的dp。
因为还要选k个观众，需要要分析这个问题的性质。这里我们想一个贪心的思路，对队员按ai进行排序。
先不考虑队员，则我们先选取topk的观众，加进来队员的选择，发现可以分为两种情况讨论：
1 选取的队员在前k个收，我们则需要在(k，n]中再选择一个当观众，考虑只有p个队队员，实际上只需要在(k，k+p]中选一个代替他来当观众。

2 选取的队员在后k个，则直接选择就好。但实际上只需要在topP中做出选择，只有一个p的时候就是最大的那个，多个p的时候涉及的选择，但是一定在topP之中。

根据上述结论，我们可以建图通过费用流帮我们选择（当然dp也可以）。需要准备的节点主要包括P[i]，tmp，O(p)个点，O(p^2)条边。具体建图见代码。

代码：

#include 
using namespace std;
#define X first
#define Y second
#define PB push_back
#define LL long long
#define pii pair
#define MEM(x,y) memset(x,y,sizeof(x))
#define bug(x) cout<<"debug "#x" is "<q;
    for(int i = 0; i < N; i++){
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow &&dis[v] > dis[u] + edge[i].cost ){
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    //return dis[t]<=0;
    if(pre[t] == -1)return false;
    else return true;
}

int minCostMaxflow(int s,int t,LL &cost){
    int flow = 0;
    cost = 0;
    while(spfa(s,t)){
        LL Min = INF;
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){
            if(Min > edge[i].cap - edge[i].flow)
                Min = edge[i].cap - edge[i].flow;
        }
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

pair> a[maxn];
int main(){
    FIO;
    int n,p,k,x;
    cin>>n>>p>>k;
    set e;
    int cnt = n;
    int P[10];
    for(int i=0;i>a[i].X;
    for(int i=0;i>x,a[i].Y.PB(x);
    sort(a,a+n,greater>>());
    for(int i=0;i v;
        for(int j=0;j