因为限制是“至少被k条边覆盖”,不太好搞,我们把它转化成,"对于点u,至多选择条边不覆盖"。而这个“至多”的限制,就可以看作是流量。所以建图很好建。
类似这样:
但是有个问题,如果对于所有的都暴力重新跑一遍,复杂度最坏是的显然不太行。但是我们注意到这道题有个特殊的性质:最大流的最大值是。所以最多只会增广次,单次增广的复杂度显然是的。最后算下来总复杂度应该是的。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#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;
}