HDU 3605——Escape状態圧縮+最大ストリーム
2180 ワード
原題:http://acm.hdu.edu.cn/showproblem.php?pid=3605
#include
#include
#include
#include
#include
#include
#include
#define inf 1e9
using namespace std;
const int maxn = 1500;
const int maxm = 15000;
int n, m;
int num_nodes;
int can[15];
int tmp[maxn];
struct Edge
{
int from, to, flow, cap;
}edge[maxm*2];
vectorG[maxn];
int edgenum;
void add(int u, int v, int c)
{
edge[edgenum].from = u;
edge[edgenum].to = v;
edge[edgenum].flow = 0;
edge[edgenum].cap = c;
edgenum++;
edge[edgenum].from = v;
edge[edgenum].to = u;
edge[edgenum].flow = 0;
edge[edgenum].cap = 0;
edgenum++;
G[u].push_back(edgenum-2);
G[v].push_back(edgenum-1);
}
int deep[maxn];
bool vis[maxn];
void BFS(int s, int t)
{
queueQ;
memset(vis, false, sizeof vis);
Q.push(t);
vis[t] = true;
deep[t] = 0;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = 0;i e.flow && deep[begin] == deep[e.to] + 1)
{
front[e.to] = G[begin][i];
cur[begin] = i;
flag = true;
begin = e.to;
break;
}
}
if(!flag)
{
int k = num_nodes-1;
for(int i = 0;i e.flow)
k = min(k, deep[e.to]);
}
if(--gap[deep[begin]] == 0) break;
gap[deep[begin] = k+1]++;
cur[begin] = 0;
if(begin != s)
begin = edge[front[begin]].from;
}
}
return flow;
}
void init()
{
for(int i = 0;i