P6517 [CEOI2010 day1] alliances 题解
MarchKid_Joe
·
·
题解
P6517 [CEOI2010 day1] alliances
算法
题目
一共给出了 4 种限制。
第 1 种结点：与四连通的 1 个邻居 Union。
第 2 种结点：与四连通的 2 个邻居 Union。
第 3 种结点：与四连通的 3 个邻居 Union。
第 4 种结点：与四连通的 4 个邻居 Union。
但是第 2 种结点还有一个坑：就是不能同时与上下或左右 Union。
最后输出一种可行方案。
思路
看到这种配对的问题，自然要考虑网络流黑白染色思想了。
规定：对于二元组 (i,j)，若 i+j 为奇数，则为黑点；否则，为白点。而且：黑点只向白点连边，但是白点不向黑点连边。
有无解
判断是否有解只需要判断：黑点的权值和是否等于结盟数（也就是最大流）。
建图
初始化
源点 s 向所有黑点连边，权值为输入的数据。
所有白点向汇点 t 连边，权值为输入的数据。
联盟关系
分为两部分：
先考虑不包括第 2 种结点的情况（非人类点）：
首先，判断黑白点，若是白点，跳过；否则：黑点向白点连边，权值为 1。
再考虑包括第 2 种结点的情况：
发现人类比较特殊，含有两条限制：不能同时与上下或左右 Union。
那我们只需要把人类拆为 3 个点：第一个为初始点 x，第二个为管理上下方向的结点 x_1，第三个为管理左右的结点 x_2。
对于初始点，仍然限流为 2。
对于其他两个结点：
若此节点为黑点：
从初结点分别向 x_1 和 x_2 连接一条权值为 1 的边。然后 x_1 向这个结点的上下结点连边，权值为 1；x_2 向这个结点的左右结点连边，权值为 1。
若此节点为白点：
从 x_1 和 x_2 分别向初结点连接一条权值为 1 的边。然后这个结点的上下结点向 x_1 连边，权值为 1；这个结点的左右结点向 x_2 连边，权值为 1。
发现黑白点就是反着建图。
建图总结
源点 s 向黑点连边。
白点向汇点 t 连边。
黑点向白点连边。
把第 2 种结点——人类拆了。
最大流
网络流模板。
统计答案
正边没有流或者反边有流则证明这条边连接的两个结点 Union。
提醒
注意普通点 1,3,4 向人类点 2 连边时不是向初始点 x 连边，而是向另外两个管辖方向的点连边。（我吃亏了）
网络流反边流量为 0。（我又吃亏了）
答案的图的大小是原图的 3 倍。（我又双吃亏了）
最好将 (1,1) 结点设为黑点，这样就不用特判只有一个点的情况了（不特判 98 分）。因为如果 (1,1) 是白点，黑点贡献（联盟数量）为 0，最大流也是 0，就判断为有解了，显然错误。（我又双叒吃亏了）
编号方式：
对于二元组 $(i,j)$，编号为 $i\times(m-1)+j$。
对于第 $k$ 个人类的管辖方向的点，编号为 $n\times m+2\times k-x\qquad x\in[0,1]$。
统计答案时要**原图结点的坐标**，开个**桶**，下标为二元组对应的编号，内容存相应的二元组就行了。
~~这是我的编号方式。（这次没吃亏）~~
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define judge ((i + dx[k] >= 1 && j + dy[k] >= 1 && i + dx[k] <= n && j + dy[k] <= m) && (a[i + dx[k]][j + dy[k]]))
//judge 判断是否越界，是否为无人区。
const int inf = 1 << 30;
const int N = 70 + 5;
const int M = 3 * N * N;
const int s = M - 1;//原点
const int t = M - 2;//汇点
namespace IO
{
struct type//二元组，其实就是pair<int,int>
{
int x, y;
friend bool operator<(const type &A, const type &B){return A.x != B.x ? A.x < B.x : A.y < B.y;}
type(int x = 0, int y = 0) : x(x), y(y){}
};
template <typename Type> void read(Type &n)
{
Type w=1;char x=getchar();n=0;
while(x<'0'||x>'9'){if(x=='-')w=-1;x=getchar();}
while(x>='0'&&x<='9'){n=(n<<1)+(n<<3)+(x^48);x=getchar();}
n*=w;
}
template <typename Type,typename...Etc> void read(Type &n,Etc &...etcs)
{
read(n);read(etcs...);
}
template <typename Type> void write(Type x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
}
using namespace IO;
namespace network//网络流模板，此部分不解释
{
struct edge
{
int u;
int v;
int w;
int nxt;
edge(int u = 0, int v = 0, int w = 0, int nxt = 0) : u(u), v(v), w(w), nxt(nxt){}
};
edge e[M << 4];
int head[M];
int dep[M];
int cur[M];
int ecnt = 1;
void add(int u, int v, int w)
{
e[++ecnt] = edge(u, v, w, head[u]); head[u] = ecnt;
e[++ecnt] = edge(v, u, 0, head[v]); head[v] = ecnt;
}
bool bfs()
{
queue<int> q;
memcpy(cur, head, sizeof(cur));
memset(dep, 0, sizeof(dep));
dep[s] = 1;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (e[i].w && !dep[v])
{
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u, int flow)
{
if (u == t)
return flow;
int i, rest = flow;
for (i = cur[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (e[i].w && dep[v] == dep[u] + 1)
{
int k = dfs(v, min(e[i].w, rest));
rest -= k;
e[i].w -= k;
e[i ^ 1].w += k;
if (!rest)
break;
}
}
cur[u] = i;
return flow - rest;
}
int maxflow()
{
int ans = 0;
while (bfs())
ans += dfs(s, inf);
return ans;
}
}
using namespace network;
int n, m, sum;
int a[N][N], b[N * 3][N * 3];//原图和答案图，记得开 3 倍
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
//下，上，右，左
int personcnt;
//人的个数
map<type, type> person;
//人拆出来的两个管辖方向的点
map<type, bool> Union;
//判断两个点是否联合。
type point[M];
//桶存相应的点的坐标
bool black(type p)//判断是否为黑点
{
return !((p.x + p.y) & 1);
}
int get_num(type p)//得到二元组的编号
{
return (p.x - 1) * m + p.y;
}
void get_edge()//建边
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
read(a[i][j]);
type now = type(i, j);
sum += a[i][j] * black(now);
if (black(now))//s->黑点
add(s, get_num(now), a[i][j]);
else//白点->t
add(get_num(now), t, a[i][j]);
point[get_num(now)] = now;
if (a[i][j] == 2)
{
++personcnt;//人类+1
person[now] = type(n * m + 2 * personcnt - 1, n * m + 2 * personcnt);//拆点
point[person[now].x] = now;
point[person[now].y] = now;
if (black(now))//黑点->x1,x2
{
add(get_num(now), person[now].x, 1);
add(get_num(now), person[now].y, 1);
}
else//x1,x2->白点
{
add(person[now].x, get_num(now), 1);
add(person[now].y, get_num(now), 1);
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
type u = type(i, j);
if (!black(u) || a[i][j] == 0)
continue;//白点，无人区不连边
for (int k = 0; k < 4; k++)
{
type v = type(i + dx[k], j + dy[k]);
if (judge)
{
if (a[i + dx[k]][j + dy[k]] == 2)//连向的点是人类
{
if (a[i][j] == 2)//当前点是人类
{
if (k < 2)//上下
add(person[u].x, person[v].x, 1);
else//左右
add(person[u].y, person[v].y, 1);
}
else//当前点是普通点
{
if (k < 2)
add(get_num(u), person[v].x, 1);
else
add(get_num(u), person[v].y, 1);
}
}
else//连向的点是普通点
{
if (a[i][j] == 2)
{
if (k < 2)
add(person[u].x, get_num(v), 1);
else
add(person[u].y, get_num(v), 1);
}
else
add(get_num(u), get_num(v), 1);
}
}
}
}
}
}
void get_map()
{
for (int i = 1; i <= n * 3; i++)
for (int j = 1; j <= m * 3; j++)
b[i][j] = '.';//初始化全部没人
for (int i = 2; i <= ecnt; i += 2)//Union
{
if (e[i].u != s && e[i].v != t && !e[i].w)
{
int u = get_num(point[e[i].u]);
int v = get_num(point[e[i].v]);
Union[type(u, v)] = true;
Union[type(v, u)] = true;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i][j])//若当前不是无人区
{
int xl = 3 * (i - 1) + 1, xr = 3 * i;
int yl = 3 * (j - 1) + 1, yr = 3 * j;
int xmid = (xl + xr) >> 1, ymid = (yl + yr) >> 1;
b[xmid][ymid] = 'O';
for (int k = 0; k < 4; k++)
if (judge && Union.count(type(get_num(type(i, j)), get_num(type(i + dx[k], j + dy[k])))))//判断四个方向是否 Union
b[xmid + dx[k]][ymid + dy[k]] = 'X';
}
}
}
}
signed main()
{
int total = 0;
read(n, m);
get_edge();//建边
if (sum != maxflow())//判断
{
printf("Impossible!");
return 0;
}
get_map();//答案
for (int i = 1; i <= n * 3; i++)//print
{
for (int j = 1; j <= m * 3; j++)
{
putchar(b[i][j]);
}
putchar('\n');
}
return 0;//never give up.
}
```
## 后言
感谢 @[Ptilopsis_w](https://www.luogu.com.cn/user/239167) DaLao 对本人错误思想的指出及正确思想的提供。
感谢管理员大大抽出时间审核。