codeforces 976 F Minimal k-covering

codeforces 976 F Minimal k-covering

​​ You are given a bipartite graph G = (U, V, E), U is the set of vertices of the first part, V is the set of vertices of the second part and E is the set of edges. There might be multiple edges.

Let’s call some subset of its edges k-covering iff the graph has each of its vertices incident to at least k edges. Minimal k-covering is such a k-covering that the size of the subset is minimal possible.

Your task is to find minimal k-covering for each , where minDegree is the minimal degree of any vertex in graph G.

Input The first line contains three integers n1, n2 and m (1 ≤ n1, n2 ≤ 2000, 0 ≤ m ≤ 2000) — the number of vertices in the first part, the number of vertices in the second part and the number of edges, respectively.

The i-th of the next m lines contain two integers ui and vi (1 ≤ ui ≤ n1, 1 ≤ vi ≤ n2) — the description of the i-th edge, ui is the index of the vertex in the first part and vi is the index of the vertex in the second part.

Output For each print the subset of edges (minimal k-covering) in separate line.

The first integer cntk of the k-th line is the number of edges in minimal k-covering of the graph. Then cntk integers follow — original indices of the edges which belong to the minimal k-covering, these indices should be pairwise distinct. Edges are numbered 1 through m in order they are given in the input.

Examples Input

Copy 3 3 7 1 2 2 3 1 3 3 2 3 3 2 1 2 1 Output

Copy 0 3 3 7 4 6 1 3 6 7 4 5 Input

Copy 1 1 5 1 1 1 1 1 1 1 1 1 1 Output

Copy 0 1 5 2 4 5 3 3 4 5 4 2 3 4 5 5 1 2 3 4 5 假如没有这么多组询问 显然下界最小流可做

但是多组询问每次暴力重建边 复杂度不正确

考虑首先算出每个点的度 然后 原有的边都连1的边 然后每个点都先连上 度数减最小值的边 那么

这样每次倒着做 做完一次就可以添加一条容量为1的边 然后统计答案即可 这里的流量意味着不选

也就是每次跑最大流表示最多不选的边 然后每个点给的容量表示这个点最多不选几条边 然后这样倒着做 就可以每次动态加边跑网络流了 复杂度(n+m)^2

#include#include#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; }const int N=4400;const int inf=0x3f3f3f3f;struct node{ int y,next,z,id;}data[N<<1];int h[N],level[N],num=1,d[N],ans[2200][2200],cur[N],T,n1,n2,m;inline bool bfs(){ queueq;q.push(0);memset(level,0,sizeof(level));level[0]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if(level[y]||!z) continue;level[y]=level[x]+1;if(y==T) return 1;q.push(y); } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss; } }return ss-s;}inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num; data[++num].y=x;data[num].next=h[y];data[num].z=0;h[y]=num;}int main(){ freopen("cf976f.in","r",stdin); n1=read();n2=read();m=read();T=n1+n2+1; for (int i=1;i<=m;++i){ int x=read(),y=read()+n1;++d[x];++d[y]; data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=1;data[num].id=i; data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=0;data[num].id=i; }int mn=inf,ans1=m; for (int i=1;i<=n1;++i) mn=min(mn,d[i]);for (int i=1;i<=n2;++i) mn=min(mn,d[i+n1]); for (int i=1;i<=n1;++i) if (d[i]-mn) insert1(0,i,d[i]-mn); for (int i=1;i<=n2;++i) if (d[i+n1]-mn) insert1(i+n1,T,d[i+n1]-mn); for (int i=mn;~i;--i){ while(bfs()) memcpy(cur,h,sizeof(h)),ans1-=dfs(0,inf); for (int j=3;j<=num;j+=2) if (data[j].y>=1&&data[j].y<=n1&&!data[j].z) ans[i][++ans[i][0]]=data[j].id; for (int j=1;j<=n1;++j) insert1(0,j,1);for (int j=1;j<=n2;++j) insert1(j+n1,T,1); } for (int i=0;i<=mn;++i){ printf("%d ",ans[i][0]); for (int j=1;j<=ans[i][0];++j) printf("%d ",ans[i][j]);puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。