HDU 3605:Escape(最大流+状态压缩)

时间:2023-03-08 16:07:22
HDU 3605:Escape(最大流+状态压缩)

http://acm.hdu.edu.cn/showproblem.php?pid=3605

题意:有n个人要去到m个星球上,这n个人每个人对m个星球有一个选择,即愿不愿意去,“Y”or"N"。问是否可以全部人都顺利到自己想去的星球。

思路:很“有趣”的一道题目,n是1e5的大小,m只有10,没有想到状态压缩,看到n这么大肯定超时还是强行写了一波,于是RE(TLE)。想了挺久还是不会。看别人的思路是说二进制状态压缩。看到这就想到m只有10,于是可以分成1<<10 = 1024种情况,代表有这个选择,就相当于把人从1e5的大小强行压到1e3了。然后源点->选择->星球->汇点这样的图就建好了。源点->选择的边权是每种选择的人数,选择->星球的边权是对于每种选择,选择了这个星球的人数,星球->汇点的边权是星球容纳的人数。就酱了。Mark。

 #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 1200
#define NUM 1024
typedef long long LL;
struct Edge {
int v, nxt, cap;
Edge () {}
Edge (int v, int nxt, int cap) : v(v), nxt(nxt), cap(cap) {}
}edge[N*N*];
int tot, head[N], cur[N], pre[N], dis[N], gap[N], S, T, tol[]; void Add(int u, int v, int cap) {
edge[tot] = Edge(v, head[u], cap); head[u] = tot++;
edge[tot] = Edge(u, head[v], ); head[v] = tot++;
} void BFS() {
memset(dis, -, sizeof(dis));
memset(gap, , sizeof(gap));
queue<int> que;
while(!que.empty()) que.pop();
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) {
Edge &e = edge[i];
if(dis[e.v] == -) continue;
dis[e.v] = dis[u] + ;
que.push(e.v);
gap[dis[e.v]]++;
}
}
} int ISAP(int n) {
BFS();
memcpy(cur, head, sizeof(cur));
int ans = , i, u = pre[S] = S;
while(dis[S] < n) {
if(u == T) {
int index, flow = INF;
for(i = S; i != T; i = edge[cur[i]].v)
if(flow > edge[cur[i]].cap)
flow = edge[cur[i]].cap, index = i;
for(i = S; i != T; i = edge[cur[i]].v)
edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;
u = index;
ans += flow;
}
// puts("AAAA");
for(i = cur[u]; ~i; i = edge[i].nxt)
if(dis[edge[i].v] == dis[u] - && edge[i].cap > ) break;
// puts("BBBB");
if(~i) {
cur[u] = i; pre[edge[i].v] = u; u = edge[i].v;
} else {
if(--gap[dis[u]] == ) break;
int md = n;
for(i = head[u]; ~i; i = edge[i].nxt)
if(dis[edge[i].v] < md && edge[i].cap > ) cur[u] = i, md = dis[edge[i].v];
// puts("CCCC");
++gap[dis[u] = md + ];
// puts("ISAP");
u = pre[u];
}
}
return ans;
} int main() {
int n, m;
while(~scanf("%d%d", &n, &m)) {
memset(head, -, sizeof(head));
tot = ; S = NUM + m + , T = NUM + m + ;
int a; int dp[N][], s[N];
memset(dp, , sizeof(dp));
memset(s, , sizeof(s));
for(int i = ; i <= n; i++) {
int ss = ;
for(int j = ; j <= m; j++) {
scanf("%d", &a);
if(a) ss |= (a << (j - ));
}
s[ss]++;
for(int j = ; j <= m; j++) {
if(ss & ( << (j-))) dp[ss][j]++;
}
}
for(int i = ; i <= m; i++) scanf("%d", &tol[i]);
for(int i = ; i <= ; i++) {
Add(S, i, s[i]);
for(int j = ; j <= m; j++) {
if(dp[i][j]) {
Add(i, NUM + j, dp[i][j]);
}
}
}
for(int i = ; i <= m; i++) Add(NUM + i, T, tol[i]);
int ans = ISAP(T + );
if(ans == n) puts("YES");
else puts("NO"); }
return ;
}