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, , head[v]); head[v] = tot++;
} void BFS() {
queue<int> que;
while(!que.empty()) que.pop();
memset(dis, -, sizeof(dis));
memset(gap, , sizeof(gap));
dis[T] = ; gap[]++; 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] == -) continue;
dis[v] = dis[u] + ;
gap[dis[v]]++;
que.push(v);
}
}
} int ISAP(int n) {
memcpy(cur, head, sizeof(cur));
BFS();
int u = pre[S] = S, ans = , 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]^].cap += flow;
}
ans += flow; u = index;
}
for(i = cur[u]; ~i; i = edge[i].nxt)
if(dis[edge[i].v] == dis[u] - && edge[i].cap > )
break;
if(~i) {
cur[u] = i;
pre[edge[i].v] = u;
u = edge[i].v;
} else {
int md = n;
if(--gap[dis[u]] == ) break;
for(int i = head[u]; ~i; i = edge[i].nxt) {
if(md > dis[edge[i].v] && edge[i].cap > ) {
md = dis[edge[i].v]; cur[u] = i;
}
}
++gap[dis[u] = md + ];
u = pre[u];
}
}
return ans;
} int main() {
int n, f, d;
while(~scanf("%d%d%d", &n, &f, &d)) {
S = , T = * n + f + d + ;
memset(head, -, sizeof(head));
tot = ; int a; char s[];
for(int i = ; i <= f; i++) {
scanf("%d", &a);
Add(S, i + * n, a);
}
for(int i = ; i <= d; i++) {
scanf("%d", &a);
Add(i + * n + f, T, a);
}
for(int i = ; i <= n; i++) {
Add(i, i + n, );
scanf("%s", s + );
for(int j = ; j <= f; j++) {
if(s[j] == 'Y') {
Add( * n + j, i, );
}
}
}
for(int i = ; i <= n; i++) {
scanf("%s", s + );
for(int j = ; j <= d; j++) {
if(s[j] == 'Y') {
Add(i + n, * n + j + f, );
}
}
}
printf("%d\n", ISAP(T + ));
}
return ;
}
上一篇:leetcode--Maximum Subarray


下一篇:hdu 3572 Escape 网络流