题目大意
直接盗链…
解题报告
老样子,附赠样例:
Input:
3 3
5 1 0 1
10 1 0 0
15 2 0 0 0 1
-10 0
90 0
-20 2 1 0 1 1
80 1 2 1
10 1 2 1
40 0
Output:
125
有消耗有收入,有相互间的牵制关系,这实际上是一道最小割的题目。
设源点为S, 汇点为T,源点集为s,汇点集为t。
每个植物看成一个点,如果点u在s中,那么看做点u被消灭了。
对每个植物u,如果权值为正,那么连接一条S->T的权值为植物权值的边。
否然连接一条u->T的权值为植物权值的绝对值的边。
搞搞就发现所有正权植物权值和减去这么跑最小割的答案就是答案。
那么怎么进行选择的约束呢?
假设如果有一条u->v的权值为INF的边,那么u和v必然要么在最小割后被分配在同一个集合里,要么v在t中而u在s中。
考虑如果植物u保护了植物v,就可以用上面的方法进行约束,连接一条v->u的INF边,那么u可以被吃掉(在s中)或不被吃掉(不在s中),而只有u在s中时v才能在s中(也被吃掉)
然后会有植物相互保护形成了一个“无敌环”的情况,这个环明显不能被最小割切开,我们为了不让这个环出现在s中,可以在环上随便找个点x连接一条x->T的INF边。原理很简单我就不多说了。
接下来上代码
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
const int INF = 0x3f3f3f3f;
const int MAXN = 35;
using std :: min;
using std :: max;
namespace isap {
const int MAXD = MAXN*MAXN+100;
const int MAXE = 500000;
struct Node {
int v, w, bk, nxt;
} d[MAXE];
int head[MAXD], etot;
inline int addEdge (int a, int b, int c) {
etot ++;
d[etot].v = b;
d[etot].w = c;
d[etot].bk = etot + 1;
d[etot].nxt = head[a];
head[a] = etot;
etot ++;
d[etot].v = a;
d[etot].w = 0;
d[etot].bk = etot - 1;
d[etot].nxt = head[b];
head[b] = etot;
return etot;
}
int dis[MAXD], vd[MAXD];
int seq[MAXD*2];
void bfs (int s) {
int lef, rig;
memset(dis, 0x3f, sizeof dis);
dis[seq[lef = rig = 0] = s] = 0;
while(lef <= rig) {
int u = seq[lef++];
for(int e = head[u]; e; e = d[e].nxt)
if(dis[d[e].v] > dis[u] + 1) {
dis[d[e].v] = dis[u] + 1;
seq[++rig] = d[e].v;
}
}
}
int S, T, N;
int dfs (int u, int val) {
if(u == T) return val;
int rest = val;
for(int e = head[u]; e; e = d[e].nxt)
if(d[e].w && dis[d[e].v]+1 == dis[u]) {
int t = dfs(d[e].v, min(rest, d[e].w));
rest -= t;
d[e].w -= t;
d[d[e].bk].w += t;
if(!rest) return val;
if(dis[S] >= N) return val - rest;
}
if(val == rest) {
if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
dis[u] = N;
for(int e = head[u]; e; e = d[e].nxt)
if(d[e].w) dis[u] = min(dis[u], dis[d[e].v] + 1);
++ vd[dis[u]];
return 0;
}
return val - rest;
}
int sap (int s, int t, int n) {
S = s, T = t, N = n;
bfs(T);
for(int i = 1; i<=N; i++)
if(dis[i] <= N) vd[dis[i]] ++;
int flow = 0;
while(dis[S] < N) flow += dfs(S, INF);
return flow;
}
}
struct Digraph {
struct Node {
int v, nxt;
} d[500000];
int head[MAXN*MAXN], etot;
Digraph () {etot = 0;}
inline int addEdge (int a, int b) {
etot ++;
d[etot].v = b;
d[etot].nxt = head[a];
head[a] = etot;
return etot;
}
Node & operator [] (int index) {
return d[index];
}
};
Digraph inp;
inline int getInt () {
int ret; char ch; bool f = false;
while((ch = getchar()) < '0' || ch > '9') f ^= (ch == '-');
ret = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9') ret *= 10, ret += ch - '0';
ungetc(ch, stdin);
return f ? -ret : ret;
}
int N, M, vtot, colr;
int val[MAXN*MAXN];
int tag[MAXN*MAXN];
int cir[MAXN*MAXN], ctot;
void dfs(int u) {
if(tag[u]) {
if(tag[u] == colr) cir[++ctot] = u;
return ;
}
tag[u] = colr;
for(int e = inp.head[u]; e; e = inp[e].nxt)
dfs(inp[e].v);
tag[u] = -1;
}
inline int getVid(int row, int col) {
return (row-1)*M+col;
}
int main () {
int sum = 0, x, y;
N = getInt(), M = getInt();
for(int i = 1; i <= N; i++)
for(int j = 1; j<=M; j++) {
val[getVid(i, j)] = getInt();
int rad = getInt(), id = getVid(i, j);
if(val[id] > 0) sum += val[id];
while(rad --) {
x = getInt()+1, y = getInt()+1;
inp.addEdge(getVid(x, y), id);
}
if(j!=M) inp.addEdge(id, getVid(i, j+1));
}
vtot = getVid(N, M);
for(int i = 1; i<=vtot; i++)
if(!tag[i]) colr++, dfs(i);
int S = 1, T = S + vtot + 1;
for(int i = 1; i<=ctot; i++)
isap :: addEdge(S + cir[i], T, INF);
for(int u = 1; u<=vtot; u++) {
for(int e = inp.head[u]; e; e = inp[e].nxt)
if(inp[e].v != u) isap :: addEdge(S + u, S + inp[e].v, INF);
if(val[u] > 0) isap :: addEdge(S, S + u, val[u]);
else isap :: addEdge(S + u, T, -val[u]);
}
sum -= isap :: sap(S, T, T);
printf("%d\n", sum);
}
Join the discussion