网络流快乐地跑...
这道题就是要求这个无向图的最小割.
根据最小割最大流定理, 我们求个最大流就好了.
但是数据巨大. 一百万个点, 我们看上去就有 2996001 条边.
这个时候, 如果按照网络流做法, 建反向边的话, 需要 11984004 条边, MLE.
其实我就没做过无向图的网络流...
结论: 无向图网络流, 只要两条边捆绑在一起就可以了, 互相为反向边.
为什么有向图的时候反向边边权为 0, 而这里不为 0?
无向图有两条边, 你必须加上去. 有向图压根就没有这条边, 只是给你一个反悔的机会而已, 是个中介的边.
所以建上 5992002 条边, 跑一个有当前弧优化的 dinic, 直接完成.
代码:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- const int maxn = 1000005, INF = 0x7f7f7f7f;
- struct Edges
- {
- int next, to, weight;
- } e[maxn * 12];
- int head[maxn], tot = 1;
- int n, m, s, t;
- int dep[maxn];
- int cur[maxn];
- int queue[maxn <<1], front, rear;
- int id(int x, int y)
- {
- return (y - 1) * m + x;
- }
- int read()
- {
- int ans = 0, s = 1;
- char ch = getchar();
- while(ch> '9' || ch <'0')
- {
- if(ch == '-') s = -1;
- ch = getchar();
- }
- while(ch>= '0' && ch <= '9')
- {
- ans = ans * 10 + ch - '0';
- ch = getchar();
- }
- return s * ans;
- }
- void link(int u, int v, int w)
- {
- e[++tot] = (Edges){head[u], v, w};
- head[u] = tot;
- }
- void addEdges(int u, int v, int w)
- {
- link(u, v, w); link(v, u, 0);
- link(v, u, w); link(u, v, 0);
- }
- bool bfs()
- {
- memset(dep, 0, sizeof(dep));
- front = rear = 0;
- dep[s] = 1; queue[rear++] = s;
- while(front <rear)
- {
- int u = queue[front++];
- for(int i = head[u]; i; i = e[i].next)
- {
- int v = e[i].to;
- if(!dep[v] && e[i].weight> 0)
- {
- dep[v] = dep[u] + 1;
- queue[rear++] = v;
- }
- }
- }
- return dep[t];
- }
- int dfs(int u, int flow)
- {
- if(u == t) return flow;
- for(int &i = cur[u]; i; i = e[i].next)
- {
- int v = e[i].to;
- if(dep[v] == dep[u] + 1 && e[i].weight> 0)
- {
- int di = dfs(v, std::min(flow, e[i].weight));
- if(di> 0)
- {
- e[i].weight -= di;
- e[i ^ 1].weight += di;
- return di;
- }
- }
- }
- return 0;
- }
- int dinic()
- {
- int ans = 0;
- while(bfs())
- {
- for(int i = 1; i <= t; i++) cur[i] = head[i];
- while(int temp = dfs(s, INF)) ans += temp;
- }
- return ans;
- }
- int main()
- {
- n = read(), m = read();
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j < m; j++)
- {
- int weight = read();
- //printf("%d %d\n", id(j, i), id(j + 1, i));
- addEdges(id(j, i), id(j + 1, i), weight);
- }
- }
- for(int i = 1; i < n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- int weight = read();
- //printf("%d %d\n", id(j, i), id(j, i + 1));
- addEdges(id(j, i), id(j, i + 1), weight);
- }
- }
- for(int i = 1; i < n; i++)
- {
- for(int j = 1; j < m; j++)
- {
- int weight = read();
- //printf("%d %d\n", id(j, i), id(j + 1, i + 1));
- addEdges(id(j, i), id(j + 1, i + 1), weight);
- }
- }
- s = 1; t = n * m;
- printf("%d\n", dinic());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2698860.html