题目描述：
你有$m$个猪圈，有$n$个人会来买猪。其中每个人都会打开某几个猪圈的门，你可以在他们买完后移动猪的位置。
每人有买猪数量的上界，求最多买多少头猪。
题解：
最大流。
神奇建图：
- 源点向每个猪圈的第一个人连边，容量为这个猪圈的猪的数量。
- 若$x$访问过猪圈$i$后$y$是第一个访问$i$的人，那么建$x->y$，容量$inf$。
- 每个人向汇点建边，容量为买猪上界。
正确性显然。
然后跑最大流就好了。
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int M = 1050;
const int N = 150;
const int inf = 0x3f3f3f3f;
const ll Inf = 0x3f3f3f3f3f3f3f3fll;
template<typename T>
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
x = f*c;
}
int m,n,pos[M],S=0,T,hed[N],cnt=1;
ll w[M];
struct EG
{
int to,nxt;
ll fl;
}e[200050];
void ae(int f,int t,ll fl)
{
e[++cnt].to = t;
e[cnt].nxt = hed[f];
e[cnt].fl = fl;
hed[f] = cnt;
}
void AE(int f,int t,ll fl)
{
ae(f,t,fl);
ae(t,f,0);
}
int cur[N],dep[N];
bool vis[N];
bool bfs()
{
queue<int>q;
memcpy(cur,hed,sizeof(cur));
memset(dep,0x3f,sizeof(dep));
dep[S] = 0,vis[S] = 1;q.push(S);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int j=hed[u];j;j=e[j].nxt)
{
int to = e[j].to;
if(e[j].fl&&dep[to]>dep[u]+1)
{
dep[to] = dep[u]+1;
if(!vis[to])vis[to]=1,q.push(to);
}
}
vis[u] = 0;
}
return dep[T]!=inf;
}
ll dfs(int u,ll lim)
{
if(u==T||!lim)return lim;
ll fl = 0,f;
for(int j=cur[u];j;j=e[j].nxt)
{
cur[u] = j;
int to = e[j].to;
if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].fl))))
{
lim-=f,fl+=f;
e[j].fl-=f,e[j^1].fl+=f;
if(!lim)break;
}
}
return fl;
}
ll dinic()
{
ll ret = 0;
while(bfs())ret+=dfs(S,Inf);
return ret;
}
int main()
{
// freopen("tt.in","r",stdin);
read(m),read(n);
T = n+1;
for(int i=1;i<=m;i++)
read(w[i]);
ll k;
for(int l,r,i=1;i<=n;i++)
{
read(l);
while(l--)
{
read(r);
if(!pos[r])AE(S,i,w[r]);
else AE(pos[r],i,Inf);
pos[r] = i;
}
read(k);
AE(i,T,k);
}
printf("%lld\n",dinic());
return 0;
}
View Code