首页 > 代码库 > HDU 4292:Food(最大流)
HDU 4292:Food(最大流)
http://acm.hdu.edu.cn/showproblem.php?pid=4292
题意:和奶牛一题差不多,只不过每种食物可以有多种。
思路:因为食物多种,所以源点和汇点的容量要改下。还有Dinic又TLE了,用ISAP过。
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <queue> #include <vector> #include <map> #include <set> using namespace std; #define INF 0x3f3f3f3f #define N 910 typedef long long LL; typedef long long LL; struct Edge { int v, cap, nxt; Edge () {} Edge (int v, int cap, int nxt) : v(v), cap(cap), nxt(nxt) {} }edge[N*N]; int tot, cur[N], dis[N], pre[N], head[N], gap[N], S, T; void Add(int u, int v, int cap) { edge[tot] = Edge(v, cap, head[u]); head[u] = tot++; edge[tot] = Edge(u, 0, head[v]); head[v] = tot++; } void BFS() { queue<int> que; while(!que.empty()) que.pop(); memset(dis, -1, sizeof(dis)); memset(gap, 0, sizeof(gap)); dis[T] = 0; gap[0]++; que.push(T); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].v; if(dis[v] == -1) continue; dis[v] = dis[u] + 1; gap[dis[v]]++; que.push(v); } } } int ISAP(int n) { memcpy(cur, head, sizeof(cur)); BFS(); int u = pre[S] = S, ans = 0, i; while(dis[S] < n) { if(u == T) { int flow = INF, index; for(int i = S; i != T; i = edge[cur[i]].v) { Edge& e = edge[cur[i]]; if(e.cap < flow) { flow = e.cap; index = i; } } for(int i = S; i != T; i = edge[cur[i]].v) { edge[cur[i]].cap -= flow; edge[cur[i]^1].cap += flow; } ans += flow; u = index; } for(i = cur[u]; ~i; i = edge[i].nxt) if(dis[edge[i].v] == dis[u] - 1 && edge[i].cap > 0) break; if(~i) { cur[u] = i; pre[edge[i].v] = u; u = edge[i].v; } else { int md = n; if(--gap[dis[u]] == 0) break; for(int i = head[u]; ~i; i = edge[i].nxt) { if(md > dis[edge[i].v] && edge[i].cap > 0) { md = dis[edge[i].v]; cur[u] = i; } } ++gap[dis[u] = md + 1]; u = pre[u]; } } return ans; } int main() { int n, f, d; while(~scanf("%d%d%d", &n, &f, &d)) { S = 0, T = 2 * n + f + d + 1; memset(head, -1, sizeof(head)); tot = 0; int a; char s[500]; for(int i = 1; i <= f; i++) { scanf("%d", &a); Add(S, i + 2 * n, a); } for(int i = 1; i <= d; i++) { scanf("%d", &a); Add(i + 2 * n + f, T, a); } for(int i = 1; i <= n; i++) { Add(i, i + n, 1); scanf("%s", s + 1); for(int j = 1; j <= f; j++) { if(s[j] == ‘Y‘) { Add(2 * n + j, i, 1); } } } for(int i = 1; i <= n; i++) { scanf("%s", s + 1); for(int j = 1; j <= d; j++) { if(s[j] == ‘Y‘) { Add(i + n, 2 * n + j + f, 1); } } } printf("%d\n", ISAP(T + 1)); } return 0; }
HDU 4292:Food(最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。