首页 > 代码库 > 【codeforces 103E】 Buying Sets
【codeforces 103E】 Buying Sets
http://codeforces.com/problemset/problem/103/E (题目链接)
题意
给出$n$个数,每个数与一个集合相关联。从其中选出最小的若干个数,选出的数的个数与这些数相关联的集合的并集大小相等。
Solution
因为保证了有完全匹配,所以跑出一个完全匹配,这样我们可以知道,如果选了某一个数,必须要选的其它数是哪些。但是问题是随着匹配的变化,这种关系会不会发生变化呢?是不会的。画画图,你会发现无论如何连边,最后都是从一个点走出去经过那些点再从一条非匹配边走回来。
所以,这很显然就是一个最小权闭合子图了,套上模板就可以AC了。
细节
边数$n^2$
代码
#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#define LL long long#define inf (1ll<<30)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=500;int head[maxn],cnt=1,ans,clk,S,T,n,a[maxn],vis[maxn],p[maxn];vector<int> v[maxn];struct edge {int to,next,w;}e[maxn*maxn*2];namespace Dinic { int d[maxn]; void link(int u,int v,int w) { e[++cnt]=(edge){v,head[u],w};head[u]=cnt; e[++cnt]=(edge){u,head[v],0};head[v]=cnt; } bool bfs() { for (int i=S;i<=T;i++) d[i]=-1; queue<int> q;q.push(S);d[S]=0; while (!q.empty()) { int x=q.front();q.pop(); for (int i=head[x];i;i=e[i].next) if (e[i].w && d[e[i].to]<0) d[e[i].to]=d[x]+1,q.push(e[i].to); } return d[T]>0; } int dfs(int x,int f) { if (f==0 || x==T) return f; int w,used=0; for (int i=head[x];i;i=e[i].next) if (e[i].w && d[e[i].to]==d[x]+1) { w=dfs(e[i].to,min(e[i].w,f-used)); used+=w,e[i].w-=w,e[i^1].w+=w; if (used==f) return used; } if (!used) d[x]=-1; return used; } int main() { int flow=0; while (bfs()) flow+=dfs(S,inf); return flow; }}using namespace Dinic;bool match(int x) { for (int i=0,j=v[x].size();i<j;i++) { if (vis[v[x][i]]==clk) continue; vis[v[x][i]]=clk; if (!p[v[x][i]] || match(p[v[x][i]])) {p[v[x][i]]=x;return 1;} } return 0;}int main() { scanf("%d",&n); for (int x,y,i=1;i<=n;i++) { scanf("%d",&y); for (int j=1;j<=y;j++) scanf("%d",&x),v[i].push_back(x); } for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) ++clk,match(i); S=0,T=n+1; for (int i=1;i<=n;i++) for (int j=0,k=v[i].size();j<k;j++) link(i,p[v[i][j]],inf); for (int i=1;i<=n;i++) { if (a[i]<0) link(S,i,-a[i]),ans-=a[i]; else link(i,T,a[i]); } ans-=Dinic::main(); printf("%d",-ans); return 0;}
【codeforces 103E】 Buying Sets
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。