正題

題目鏈接:http://www.51nod.com/Challenge/Problem.html#problemId=1551

---

題目大意

$n$個集合，$n$個物品，每個集合有一些物品，一個價錢。滿足任意$k$個集合都有$k$種不同的物品。

要求一個最低的價格來購買集合且購買集合數等于里面不同物品數。

---

解題思路

這個條件根據$hall$定理可以證明如果一個集合對應一個物品則可以找到完全匹配。

那么也就是對于每個集合可以對應一個唯一的物品，每個一個物品也可以對應一個唯一的集合。

那么如果一個集合中有其他的物品，那么這個其他的物品所對應的集合也要選擇，這樣就可以用最大權閉合圖來解決這個問題。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1210,inf=2147483647; queue<int> q; struct node{int to,next,w; }; int n,ans,d[N]; struct New_Flow{node a[N*200];int s,t,tot=1,ls[N],dep[N];void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;return;}bool bfs(){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0;}int dinic(int x,int flow){if(x==t)return flow;int rest=0,k;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return flow;}if(!rest)dep[x]=0;return rest;}int net_flow(){int ans=0;while(bfs())ans+=dinic(s,inf);return ans;} }p,nf; int main() {scanf("%d",&n);p.s=2*n+1;p.t=p.s+1;for(int i=1;i<=n;i++){int k,x;scanf("%d",&k);p.addl(p.s,i,1);for(int j=1;j<=k;j++)scanf("%d",&x),p.addl(i,x+n,1);p.addl(i+n,p.t,1);}p.net_flow();for(int x=1;x<=n;x++)for(int i=p.ls[x];i;i=p.a[i].next){int y=p.a[i].to;if(!p.a[i].w&&y>n&&y<=2*n){d[y-n]=x;break;}}for(int x=1;x<=n;x++){for(int i=p.ls[x];i;i=p.a[i].next){int y=p.a[i].to;if(p.a[i].w&&y>n&&y<=2*n)nf.addl(x,d[y-n],inf);}}nf.s=n+1;nf.t=n+2;for(int i=1;i<=n;i++){int x;scanf("%d",&x);x=-x;if(x<0)nf.addl(i,nf.t,-x);else nf.addl(nf.s,i,x),ans+=x;}printf("%d\n",nf.net_flow()-ans);return 0; }

總結

以上是生活随笔為你收集整理的51nod1551-集合交易【hall定理,最大权闭合图,网络流】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。