CF976F Minimal k-covering

因为限制是“至少被k条边覆盖”,不太好搞,我们把它转化成,"对于点u,至多选择degreeukdegree_u-k条边不覆盖"。而这个“至多”的限制,就可以看作是流量。所以建图很好建。
类似这样:

但是有个问题,如果对于所有的kk都暴力重新跑一遍,复杂度最坏是(mn)2(m\sqrt n)^2的显然不太行。但是我们注意到这道题有个特殊的性质:最大流的最大值是mm。所以最多只会增广mm次,单次增广的复杂度显然是O(n+m)O(n+m)的。最后算下来总复杂度应该是(n+m)2(n+m)^2的。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2*2e3+100;
const int base=2000;
const int s=maxn-2,t=maxn-1;
const int inf=1e9+100;
int head[maxn];
pii ori[maxn];
int cnt=1;
struct gg{
	int u,v,w,idx,next;
}side[maxn*4];
void ins(int u,int v,int w,int idx){
	side[++cnt]=(gg){u,v,w,idx,head[u]};head[u]=cnt;
	side[++cnt]=(gg){v,u,0,idx,head[v]};head[v]=cnt;
}
int d[maxn];
vector<vi>ans;
int cur[maxn],rk[maxn];
queue<int>q;
bool bfs(){
	memset(rk,0,sizeof(rk));while(!q.empty())q.pop();
	q.push(s);rk[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=side[i].next){
			int v=side[i].v;if(rk[v]||!side[i].w)continue;
			rk[v]=rk[u]+1;q.push(v);
		}
	}
	if(rk[t])return 1;
	return 0;
}
int dfs(int u,int flow){
	if(u==t||!flow)return flow;
	int tot=0;
	for(int &i=cur[u];i;i=side[i].next){
		int v=side[i].v;if(side[i].w<=0||rk[v]!=rk[u]+1)continue;
		int sent=dfs(v,min(flow,side[i].w));
		//cout<<v<<"---------->"<<u<<"   flow="<<sent<<endl;
		flow-=sent,tot+=sent;side[i].w-=sent,side[i^1].w+=sent;
		if(!flow)break;
	}
	return tot;
}
void dinic(){
	while(bfs()){
		memcpy(cur,head,sizeof(head));
		dfs(s,inf);		
	}
}
int n1,n2,m;
void debug(){
	rep(i,1,n1)for(int j=head[i];j;j=side[j].next)cout<<">>"<<side[j].u<<' '<<side[j].v<<' '<<side[j].w<<endl;
	rep(i,1,n2)for(int j=head[i+base];j;j=side[j].next)cout<<">>"<<side[j].u<<' '<<side[j].v<<' '<<side[j].w<<endl;
	for(int j=head[s];j;j=side[j].next)cout<<">>"<<side[j].u<<' '<<side[j].v<<' '<<side[j].w<<endl;
	cout<<"END"<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n1>>n2>>m;
	int mi_d=1e9,mx_d=0;
	rep(i,1,m){
		int u,v;cin>>u>>v;ori[i]=mk(u,v);d[u]++,d[v+base]++;
		ins(u,v+base,1,i);
	}
	rep(i,1,n1)mi_d=min(mi_d,d[i]),mx_d=max(mx_d,d[i]);
	rep(i,1,n2)mi_d=min(mi_d,d[i+base]),mx_d=max(mx_d,d[i+base]);
	//容量 \in [u_degree-mi_degree,u_degree];
	rep(i,1,n1){
		ins(s,i,d[i]-mi_d-1,0);
	}
	rep(i,1,n2){
		ins(i+base,t,d[i+base]-mi_d-1,0);
	}
	
	//debug();
	for(int k=mi_d;k>=0;k--){
		for(int i=head[s];i;i=side[i].next){
			//int v=side[i].v;
			if(!side[i].idx)side[i].w++;
		}
		rep(i,1,n2){
			for(int j=head[i+base];j;j=side[j].next){
				int v=side[j].v;
				if(!side[j].idx&&v==t)side[j].w++;
			}
		}
	//	debug();
		dinic();
		vi tmp;vi jk;
		rep(gg,base+1,base+n2)for(int i=head[gg];i;i=side[i].next)
		if(side[i].idx&&side[i].v<=n1&&side[i].w)
		tmp.pb(side[i].idx);
		sort(tmp.begin(),tmp.end());
		int now=0;
		rep(i,1,m){
			if(now<tmp.size()&&tmp[now]==i){
				now++;continue;
			}
			jk.pb(i);
		}
		ans.pb(jk);
	}
	for(int i=ans.size()-1;i>=0;i--){
		vi tmp=ans[i];cout<<tmp.size()<<' ';
		rep(j,0,tmp.size()-1)cout<<tmp[j]<<' ';
		cout<<endl;
	}
	return 0;
}