文章目錄

• 題目描述
• • 數據范圍
• 解析
• 代碼

題目描述

尼克在一家養豬場工作，這家養豬場共有$M$間鎖起來的豬舍，由于豬舍的鑰匙都給了客戶，所以尼克沒有辦法打開這些豬舍。有$N$個客戶從早上開始一個接一個來購買生豬，他們到達后首先用手中的鑰匙打開他所能打開的全部豬舍，然后從中選取他要買的豬，尼克可以在此期間將打開的豬舍中的豬調整到其它開著的豬舍中，每個豬舍能存放的豬的數量是沒有任何限制的。買完豬后客戶會將他打開的豬舍關上。

好在尼克事先知道每位客戶手中有哪些鑰匙，要買多少豬，以及客戶到來的先后次序。請你寫一個程序，幫助尼克求出最多能賣出多少頭豬。

數據范圍

$M<=1000,N<=100$

解析

關鍵在于建圖的方法
直觀感覺是把客戶和他能開的豬圈連不限流的雙向邊，但是會出現時光倒流的bug
我的解決辦法是只讓豬圈和顧客連邊，然后顧客按先后順序暴力判斷豬圈有交集則連一條單向不限流的邊
但這樣的理論最差邊數是$n^2$，再加上點數為m,1e3級別，最差情況下 $m^2?n^2$似乎無法通過
然而實際上59ms跑的飛快
所以網絡流一定要敢寫
一個比較巧妙的建圖方式是把豬圈x連向第一個打開x的顧客，以后再有打開x的顧客k，就從上一個打開x的顧客lst連一條到k的不限流的邊
很巧妙
不過邊數最差似乎還變成了n*m,更差了…

代碼

（因為似乎沒有實質的優化，所以還是暴力建圖的碼）

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1205; const int M=1e9; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,s,t,num; struct node{int to,nxt,cap; }p[N*N*2]; int fi[N],cnt; void addline(int x,int y,int cap){p[++cnt]=(node){y,fi[x],cap};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0};fi[y]=cnt; } int col[N],cur[N]; queue<int>q; int bfs(){memset(col,0,sizeof(col));col[s]=1;q.push(s);while(!q.empty()){int now=q.front();q.pop();for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(col[to]||!p[i].cap) continue;col[to]=col[now]+1;q.push(to);}}return col[t]; } int dfs(int x,int lim){if(x==t||!lim) return lim;int res=0;for(int &i=cur[x];~i&&lim;i=p[i].nxt){int to=p[i].to;if(!p[i].cap||col[to]!=col[x]+1) continue;int add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(!res) col[x]=-1;return res; } int dinic(){int tot=0;while(bfs()){while(int tmp=dfs(1,2e9)) tot+=tmp;}return tot; } int key[106][1005],tot[106],need[106],id[106]; bool vis[1005]; bool ok(int x,int y){memset(vis,0,sizeof(vis));for(int i=1;i<=tot[x];i++) vis[key[x][i]]=1;for(int i=1;i<=tot[y];i++) if(vis[key[y][i]]) return true;return false; } int main(){memset(fi,-1,sizeof(fi));cnt=-1;m=read();n=read();s=++num;t=++num;for(int i=1;i<=m;i++){int x=read();++num;addline(s,num,x);}for(int i=1;i<=n;i++){tot[i]=read();id[i]=++num;for(int j=1;j<=tot[i];j++){key[i][j]=read();addline(key[i][j]+2,num,2e9);}need[i]=read();addline(num,t,need[i]);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(ok(i,j)) addline(id[i],id[j],2e9);}}printf("%d",dinic());return 0; }

總結

以上是生活随笔為你收集整理的YBTOJ：卖猪问题（网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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