Educational Codeforces Round 134 (Rated for Div. 2) F - Matching Reduction 最小点覆盖

真傻逼Σ(☉▽☉"a——wa23是因为数组开小了，wa53是数组开大了爆了

（不能任性随便开了

问最少删多少点使得最大匹配数-1

这题就考一个结论：最大匹配数==最小点覆盖

所以很典的删最少点其实只要删一个点，也就是最小点覆盖集合里的任意一点。

 转化为求最小点覆盖，有dinic算法和HK算法，时间复杂度都为sqrt(n)*m，其中n为较小的那方点数，m为边数，复杂度证明见：Dinic 二分图匹配 / Hopcroft-Karp 算法 复杂度简单证明 - cjoier_Itst - 博客园 (cnblogs.com)

求出最大匹配后，根据上图证明里的做法，用mark函数打标记

最后遍历所有边，满流的即为匹配边，但选取该边的左部点还是右部点取决于标记

剩下的就是一些dirty_work

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct lys{
    ll from,to,nxt,c;
}e[maxn*6];
ll cnt=1,s,t,dep[maxn<<1],head[maxn<<1];
ll val[maxn*6];// val && edge 
void add(ll from,ll to,ll c)
{
    cnt++;
    e[cnt].from=from;e[cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;val[cnt]=c;
}

bool  bfs()
{   queue<int>q;
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=e[i].nxt)
        {
            ll to=e[i].to;
            if(val[i]&&!dep[to])
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t];    
    // dep[t]!=0  say that t can be reached 
}
ll dfs(int u,ll in)
{
    if(u==t) 
    return in;
    ll out=0;
    for(ll i=head[u];i&&in;i=e[i].nxt)
    {
      int to=e[i].to;
      if(val[i]&&dep[to]==dep[u]+1)
      {
          ll res=dfs(to,min(val[i],in));
          val[i]-=res;// val :e[i].c-e[i].f, i..e left network 
          val[i^1]+=res;
          in-=res;
          out+=res;
      }    
    }
    
    if(!out) 
      dep[u]=0;
    return out;
}
void dinic(){
    ll ans=0;
    while(bfs())     
    ans+=dfs(s,1e18);
//    cout<<"#max flow："<<ans<<endl;
}
bool vis[maxn<<1];
void mark(int u){
    if(vis[u]) return;
    vis[u]=1;
    for(ll i=head[u];i;i=e[i].nxt){
        ll to=e[i].to;
        if(val[i]) {
            mark(to);
        }
    }
}
int main()
{   //freopen("lys.in","r",stdin);
    ll n1,n2,m,q;
    scanf("%lld%lld%lld%lld",&n1,&n2,&m,&q);
    s=n1+n2+1;
    t=s+1;
    ll sum=0;
    for(ll i=1;i<=m;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v+n1,1);
        add(v+n1,u,0);
    }
    for(ll i=1;i<=n1;i++) {
        add(s,i,1);
        add(i,s,0);
    }
    for(ll i=1;i<=n2;i++){
        add(i+n1,t,1);
        add(t,i+n1,0);
    }
    dinic();
    // find min point cover
    mark(s);
    vector<pair<ll,ll>>point_cover;
    //cout<<"debug"<<endl;
    for(ll i=1;i<=m;i++){
        if(val[i<<1]==0){// find one
            ll to=e[i<<1].to,from=e[i<<1].from;
            sum+=i;
            if(vis[to]){
                point_cover.push_back(make_pair(i,-(to-n1)));
            //    cout<<i<<" "<<from<<" "<<-(to-n1)<<endl;
            }
            else {
                point_cover.push_back(make_pair(i,from));
            //   cout<<i<<" "<<from<<" "<<to<<endl;
            }
        }
    }
    for(ll tc=1;tc<=q;tc++){
        ll op;
        scanf("%lld",&op);
        if(op==1){
            puts("1");
            pair<ll,ll> it=point_cover.back();
            point_cover.pop_back();
            printf("%lld\n",it.second);
            sum-=it.first;
            printf("%lld\n",sum);
        }
        else {
            printf("%d\n",point_cover.size());// min point cover == max matched
            for(auto x:point_cover)
                printf("%lld ",x.first);
            puts("");
        }
        fflush(stdout);
        //cout<<"===="<<endl;
    }
}