本文主要是介绍Minimal k-covering CodeForces - 976F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
具体建图看官方题解点击打开链接
因为要求最小的边覆盖 所以要去掉最多的边 所以可以用网络流来解决
先从最大值到最小值来枚举 源点到二分图第一部分以及二分图第二部分到汇点所连的边的权值代表当前情况下每个点需要去掉几条边 然后跑完一遍最大流后残量网络中的边即为所求 然后加大源汇点的流量 表示下一次要多去掉一些边
#include <bits/stdc++.h>
using namespace std;
#define N 0x3f3f3f3fstruct node
{int v;int w;int id;int next;
};queue <int> que;
vector <int> ans[4010];
node edge[12010];
int first[4010],degree[4010],dis[4010],gap[4010],cur[4010],pre[4010];
int n1,n2,m,num,ss,ee;void addedge(int u,int v,int w,int id)
{edge[num].v=v;edge[num].w=w;edge[num].id=id;edge[num].next=first[u];first[u]=num++;return;
}void bfs()
{int i,u,v;while(!que.empty()) que.pop();memset(dis,-1,sizeof(dis));memset(gap,0,sizeof(gap));que.push(ee);dis[ee]=0;while(!que.empty()){u=que.front();que.pop();gap[dis[u]]++;for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v;if(dis[v]==-1){que.push(v);dis[v]=dis[u]+1;}}}return;
}int isap()
{int j,u,v,w,flow,minn,ans;bfs();memcpy(cur,first,sizeof(first));memset(pre,-1,sizeof(pre));u=ss,flow=N,ans=0;while(dis[ss]<num){int &i=cur[u];for(;i!=-1;i=edge[i].next){v=edge[i].v,w=edge[i].w;if(dis[v]+1==dis[u]&&w>0){pre[v]=i;u=v,flow=min(flow,w);if(u==ee){while(u!=ss){edge[pre[u]].w-=flow;edge[pre[u]^1].w+=flow;u=edge[pre[u]^1].v;}ans+=flow,flow=N;}break;}}if(i==-1){if(--gap[dis[u]]==0) break;cur[u]=first[u];minn=num-1;for(j=first[u];j!=-1;j=edge[j].next){v=edge[j].v,w=edge[j].w;if(w>0){minn=min(minn,dis[v]);}}dis[u]=minn+1;gap[dis[u]]++;if(u!=ss){u=edge[pre[u]^1].v;}}}return ans;
}int main()
{int gou[4010];int i,j,u,v,w,id,k;scanf("%d%d%d",&n1,&n2,&m);memset(first,-1,sizeof(first));memset(degree,0,sizeof(degree));num=0;for(i=1;i<=m;i++){scanf("%d%d",&u,&v);addedge(u,n1+v,1,i);addedge(n1+v,u,0,0);degree[u]++,degree[n1+v]++;}k=N;for(i=1;i<=n1+n2;i++){k=min(k,degree[i]);}ss=n1+n2+1,ee=n1+n2+2;for(i=1;i<=n1;i++){addedge(ss,i,degree[i]-k,0);addedge(i,ss,0,0);}for(i=n1+1;i<=n1+n2;i++){gou[i]=num;addedge(i,ee,degree[i]-k,0);addedge(ee,i,0,0);}num=n1+n2+2;for(i=k;i>=1;i--){isap();ans[i].clear();for(u=1;u<=n1;u++){for(j=first[u];j!=-1;j=edge[j].next){v=edge[j].v;if(v!=ss){w=edge[j].w,id=edge[j].id;if(w) ans[i].push_back(id);}}}for(j=first[ss];j!=-1;j=edge[j].next){edge[j].w++;}for(u=n1+1;u<=n1+n2;u++){edge[gou[u]].w++;}}for(i=0;i<=k;i++){printf("%d",ans[i].size());for(j=0;j<ans[i].size();j++){printf(" %d",ans[i][j]);}printf("\n");}return 0;
}
这篇关于Minimal k-covering CodeForces - 976F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
