题意

有一个 $n$ 个点的 DAG，现在有 $k$ 波进攻，第 $i$ 波有 $i$ 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备，可以花 $1$ 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$，如果花费了 $t_i$ 时间准备，如果不会所有点都被占领，就会获得收益 $\max(0,a_i-tb_i)$，如果被占领就不会有收益了，求最大收益，输出方案。

$n \leq 50$。

题解

先考虑如何求是否能全部占领：其实就是判断 DAG 的最小链覆盖和 $i$ 的关系。求最小链覆盖又可以转化成二分图求最大匹配，设最大匹配为 $m$，那么如果第 $i$ 波能胜利，就需要满足 $i < n-m \Rightarrow m \leq n-i-1$。而这个操作实际上就是每次删除一个点，一个想法是我们是否能找到一个很优的删点序列，然后剩下的就 dp 出来怎么删就好了。

我们肯定想每次删都能让最大匹配减一，然后我比赛时就想到这里停了，其实应该信仰一发写个暴力找的试试的。实际上可以证明存在这样的序列：因为首先最大匹配等于最小点覆盖，那么我们求出一个最小点覆盖，然后每次删掉最小点覆盖中的一个点一定会让最小点覆盖减少 $1$，所以这也顺便构造出方案了。

接下来问题是如何求最小点覆盖：我们先求出一个最大匹配，然后匹配边向左，非匹配边向右，我们从左边的所有非匹配点开始 dfs，把左边没有被访问的匹配点和右边被访问的匹配点全都选出来就好了。

首先数量肯定是对的：右边一个匹配点被访问对应左边一个匹配点被访问，总数量不变；

正确性&&如何想到的：我们一开始肯定有个 naive 的想法是全部选左边的匹配点，但是这样显然不对，它不能覆盖左边的非匹配点和右边的匹配点的连边（注意这里不会有左边非匹配点连右边非匹配点的边，否则不是最大匹配）。于是我们遍历这种边，如果有这种边，就转而去选它对应的右边的匹配点，为了维持数量我们要不选对应的左边匹配点，这时候就递归成了要处理左边刚刚被不选的点和右边点之间的边的问题了，再 dfs 即可。

这启发我们：

• 遇到很多问题要思考最大匹配能否转成其他的东西。。这个题就启发我们二分图最大匹配一定有完美消除序列。
• 二分图问题很多都可以求出最大匹配，然后重定向考虑。

复杂度 $O(n^3)$。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100 + 5;
int n,m,k;

struct Edge{
    int to,w,nxt;
}e[MAXN*MAXN*10];

int cnt=1,head[MAXN],cur[MAXN];

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
}

int dep[MAXN],N,S,T;

inline bool bfs(){
    FOR(i,1,N) cur[i] = head[i],dep[i] = 0;
    std::queue<int> q;q.push(S);dep[S] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].w > 0 && !dep[e[i].to]){
                dep[e[i].to] = dep[v] + 1;
                q.push(e[i].to);
            }
        }
    }
    return dep[T];
}

inline int dfs(int v,int lim=1e9){
    if(v == T) return lim;
    if(!lim) return 0;
    int res = 0;
    for(int &i = cur[v];i;i = e[i].nxt){
        if(e[i].w > 0 && dep[e[i].to] == dep[v] + 1){
            int t = dfs(e[i].to,std::min(lim,e[i].w));
            if(t){
                lim -= t;e[i].w -= t;
                e[i^1].w += t;res += t;
            }
        }
    }
    return res;
}

inline int Dinic(){
    int res = 0,t = 0;
    while(bfs()) while((t = dfs(S))) res += t;
    return res;
}

bool vis[MAXN];
int edge[MAXN];

inline void dfs1(int v){
    vis[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to <= 2*n && e[i].w && !vis[e[i].to]){
            dfs1(e[i].to);
        }
    }
}

LL f[MAXN][MAXN];int pre[MAXN][MAXN];
int x[MAXN],y[MAXN];
int req[MAXN];
// 前 i 波 当前最大匹配是 j

int main(){
    scanf("%d%d%d",&n,&m,&k);
    S = 2*n+1;T = N = 2*n+2;
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v+n,1);
    }
    FOR(i,1,k) scanf("%d%d",x+i,y+i);
    FOR(i,1,n) edge[i] = cnt+1,add(S,i,1),edge[i+n] = cnt+1,add(i+n,T,1);
    int sz = Dinic();
    FOR(i,1,n) if(!e[edge[i]^1].w) dfs1(i);
    std::vector<int> vec;
    FOR(i,1,n) if(!vis[i] && e[edge[i]^1].w) vec.pb(i);
    FOR(i,n+1,2*n) if(vis[i] && e[edge[i]^1].w) vec.pb(i);
    CLR(f,-1);
    f[0][sz] = 0;
    FOR(i,1,k){
        FOR(j,0,sz){
            if(f[i-1][j] < 0) continue;
            FOR(k,0,j){
                LL gx = std::max(0ll,x[i]-1ll*k*y[i]);
                if(j-k >= n-i) gx = 0;
                if(f[i][j-k] < f[i-1][j]+gx){
                    f[i][j-k] = f[i-1][j]+gx;
                    pre[i][j-k] = k;
                }
            }
        }
    }
    int ps = 0;
    FOR(i,1,sz) if(f[k][i] > f[k][ps]) ps = i;
    ROF(i,k,1){
        req[i] = pre[i][ps];
        ps += pre[i][ps];
    }
    std::vector<int> ans;
    FOR(i,1,k){
        FOR(j,1,req[i]){
            int t = vec.back();vec.pop_back();
            if(t <= n) ans.pb(t);
            else ans.pb(n-t);
        }
        ans.pb(0);
    }
    printf("%d\n",SZ(ans));
    for(auto x:ans) printf("%d ",x);puts("");
    return 0;
}