hdu 3452 Bonsai
一颗带权的树，求最小割使根和叶不连通添加汇点，每个叶子向其连权值为inf的边，求根到汇点的最小割
hdu 3491 Thieves
基于点的最小割，将每个点拆分成入和出两点
hdu 3987 Harry Potter and the Forbidden Forest
求最少割边数的最小割集，实际上就是求原图有多少次扩增。借鉴了别人的方法，建图的时候将原权值变为 A = A*(N+1)+1，那么最后得到的maxFlow = (.....)*(N+1)+B，而B就是扩增次数。
hdu 2435 There is a war
在原有向图中可以添加或修改一条原有的边使其权值为inf。求最大的最小割
分析：
如果是修改原有边，则该边的端点必然在原图的割集中，假设修改的边为e{a, b}，则再跑一边最大流maxFlow = min(maxFlow(S, a), maxFlow(b,T))。因为原图的割集互不影响，所以可以枚举找出以每个割集中割点为新汇点的最大流，最后求出两者中的最小值即为解。
若添加新边，如果原图中S和T连通则同上。否则，由于S和T所在部分已经构成了割集，所以解法同上。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int MAXN = 105; const int MAXM = MAXN*MAXN*2; int n, m; struct _edge { int v, nxt; int w; _edge(int vv, int ww, int nnxt):v(vv),w(ww),nxt(nnxt){} _edge(){} }ee[MAXM]; int head[MAXN], cnt, sto[MAXM], n1, n2; int cur[MAXN], dis[MAXN], gap[MAXN], pre[MAXN], ff[MAXN]; void add(int u, int v, int w) { ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++; ee[cnt] = _edge(u,0,head[v]); head[v] = cnt++; } int sap(int start,int end,int nodenum) { memset(dis,0,4*MAXN); memset(gap,0,4*MAXN); memcpy(cur,head,4*MAXN); int u=pre[start]=start; int maxflow=0,aug=-1; gap[0]=nodenum; while(dis[start]<nodenum) { loop: for(int &i=cur[u];i!=-1;i=ee[i].nxt) { int v=ee[i].v; if(ee[i].w&&dis[u]==dis[v]+1) { if(aug==-1||aug>ee[i].w) aug=ee[i].w; pre[v]=u; u=v; if(v==end) { maxflow+=aug; for(u=pre[u];v!=start;v=u,u=pre[u]) { ee[cur[u]].w-=aug; ee[cur[u]^1].w+=aug; } aug=-1; } goto loop; } } int mindis=nodenum; for(int i=head[u];i!=-1;i=ee[i].nxt) { int v=ee[i].v; if(ee[i].w && mindis>dis[v]) { cur[u]=i; mindis=dis[v]; } } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } void dfs(int u) { ff[u] = 1; ++n1; for (int i = head[u]; ~i; i=ee[i].nxt) { int v = ee[i].v; if (!ff[v] && (i&1)==0 &&ee[i].w > 0) dfs(v); } } void _dfs(int u) { ff[u] = 2; ++n2; for (int i = head[u]; ~i; i=ee[i].nxt) { int v = ee[i].v; if (!ff[v] && (i&1) == 1 && ee[i^1].w > 0) _dfs(v); } } void init() { cnt = 0; memset(head, -1, sizeof head); memset(ff, 0, sizeof ff); n1 = n2 = 0; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int t, res, a, b; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); init(); while (m--) { int u, v, c; scanf("%d%d%d", &u, &v, &c); add(u, v, c); } int pp = sap(1, n, n); a = 0, b = 0; dfs(1); _dfs(n); for (int i = 0; i< cnt; ++i) sto[i] = ee[i].w; for (int u = 2; u< n; ++u) { if (ff[u] == 1) { for (int i = 0; i< cnt; ++i) ee[i].w = sto[i]; a = max(a, sap(1,u,n1)); } else if (ff[u] == 2) { for (int i = 0; i< cnt; ++i) ee[i].w = sto[i]; b = max(b, sap(u,n,n2)); } } printf("%d\n", min(a,b)+pp); } return 0; }
hdu 3996 Gold Mine（最大闭合权图）
闭合图的概念：在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。构造方法：一个点的权值如果为正，则与S相连，且边权为该点的权值，如果为负，则与T相连，且边权为该点权值的绝对值，原来的边的权值设为正无穷。#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> using namespace std; typedef __int64 LL; const int MAXN = 3010; const int MAXM = MAXN*55*2; const LL INF = LL(1)<<55; int n, m; struct _edge { int v, nxt; LL w; _edge(int vv, LL ww, int nnxt):v(vv),w(ww),nxt(nnxt){} _edge(){} }ee[MAXM]; int head[MAXN], cnt; int cur[MAXN], dis[MAXN], gap[MAXN], pre[MAXN]; void add(int u, int v, LL w) { ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++; ee[cnt] = _edge(u,0,head[v]); head[v] = cnt++; } LL sap(int start,int end,int nodenum) { memset(dis,0,4*MAXN); memset(gap,0,4*MAXN); memcpy(cur,head,4*MAXN); int u=pre[start]=start; LL maxflow=0,aug=-1; gap[0]=nodenum; while(dis[start]<nodenum) { loop: for(int &i=cur[u];i!=-1;i=ee[i].nxt) { int v=ee[i].v; if(ee[i].w&&dis[u]==dis[v]+1) { if(aug==-1||aug>ee[i].w) aug=ee[i].w; pre[v]=u; u=v; if(v==end) { maxflow+=aug; for(u=pre[u];v!=start;v=u,u=pre[u]) { ee[cur[u]].w-=aug; ee[cur[u]^1].w+=aug; } aug=-1; } goto loop; } } int mindis=nodenum; for(int i=head[u];i!=-1;i=ee[i].nxt) { int v=ee[i].v; if(ee[i].w && mindis>dis[v]) { cur[u]=i; mindis=dis[v]; } } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } void init() { cnt = 0; memset(head, -1, sizeof head); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int t, cs = 0, nl, ng, ww, ed = 3000; LL cost, val, res; scanf("%d", &t); while (t--) { res = 0; n = 0; init(); printf("Case #%d: ", ++cs); scanf("%d", &nl); for (int i = 1; i<= nl; ++i) { scanf("%d", &ng); for (int j = 1; j<= ng; ++j) { int d = (i-1)*25+j, a, b; ++n; scanf("%I64d%I64d%d", &cost, &val, &ww); val = val - cost; if (val > 0) add(0, d, val), res+=val; else if (val < 0) add(d, ed, -val); while (ww--) { scanf("%d%d", &a, &b); a = (a-1)*25+b; add(d, a, INF); } } } printf("%I64d\n", res-sap(0,ed,2+n)); } return 0; }
hdu 3870 Catch the Theves（平面图最小割最短路）
将平面图的最小割问题转化为最短路问题#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <vector> using namespace std; typedef __int64 LL; const int MAXN = 405*405; const int MAXM = MAXN*4; int n, m; struct _edge { int v, nxt; int w; _edge(int vv, int ww, int nnxt):v(vv),w(ww),nxt(nnxt){} _edge(){} }ee[MAXM]; int head[MAXN], cnt; int vis[MAXN]; void add(int u, int v, int w) { ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++; ee[cnt] = _edge(u,w,head[v]); head[v] = cnt++; } void init() { cnt = 0; memset(head, -1, sizeof head); memset(vis, 0, sizeof vis); } struct _node { int u, w; _node(int a, int b):u(a),w(b){} _node(){} bool operator < (const _node & a) const { return w > a.w; } }; priority_queue<_node> qq; int solve(int S, int T) { while (!qq.empty()) qq.pop(); _node tn(S, 0); int v, w, res; qq.push(tn); while (!qq.empty()) { tn = qq.top(); qq.pop(); if (vis[tn.u]) continue; vis[tn.u] = 1; if (tn.u == T) { res = tn.w; break; } for (int i = head[tn.u]; ~i; i=ee[i].nxt) { if (vis[v=ee[i].v]) continue; qq.push(_node(v, tn.w+ee[i].w)); } } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int t, a, p, S, T, k; scanf("%d", &t); while (t--) { scanf("%d", &n); S = n*n; T = S+1; init(); for (int i = 0; i< n; ++i) for (int j = 0; j< n; ++j) { scanf("%d", &a); p = i*n+j; if (j == 0 && i != n-1) add(T, p, a); if (i == n-1 && j != n-1) add(T, p-n, a); if (i == 0 && j != n-1) add(S, p, a); if (j == n-1 && i != n-1) add(S, p-1, a); if (j > 0 && j < n-1 && i < n-1) add(p, p-1, a); if (i > 0 && i < n-1 && j < n-1) add(p-n, p, a); } printf("%d\n", solve(S, T)); } return 0; }