【LA 5928】[2016-2017 ACM-ICPC CHINA-Final] Mr.Panda and TubeMaster

相关链接

题目传送门：https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=769&page=show_problem&problem=5928

中文题面

Mr. Panda很喜欢玩游戏。最近，他沉迷在一款叫Tube Master的游戏中。
在Tube Master游戏中，玩家可以在$N\times M (N,M \le 30)$的网格中放置管道。每个网格要么为空格子，要么放置下面四种管子中的一种。

当两个相邻（有公共边的格子视为相邻）的格子中间有管道连接（例如下面这幅图），那么玩家将会得到一些分数（具体细节将在输入描述中给出）。

游戏中，有些格子是关键格子。对于每一个关键格子，玩家必须放置这四种管道中的任意一种，不得留空，否则玩家将输掉整局游戏。
玩家放好管道后，这个$N\times M$的网格必须满足以下两个条件，否则玩家将输掉整局游戏。
1. 每个格子要么没有管道，要么这个格子的管道是环形管道的一部分。
2. 每个关键格子必须放置管道。
特别地，如果没有关键格子，那么空网格也是一组合法解。
可以有多个环。

在上面三张图中，灰色格子是关键格子。其中：
左边的图不合法，因为关键格子没有放管道。
中间的图合法。
右边的图不合法，因为管道没有构成环。
Mr. Panda想要打赢这局游戏并且拿到尽可能多的分数。你能帮他计算他最多能拿多少分吗？

解题报告

这是一道非常玄妙的费用流题目

我们先将所有的点黑白染色
然后我们钦定黑点是从横变竖，白点是从竖变横（如果刚好相反的话，我们把这个环给反向就可以了）
之后我们再把每个点拆成入度和出度两个点，入度全部放左边，出度放右边
根据我们的旨意，黑色的入度只能匹配其上下的方格的出度，其出度只能匹配其左右两个方格的入度
我们在连边的时候，注意这个限制。
根据这个题目的启示TopCoder – Curvy on Rails，如果存在完备匹配，这个匹配的意义一定是几个圈

现在唯一的问题就是，有一些点可以不选了
那么我们可以认为他的出度与自己的入度匹配了（自环）
于是对于不必选的点我们连一条自己到自己的边，必选的边不连
之后搞一发费用流就可以了！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 100000;
const int INF = 1e9;

int n,m,S,T,E,head[N],nxt[M],cost[M],flow[M],to[M];
int pos[30][30],cx[30][30],cy[30][30],vis[30][30];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int AddEdge(int u, int v, int c, int f) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
	return E - 1;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N];
    queue<int> que; 
    public:
        inline int MaxFlow() {
            int ret_cost = 0, ret_flow = 0;
            for (int f=INF,w;SPFA();f=INF) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                ret_cost += dis[T] * f;
                ret_flow += f;
            }
            return ret_flow == n * m? ret_cost: -INF;
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

inline int id(int x, int y, int t) {
	return ((y - 1) * n + x - 1) * 2 + t;
}

int main() {
	for (int TT=read(),t=1;t<=TT;t++) {
		S = 0; T = N - 1; E = 1; memset(head,0,sizeof(head));
		printf("Case #%d: ",t);	m = read(); n = read();
		for (int j=1,v;j<=m;j++) for (int i=1;i<n;i++) cx[i][j] = -read();
		for (int j=1,v;j<m;j++) for (int i=1;i<=n;i++) cy[i][j] = -read();
		for (int e=read(),x,y;e;e--) x=read(), y=read(), vis[y][x] = t;
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				AddEdge(S, id(i,j,1), 0, 1);
				AddEdge(id(i,j,2), T, 0, 1);
				if (vis[i][j] != t) AddEdge(id(i,j,1), id(i,j,2), 0, 1); 
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				if ((i + j) & 1) {
					if (i < n) AddEdge(id(i+1,j,1), id(i,j,2), cx[i][j], 1);
					if (i > 1) AddEdge(id(i-1,j,1), id(i,j,2), cx[i-1][j], 1);
					if (j < m) AddEdge(id(i,j,1), id(i,j+1,2), cy[i][j], 1);
					if (j > 1) AddEdge(id(i,j,1), id(i,j-1,2), cy[i][j-1], 1);
				} 
			}
		}
		int tmp = MCMF.MaxFlow();
		if (tmp == -INF) puts("Impossible");
		else printf("%d\n",-tmp);
	}
	return 0;
}

—————————— UPD 2017.3.22 ——————————
Claris给我讲了一点新的姿势，不需要原来的无源汇带上下界费用流了
只需要一个普通的费用流即可，已经更新
Claris真是太强了 _(:з」∠)_