并不难的一道题，甚至比一双木棋还容易一些

关键点就是一个：怎么处理“最优结果”，即总体字典序最小

显然要反悔。匹配问题反悔套路就多了

 

法一：

变形匈牙利算法

记录右部点导师的战队情况

枚举每个人，枚举每一层进行尝试匹配

最多把前面的人的边都遍历到，总共O(n*n*c)

 

第二问

显然二分

第一问时候存图即可

 

技巧：

n，m很小，充分利用桶和计数器，可以不带set等logn结构，也不用vector（防止卡常）

#include
      
       #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){
    for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=201;int n,m,C;int vis[N];int con[N][N];int to[N][N][N],cnt[N][N];int b[N],mem[N][N],p[N];//teacherint s[N];int c[N];//ans1 struct node{    int mem[N][N],p[N];}tim[N];bool dfs(int x,int d,int st){    for(reg i=1;i<=cnt[x][d];++i){        int y=to[x][d][i];        if(vis[y]==st) continue;        vis[y]=st;        if(p[y]
          
         
        
       
      

 

法二：

动态加边dinic最大流

第一问就是把匈牙利变成dinic，据说要把匹配失败的边删除防止TLE

第二问：

二分。用vector存第一问每次图的边

一次性把前s[i]个边都加入，跑dinic

 

技巧：

删除的话，只用vector.pop_back即可。其他的边，由于找不到增广路，所以依然流量守恒的

 

 

题面很长，实际不难

就是考察一个匹配的反悔机制了

暴力分还很多、、、