[vijos 生命之泉]最大费用流
From:
Solution:
和炸毁燃料库一样,参见
#include#include #include #include #include #include #include #include using namespace std;#define N 1005#define M 705#define oo 0x6fffffff#define nil (-1)struct { int w,c,to,next;} nod[N*4];bool inQ[N];int adj[N], d[N], fa[N], idx[N], now, S, T;void Init(int n){ now = 0; S = 0; T = n+2; for (int i = 0; i <= T; ++i) adj[i] = nil;}int NewNode(int u, int w, int c){ nod[now].to = u; nod[now].w = w; nod[now].c = c; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int w, int c){ int u1 = NewNode(v, w, c); int v1 = NewNode(u, -w, 0); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Spfa(int n){ for (int i = 0; i <= n; ++i) d[i] = -oo, fa[i] = nil, inQ[i] = false; queue Q; d[S] = 0; Q.push(S); inQ[S] = true; while ( !Q.empty() ){ int u = Q.front(); Q.pop(); inQ[u] = false; for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] < d[u] + nod[i].w ){ d[v] = d[u] + nod[i].w; fa[v] = u; idx[v] = i; if ( !inQ[v] ) inQ[v] = true, Q.push(v); } } } return d[T] != -oo;}int Argument(){ int cf = oo; for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c); for (int i = T; i != S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; } return d[T];}int MinCost_Flow(int n){ int ans = 0; while ( Spfa(n) ) ans += Argument(); return ans;}void RunTest(int n, int m, int k){ Init(n); for (int i = 0; i < m; ++i){ int a,b,w; scanf("%d%d%d", &a, &b, &w); AddEdge(a, b+1, w, 1); } for (int i = 1; i <= n; ++i) AddEdge(i, i+1, 0, oo); AddEdge(S, 1, 0, k); AddEdge(n+1, T, 0, k); printf("%d\n", MinCost_Flow(n+2));}int main(){ int n,m,k; while( scanf("%d%d%d", &n, &m, &k) != EOF ) RunTest(n,m,k); return 0;}
[vijos 餐巾纸引发的血案]带源汇的上下界费用流
From:
Solution:
和80人环游差不多, 可用带上下界的费用流撸过。但是这里的数据较弱, 把费用流的代码扔到大视野就TLE了, 需要优化。 建图如下:
1.源点连接i, 费用f, 容量为第i天的人数
2.拆点i为i和i+n, i+n连接i+2*n, 费用为0, 容量为第i天人数N, 表示第i天用完的毛巾最多有N条
3.把i+2*n处的点连接[i+a+1,n]和[i+b+1,n]两个范围内的点, 表示第i天用完的毛巾可以用在这两个范围内的天里面
4.把i+2*n处的点连接汇点T, 表示这天的流也可以不用做A或B消毒
5.上下界流的处理, 新增_S,_T...
#include#include #include #include #include #include #include #include using namespace std;#define N 410#define M 705#define oo 0x6fffffff#define nil (-1)struct { int w,c,to,next;} nod[N*N];bool inQ[N];int adj[N], d[N], fa[N], idx[N], in[N], now, S, T, _S, _T;void Init(int n){ now = 0; S = 0; T = 3*n+1; _S = 3*n+2; _T = 3*n+3; for (int i = 0; i <= _T; ++i) in[i] = 0, adj[i] = nil;}int NewNode(int u, int w, int c){ nod[now].to = u; nod[now].w = w; nod[now].c = c; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int w, int c){ int u1 = NewNode(v, w, c); int v1 = NewNode(u, -w, 0); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Spfa(int n){ for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil, inQ[i] = false; queue Q; d[_S] = 0; Q.push(_S); inQ[_S] = true; while ( !Q.empty() ){ int u = Q.front(); Q.pop(); inQ[u] = false; for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] > d[u] + nod[i].w ){ d[v] = d[u] + nod[i].w; fa[v] = u; idx[v] = i; if ( !inQ[v] ) inQ[v] = true, Q.push(v); } } } return d[_T] != oo;}int Argument(){ int cf = oo; for (int i = _T; i != _S; i = fa[i]) cf = min(cf, nod[idx[i]].c); for (int i = _T; i != _S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; } return cf*d[_T];}int MinCost_Flow(int n){ int ans = 0; while ( Spfa(n) ) ans += Argument(); return ans;}int main(){ int n,a,b,f,Fa,Fb; while( scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &Fa, &Fb) != EOF ){ Init(n); for (int i = 1; i <= n; ++i){ int dd = 0; scanf("%d", &dd); in[i] -= dd; in[i+n] += dd; AddEdge(S, i, f, dd); AddEdge(i+n, i+2*n, 0, dd); AddEdge(i+2*n, T, 0, dd); if ( i+a < n ){ for (int j = i+a+1; j <= n; ++j) AddEdge(i+n, j, Fa, oo); } if ( i+b < n ){ for (int j = i+b+1; j <= n; ++j) AddEdge(i+n, j, Fb, oo); } } for (int i = 1; i <= 2*n; ++i){ int dd = in[i]; if ( dd < 0 ) AddEdge(i, _T, 0, -dd); else if ( dd > 0 ) AddEdge(_S, i, 0, dd); } AddEdge(T, S, 0, oo); printf("%d\n", MinCost_Flow(3*n+3)); } return 0;}
[vijos 笨笨的洪水堵截]最小割
From:
Solution:
拆点, 容量为点的权值,所求最小割即为从S不可达T的最小代价。
#include#include #include #include #include #include #include #include using namespace std;#define N 115#define M 101#define oo 0x6fffffff#define nil (-1)struct { int c,to,next;} nod[N*N];int adj[N], d[N], fa[N], idx[N], maxflow, now, S, T;void Init(int n){ now = 0; S = 0; T = n; for (int i = 0; i <= n; ++i) adj[i] = nil;}int NewNode(int u, int c){ nod[now].to = u; nod[now].c = c; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int c){ int u1 = NewNode(v, c); int v1 = NewNode(u, 0); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Bfs(int n){ for (int i = 0; i <= n; ++i) d[i] = oo; queue Q; d[S] = 0; Q.push(S); while ( !Q.empty() ){ int u = Q.front(); Q.pop(); for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] == oo ){ d[v] = d[u] + 1; if ( v == T ) return true; Q.push(v); } } } return false;}int Dfs(int u){ if ( u != T ){ if ( d[u] != oo ){ for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] == d[u] + 1 ){ fa[v] = u; idx[v] = i; int r = Dfs(v); if ( r != nil && r != u ) return r; } } d[u] = oo; } } else { int cf = oo, r = fa[T]; for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c); for (int i = T; i != S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; if ( !nod[idx[i]].c ) r = fa[i]; } maxflow += cf; return r; } return nil;}int Dinic(int n){ maxflow = 0; while ( Bfs(n) ) Dfs(S); return maxflow;}int main(){ int n,m,ca; scanf("%d", &ca); while ( ca-- ){ scanf("%d%d", &n, &m); Init(2*n+3); int tot = 0; for (int i = 1; i < n; ++i){ int dd; scanf("%d", &dd); AddEdge(i+1, i+n+2, dd); tot += dd; } for (int i = 0; i < m; ++i){ int a,b; scanf("%d%d", &a, &b); AddEdge(a+n+2, b+1, oo); AddEdge(b+n+2, a+1, oo); } AddEdge(1, n+2, oo); AddEdge(n+1, 2*n+2, oo); AddEdge(S, 1, oo); AddEdge(n+1, T, oo); int ans = Dinic(2*n+3); if ( ans == 0 ) printf("Min!\n"); else if ( ans > tot ) printf("Max!\n"); else printf("%d\n", ans); } return 0;}
[vijos 植物大战僵尸]最大流
From:
Solution: 如果不能解所提题目, 那么尝试找一道与题目有关且更容易解决的问题。只保留条件的一部分, 丢弃其他, 那么未知量能确定到什么程度?
1.丢弃条件"攻击范围", 题目就变成在图中求一个最大权闭合图, 这是已经模型, 如何解是知道的, 是否能利用这个模型呢?
2.尝试丢弃条件"植物的分数", 题目就变成如何在矩阵中找到可以攻击的植物, 不难发现, 如果植物相互保护那么必然不可攻击, 对应图来说, 就是强联通分量一定不可攻击。另外, 僵尸从右往左移动, 也就是说如果(r,c)属于一个强联通分量, 那么(r,c-1)也不可攻击。于是, 只要求出强联通分量, 从右往左遍历, 就可以求出可以攻击的植物。
结合1,2, 通过2找到可以攻击的植物, 再用最大权闭合图模型求解即可。
#include#include #include #include #include #include #include #include using namespace std;#define N 605#define M 101#define oo 0x6fffffff#define nil (-1)struct { int c,to,next;} nod[N*N];stack sta;bool vis[N], inSta[N];int adj[N], d[N], fa[N], idx[N], low[N], scc[N], scc_cnt[N], a[N], t, sum, scc_num, maxflow, now, S, T;void Init(int n){ now = 0; S = n; T = n+1; for (int i = 0; i <= T; ++i) adj[i] = nil; while ( !sta.empty() ) sta.pop();}int NewNode(int u, int c){ nod[now].to = u; nod[now].c = c; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int c){ int u1 = NewNode(v, c); int v1 = NewNode(u, 0); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Bfs(int n){ for (int i = 0; i <= n; ++i) d[i] = oo; queue Q; d[S] = 0; Q.push(S); while ( !Q.empty() ){ int u = Q.front(); Q.pop(); for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] == oo ){ d[v] = d[u] + 1; if ( v == T ) return true; Q.push(v); } } } return false;}int Dfs_Flow(int u){ if ( u != T ){ if ( d[u] != oo ){ for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] == d[u] + 1 ){ fa[v] = u; idx[v] = i; int r = Dfs_Flow(v); if ( r != nil && r != u ) return r; } } d[u] = oo; } } else { int cf = oo, r = fa[T]; for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c ); for (int i = T; i != S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; if ( !nod[idx[i]].c ) r = fa[i]; } maxflow += cf; return r; } return nil;}int Dinic(int n){ maxflow = 0; while ( Bfs(n) ) Dfs_Flow(S); return maxflow;}void Dfs_Conn(int u){ d[u] = low[u] = t = t + 1; sta.push(u); vis[u] = inSta[u] = true; for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 ){ if (!vis[v] ){ Dfs_Conn(v); low[u] = min(low[u], low[v]); } else if ( inSta[v] ){ low[u] = min(low[u], d[v]); } } } if ( low[u] == d[u] ){ ++scc_num; do { int tt = sta.top(); sta.pop(); scc[tt] = scc_num; inSta[tt] = false; if ( tt == u ) break; } while ( !sta.empty() ); }}void Dfs_Conn_Build(int n, int m){ sum = scc_num = 0; int tot = n*m; for (int i = 0; i < tot; ++i) vis[i] = inSta[i] = false; for (int i = 0; i < tot; ++i) if ( !vis[i] ) Dfs_Conn(i); for (int i = 0; i < scc_num; ++i) scc_cnt[i] = 0; for (int i = 0; i < tot; ++i) scc_cnt[scc[i]] += 1; for (int i = 0; i < n; ++i) for (int j = m-1; j >= 0; --j){ int u = i*m+j; if ( scc_cnt[scc[u]] != 1 ) break; if ( a[u] > 0 ) sum += a[u], AddEdge(S, u, a[u]); else AddEdge(u, T, -a[u]); } printf("%d\n", sum-Dinic(n*m+1));}int main(){ int n,m; while ( scanf("%d%d", &n, &m) != EOF ){ Init(n*m); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j){ int w; scanf("%d%d", &a[i*m+j], &w); if ( j+1 < m ){ AddEdge(i*m+j, i*m+j+1, oo); } if ( w > 0 ){ while ( w-- ){ int r,c; scanf("%d%d", &r, &c); AddEdge(r*m+c, i*m+j, oo); } } } Dfs_Conn_Build(n,m); } return 0;}
[vijos 终极情报网]最小费用流
From:
Solution:
实数的费用流没怎么做, 处理不好就会出现精度问题造成负环。思路很简单, 把乘法取对数转换成加法, 就变成熟悉的最短路问题, 就可以用费用流了。
#include#include #include #include #include #include #include #include #include using namespace std;#define N 405#define M 101#define oo 0x6fffffff#define oof 10000000.0#define nil (-1)struct { int c,to,next; double w;} nod[N*N];bool inQ[N];double d[N], as[N];int adj[N], fa[N], idx[N], maxflow, now, S, T;void Init(int n){ now = 0; S = n+1; T = n+2; for (int i = 0; i <= T; ++i) adj[i] = nil;}int NewNode(int u, int c, double w){ nod[now].to = u; nod[now].c = c; nod[now].w = w; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int c, double w){ int u1 = NewNode(v, c, w); int v1 = NewNode(u, 0, -w); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Spfa(int n){ for (int i = 0; i <= n; ++i) d[i] = oof, fa[i] = nil, inQ[i] = false; queue Q; d[S] = 0; Q.push(S); inQ[S] = true; while ( !Q.empty() ){ int u = Q.front(); Q.pop(); inQ[u] = false; for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; double dd = d[u] + nod[i].w; if ( nod[i].c > 0 && fabs(d[v]-dd) > 1e-10 && d[v] > dd ){ d[v] = dd; fa[v] = u; idx[v] = i; if ( !inQ[v] ) inQ[v] = true, Q.push(v); } } } return d[T] != oof;}double Argument(){ int cf = oo; for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c); for (int i = T; i != S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; } maxflow += cf; return d[T]*cf;}void Output_Ans(double x){ int ans[15], n = 0, va = 0; while ( va < 5 ){ int m = (int)(x); ans[n++] = m; if ( m||va ) ++va; x = (x-m)*10; } if ( (int)x >= 5 ) ans[n-1] += 1; for (int i = n-1; ans[i] >= 10; --i){ ans[i-1] += ans[i]/10; ans[i] %= 10; } printf("%d.", ans[0]); for (int i = 1; i < n; ++i) printf("%d", ans[i]); printf("\n");}void MaxCost_Flow(int n, int k){ maxflow = 0; double ans = 0; while ( Spfa(n) ) ans += Argument(); if ( maxflow < k ) printf("0\n"); else Output_Ans(exp(-ans));}int main(){ int n,m; while ( scanf("%d%d", &n, &m) != EOF ){ Init(n); AddEdge(S, 0, m, 0); for (int i = 1; i <= n; ++i) scanf("%lf", &as[i]); for (int i = 1; i <= n; ++i){ int a; scanf("%d", &a); if ( a ) AddEdge(0, i, a, -log(as[i])); } for (int i = 1; i <= n; ++i){ int a; scanf("%d", &a); if ( 1 == a ) AddEdge(i, T, oo, 0); } double ww; int x,y,z; while (scanf("%d%d", &x, &y) && x != -1 && y != -1 ){ scanf("%lf%d", &ww, &z); AddEdge(x, y, z, -log(ww)); AddEdge(y, x, z, -log(ww)); } MaxCost_Flow(n+2,m); } return 0;}
[vijos 疯狂的方格取数]最大费用流
From:
Solution:
裸的最大费用最大流, 拆点建图。
#include#include #include #include #include #include #include #include #include using namespace std;#define N 4005#define M 101#define oo 0x6fffffff#define nil (-1)bool inQ[N];struct { int c,w,to,next;} nod[20*N];int adj[N], d[N], fa[N], idx[N], now, S, T,maxflow;void Init(int n){ now = 0; S = n; T = n+1; for (int i = 0; i <= T; ++i) adj[i] = nil;}int NewNode(int u, int w, int c){ nod[now].to = u; nod[now].w = w; nod[now].c = c; nod[now].next = nil; return now++;}void AddEdge(int u, int v, int w, int c){ int u1 = NewNode(v, w, c); int v1 = NewNode(u, -w, 0); nod[u1].next = adj[u]; adj[u] = u1; nod[v1].next = adj[v]; adj[v] = v1;}bool Spfa(int n){ for (int i = 0; i <= n; ++i) d[i] = -oo, fa[i] = nil, inQ[i] = false; queue Q; d[S] = 0; Q.push(S); inQ[S] = true; while ( !Q.empty() ){ int u = Q.front(); Q.pop(); inQ[u] = false; for (int i = adj[u]; i != nil; i = nod[i].next){ int v = nod[i].to; if ( nod[i].c > 0 && d[v] < d[u] + nod[i].w ){ d[v] = d[u] + nod[i].w; fa[v] = u; idx[v] = i; if ( !inQ[v] ) inQ[v] = true, Q.push(v); } } } return d[T] != -oo;}int Argument(){ int cf = oo; for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c); for (int i = T; i != S; i = fa[i]){ nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf; } maxflow += cf; return d[T];}int MinCost_Flow(int n){ maxflow = 0; int cost = 0; while ( Spfa(n) ) cost += Argument(); return cost;}int main(){ int n, m, k; while ( scanf("%d%d%d", &k, &m, &n) != EOF ){ Init(2*n*m); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j){ int tmp; scanf("%d", &tmp); AddEdge(i*m+j, i*m+j+n*m, tmp, 1); AddEdge(i*m+j, i*m+j+n*m, 0, oo); } for (int i = 0; i < n-1; ++i) for (int j = 0; j < m-1; ++j){ int k1 = i*m+j+1, k2 = (i+1)*m+j; AddEdge(i*m+j+n*m, k1, 0, oo); AddEdge(i*m+j+n*m, k2, 0, oo); } for (int j = 0; j < m-1; ++j){ int k1 = (n-1)*m+j+1; AddEdge((n-1)*m+j+n*m, k1, 0, oo); } for (int i = 0; i < n-1; ++i){ int k1 = (i+1)*m+m-1; AddEdge(i*m+m-1+n*m, k1, 0, oo); } AddEdge(S, 0, 0, k); AddEdge(2*n*m-1, T, 0, k); printf("%d\n", MinCost_Flow(2*n*m+1)); } return 0;}