首页 > 代码库 > BZOJ 3438 小M的作物 最小割
BZOJ 3438 小M的作物 最小割
题目大意:给出一些作物,这些作物要不就是种在A地,要不就是种在B地,有些作物种在一起会有额外收成。问最多可以获得多少收成。
思路:最小割模型,与S集相连的点都是种在A地的点,与T集相连的点都是种在B地的点。中间随便乱搞一下,总之最后就是所有收成-最大流就是最后答案。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 3010 #define MAXE 5000010 #define S 0 #define T (MAX - 1) #define INF 0x3f3f3f3f using namespace std; struct MaxFlow{ int head[MAX],total; int next[MAXE],aim[MAXE],flow[MAXE]; int deep[MAX]; MaxFlow() { total = 1; } void Add(int x,int y,int f) { next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; } void Insert(int x,int y,int f) { Add(x,y,f); Add(y,x,0); } bool BFS() { static queue<int> q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) if(flow[i] && !deep[aim[i]]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x,int f) { if(x == T) return f; int temp = f; for(int i = head[x]; i; i = next[i]) if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) { int away = Dinic(aim[i],min(temp,flow[i])); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp; } }solver; int cnt,pos; int asks,ans; int main() { cin >> cnt; pos = cnt; for(int x,i = 1; i <= cnt; ++i) { scanf("%d",&x); ans += x; solver.Insert(S,i,x); } for(int x,i = 1; i <= cnt; ++i) { scanf("%d",&x); ans += x; solver.Insert(i,T,x); } cin >> asks; for(int num,x,i = 1; i <= asks; ++i) { scanf("%d",&num); pos += 2; scanf("%d",&x); solver.Insert(S,pos - 1,x); ans += x; scanf("%d",&x); solver.Insert(pos,T,x); ans += x; for(int j = 1; j <= num; ++j) { scanf("%d",&x); solver.Insert(pos - 1,x,INF); solver.Insert(x,pos,INF); } } int max_flow = 0; while(solver.BFS()) max_flow += solver.Dinic(S,INF); cout << ans - max_flow << endl; return 0; }
BZOJ 3438 小M的作物 最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。