首页 > 分享 > [POJ 1149]PIGS

[POJ 1149]PIGS

萌宠菠菠乐园
2024-12-03 06:09

题目链接

这是一道网络流建图好题。

这个题最大的难点就在于“调换”操作。如果没有调换操作显然这是一道网络流棵题。但是加上调换操作就麻烦多了。
考虑第 i" role="presentation">i 位顾客，他能够从 p,q" role="presentation">p,q 猪圈购买猪，那他之后的第 j" role="presentation">j 位顾客如果也能从 p" role="presentation">p 猪圈购买猪的话，那这位顾客也可以从 q" role="presentation">q 猪圈购买猪，因为如果他需要，在第 i" role="presentation">i 位顾客购买时就已经调整好了。本着这个原则，我们来建图。

建立超级源点S、T。 S向每个顾客连流量为1的边（显然）如果某个猪圈第一次被一位顾客i" role="presentation">i访问，则从i" role="presentation">i向T连流量为该猪圈初始猪数目的边如果某个猪圈被解锁过了，则维护该猪圈最后一个解锁它的顾客编号，当前顾客向那个顾客连流量为inf的边。
这样就得到一张图了。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #include<vector> #include<set> #include<map> #include<string> #include<iostream> #include<queue> #include<cctype> using namespace std; #define A(x) cout << #x << " " << x << endl; #define AA(x,y) cout << #x << " " << x << #y << " " << y << endl; #define B cout << "Break" << endl; #define ll long long int read() {char c = getchar();int x = 0,f = 1;while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}while(isdigit(c)){x = x * 10 + c - '0';c = getchar();}return f * x; } #define inf 1000000000 #define N 3010 #define M 100100 int head[N],nxt[M],to[M],val[M]; int ecnt = 1,tot,n,m; void Add(int u,int v,int w) { nxt[++ecnt] = head[u]; head[u] = ecnt; to[ecnt] = v; val[ecnt] = w; } void add(int u,int v,int w) { Add(u,v,w); Add(v,u,0); } int s,t; int cur[N],dep[N]; bool bfs() { queue<int>q; while(!q.empty()) q.pop(); memset(dep,-1,sizeof(dep)); dep[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u];i;i = nxt[i]) { int v = to[i]; if(dep[v] == -1 && val[i] > 0) { dep[v] = dep[u] + 1; q.push(v); } } } return dep[t] != -1; } int dfs(int u,int flow) { if(u == t) return flow; int used = 0,tmp = 0; for(int &i = cur[u];i;i = nxt[i]) { int v = to[i]; if(dep[v] == dep[u] + 1 && val[i] > 0) { tmp = dfs(v,min(val[i],flow - used)); if(tmp > 0) { val[i] -= tmp; used += tmp; val[i ^ 1] += tmp; if(used == flow) return used; } } } if(used != flow) dep[u] = -1; return used; } int maxflow() { int tmp,ans = 0; while(bfs()) { memcpy(cur,head,sizeof(head)); while((tmp = dfs(s,inf))) ans += tmp; } return ans; } int last[N],pig[N]; int main() { n = read(),m = read(); for(int i = 1;i <= n;i++) pig[i] = read(); s = 0,t = n + 1; for(int i = 1;i <= m;i++) { int qwq = read(); for(int j = 1;j <= qwq;j++) { int go = read(); if(!last[go]) add(i,t,pig[go]); else add(i,last[go],inf); last[go] = i; } int nd = read(); add(s,i,nd); } printf("%dn",maxflow()); }