i 位顾客,他能够从 p,q" role="presentation">p,q 猪圈购买猪,那他之后的第 j" role="presentation">j 位顾客如果也能从 p" role="presen" />
首页 > 分享 > [POJ 1149]PIGS

[POJ 1149]PIGS

题目链接

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

这个题最大的难点就在于“调换”操作。如果没有调换操作显然这是一道网络流棵题。但是加上调换操作就麻烦多了。
考虑第 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()); }

相关知识

poj 3094 Quicksum
云南农业大学动物科学技术学院
美妇女养40头宠物猪惹邻居不满
美国妇女养40头宠物猪 政府勒令为猪找新家
高纤维日粮对猪营养和代谢的影响综述
双语 | 养宠物猪之前“好脏”,养宠物猪之后“真香”!
豚鼠寄生虫:枯萎病、蜱虫、跳蚤和虱子——症状、治疗和预防
茶杯猪
养宠物的好处:许多英国人依靠宠物来治疗抑郁症等心理疾病
为什么宠物猪更像狼而不是狗

网址: [POJ 1149]PIGS https://m.mcbbbk.com/newsview682489.html

所属分类:萌宠日常
上一篇: 原本娇小玲珑的宠物猪 养成了30
下一篇: 新一代QQ宠物—猪猪基本喂养指南